AOJ 1269,PKU 3132 Sum of Different Primes

概要

2数n(<=1120),k(<=14)が与えられる。
nを異なるk種類の素数の和で表すとき、その表し方の個数を求めよ。
ただし順番が異なるだけのものは同じものと見なす。

考え方

メモ化再帰するだけ。

実装(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> primes;
typedef long long lli;
lli dp[1121][15][200];
int solve(int n,int k,int used){
  lli res=0;
  if(n==0&&k==0)return 1;
  if(k==0)return 0;
  if(n<=0)return 0;
  if(dp[n][k][used]>=0)return dp[n][k][used];
  for(int i=used;i<(int)primes.size();i++){
    if(n-primes[i]<0)break;
    res+=solve(n-primes[i],k-1,i+1);
  }
  return dp[n][k][used]=res;
}
int main(){
  for(int i=2;i<=1120;i++){
    bool isprime=true;
    for(int j=2;j<i;j++)if(i%j==0)isprime=false;
    if(isprime)primes.push_back(i);
  }
  int n,k;
  memset(dp,-1,sizeof(dp));
  for(;;){
    cin>>n>>k;
    if(n==0)break;
    cout<<solve(n,k,0)<<endl;
  }
  return 0;
}