1269 - Sum of Different Primes

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1269

問題

n, kが与えられるので、nを異なる素数k個の和で表すときの表し方の数を求めよ。
ただし、順番を入れ替えただけのものは同じと考える。

解法

DP。
重複が許されないので、普通に考えるとどこまで使ったかという情報が欲しいが、ループの回し方を工夫することでそれを避けることが出来る。
DP[i][j] = 異なる素数i個使ってjを表す表し方
として値を更新していく。

使う素数の重複を許さないので、一番外側のループを使う素数にする。
あとは、何個素数を使ったかと和のループを回すが、１回で何回も足してしまわないように逆順にする。

計算量が少し多いメモ化再帰が多分一番簡単。


このような問題をやった記憶があったので自分のブログを見返したら、AOJ0537がほぼ同じ問題だった。(記事：[id:sune2:20110730:1312011633])

ソース

int dp[15][1121];
int main() {
  int N = 1300;
  vector<int> prime(N, 1);
  REP(i,N) prime[i] = i;
  prime[0] = prime[1] = 0;
  for (int i=2; i<N; ++i)
    if (prime[i])
      for (int j=i*2; j<N; j+=i)
        prime[j] = 0;
  prime.erase(remove(ALL(prime), 0), prime.end());
  
  dp[0][0] = 1;
  REP(i, prime.size())
    for (int j=13; j>=0; --j)
      for (int k=1120-prime[i]; k>=0; --k)
        dp[j+1][k+prime[i]] += dp[j][k];
  int n, k;
  while(cin>>n>>k,n||k)
    cout << dp[k][n] << endl;
}