这个题真是坑啊,到现在为止我都不知道为什么有个地方加了会错,以个人看绝对不会错,就是注释部分,比总和大的因子不可能出现,所以可以省略不要,为什么省略了就会错,我一天的时间砸在上面砸出这么个破结论,不知道acm的严密性哪儿去了
哎,代码发这里,大神们谁能解决我的问题
我刚开始也是看别人的解题报告,都说裸dp,对于我们这些xx们,还是清楚点好;
滚动dp【i%2】【j】【k】,array里面存了公倍数的因子,pos【1001】里面存了某个因子在array中哪个位子
那么dp【i%2】【j】【k】,的意思就是前i个数的和为j,公倍数为第k个位子中的因子(因为这些子公倍数都会是总公倍数的因子,自己都糊涂了,呵呵,希望大家好好理解)
而刚好有了dp的一个重要性质,后面的抉择只与前面的结果有关,与前面的抉择无关,刚好有了和j,公倍数k,就可以用后面的抉择以此算出和跟公倍数,因此形成递推关系
还有个小技巧就是预处理lcm最小公倍数,否则超时,哎,不得不感叹现场赛卡得紧啊
也有一些小感受吧,如果感觉算法时间内能过,尽量多找地方优化,比如这个题目的公倍数都是总公倍数的因子(虽然不这样,算法也只算那么多次,但开的数组就大很多,初始化也就浪费了很多时间,这是今天最大的收获),%2变成&2位运算优化,memset初始化优化
#include <iostream>
#include<stdio.h>
#include<string.h>
#define INF 1000000007
using namespace std;
int n,m,k;
int dp[2][1005][105];
int array[1005],anum,LCM[1005][1005],pos[1005];
int gcd(int a,int b)
{
int max,min;
if(a>b)
max=a;
else
max=b;
min=a+b-max;
if(max%min==0)
return min;
return gcd(min,max%min);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int i,j,q,p,s,l,pp;
for(i=1;i<=1000;i++)
for(j=i;j<=1000;j++)
LCM[i][j]=LCM[j][i]=lcm(i,j);
while(scanf("%d%d%d",&m,&k,&n)!=EOF)
{
memset(dp,0,sizeof(dp));
anum=0;
for(i=1;i<=k;i++)
{
// if(i>m) //注释去掉竟然错了,求解释
// break;
if(k%i==0)
{
array[++anum]=i;
pos[i]=anum;
dp[1%2][i][anum]=1;
}
}
for(q=2;q<=n;q++)
{
memset(dp[q&1],0,sizeof(dp[q&1]));
for(i=1;i<=m;i++)
for(pp=1;pp<=anum;pp++)
{
if(dp[1-q&1][i][pp])
{
for(p=1;p<=anum;p++)
{
s=i+array[p];
if(s>m)
break;
l=LCM[array[pp]][array[p]];
dp[q&1][s][pos[l]]+=dp[1-q&1][i][pp];
while(dp[q&1][s][pos[l]]>=INF)
dp[q&1][s][pos[l]]-=INF;
}
}
}
}
printf("%d\n",dp[n&1][m][pos[k]]);
}
return 0;
}