dp[i][j][k] i为K位的最小公倍数 j为k位的和 k以滚动数组的形式
这题最棒的是 有一个强有力的剪枝 组成公倍数m的肯定都是M的质因子 这样1000里面最多就30多个 复杂度可过了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
#define mod 1000000007
int dp[][][];
int q[][],f[],lc[][];
int p[];
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
int n,m,k,i,j,g;
for(i = ; i <= ; i++)
for(j = ; j <= ; j++)
lc[i][j] = i*j/gcd(i,j);
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
int o;
int to = ;
for(i =; i <= m ; i++)
if(m%i==)
{
to++;
p[to] = i;
}
memset(dp,,sizeof(dp));
for(i = ; i <= min(n,m) ; i++)
{
dp[i][i][] = ;
}
for(i = ; i <= k; i++)
{
for(o = ; o <= to ; o++)
for(g = ; g <= n ; g++)
dp[p[o]][g][i%] = ;
for(j = ; j <= to ; j++)
{
for(g = i-; g <= n ; g++)
{
if(dp[p[j]][g][(i-)%]==)
continue;
for(o = ; o <= to ; o++)
{
int x = lc[p[j]][p[o]];
if(g+p[o]>n)
break;
if(x>m)
continue;
dp[x][g+p[o]][i%] = (dp[x][g+p[o]][i%]+dp[p[j]][g][(i-)%])%mod;
}
}
}
}
printf("%d\n",dp[m][n][k%]);
}
return ;
}