570
將一個數分解成多個素數和的方法數
題目描述：哥德巴赫猜想認為任一大於2的偶數，都可表示成兩個素數之和，比如
6 = 2+2+2
6 = 3+3
10 = 2+2+2+2+2
10 = 2+2+3+3
10 = 2+3+5
10 = 3+7
像3+7與7+3隻有順序不一樣的認為是一種方式
問：給定一個10000以內的偶數，將它表示為素數的和有幾種方式？(結果對10^9+7取模)
分析：相當於求以質數為物品體積，背包容量為10000的，可以重複選擇的背包，設p[i]是第i個質數，dp[i][n]表示把正整
數n拆分為不大於p[i]的若幹質數和的方案數，則有dp[i][n]=dp[i-1][n]+dp[i][n-p[i]]
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 10005;
const LL MOD = 1000000007;
bool prime[N];
int p[N];
int k;
vector<LL> v1;
vector<LL> v2;
vector<LL> *p1;
vector<LL> *p2;
void isprime()
{
k = 0;
int i,j;
memset(prime,true,sizeof(prime));
for(i=2;i<N;i++)
{
if(prime[i])
{
p[k++] = i;
for(j=i+i;j<N;j+=i)
{
prime[j] = false;
}
}
}
}
void Work()
{
p1 = &v1;
p2 = &v2;
for(int i=0;i<N;i++)
{
if(i&1) p1->push_back(0);
else p1->push_back(1);
}
for(int i=1;i<k;i++)
{
p2->clear();
for(int j=0;j<N;j++)
{
if(j < p[i]) p2->push_back((*p1)[j]%MOD);
else p2->push_back(((*p1)[j]%MOD + (*p2)[j-p[i]]%MOD)%MOD);
}
vector<LL> *tmp;
tmp = p2;
p2 = p1;
p1 = tmp;
}
}
int main()
{
int n;
isprime();
Work();
while(cin>>n)
{
cout<<(*p1)[n]<<endl;
}
return 0;
}
最後更新：2017-04-03 14:54:04