ZOJ 3662 Math Magic（构造K个和为N且最小公倍数为M的正整数的方案数/dp）

题目链接：
ZOJ 3662 Math Magic
题意：
求构造K个和为N且最小公倍数为M的正整数的方案数。
1<=N,M<=1000,1<=K<=100.结果mod(1e9+7) .
如：N=2,M=2,K=2。有两种：(1,2)和(2,1)。
分析：
首先每个数都必须是M的约数，其次任意若干个数最小公倍数也必须是M的约数。
先预处理出1000以内的所有数的约数以及任意两个数的最小公倍数。
用dp[i][j][k]表示前i个数和为j最小公倍数是k的方案数。但是因为N和M及K的范围原因，这样直接用数组的话空间不够。
所以要用滚动数组。用dp[0][j][k]和dp[1][j][k]进行状态转化。
初始化：dp为0，但是dp[0][0][1]=1。
状态转移方程：
需要枚举上一状态的所有数字和，以及在这个和下的所有最小公倍数，然后枚举第i个数，就得到了前i个数的数字和以及最小公倍数，
dp[now][x][y]=(dp[now][x][y]+dp[pre][i][divisor[M][j]])%mod;
其中 x，y和i,divisor[M][j] 分别是当前状态以及上一状态的数字和与最小公倍数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
const int MAX_N=1010;
const int mod=(int)(1e9+7);

int N,M,K;
int dp[2][MAX_N][MAX_N];

int LCM[MAX_N][MAX_N],divisor[MAX_N][MAX_N],cnt[MAX_N];

inline int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

inline int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

inline void GetLCM()
{
    //LCM[i][j]是i和j的最小公倍数
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j++){
            LCM[i][j]=LCM[j][i]=lcm(i,j);
        }
    }
}

inline void GetDivisor()
{
    //divisor[i]保存i的约数,cnt[i]是i的约数个数
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=1000;i++){
        int tmp=0;
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                divisor[i][tmp++]=j;
                if(i/j!=j){
                divisor[i][tmp++]=i/j;
                }
            }
        }
        cnt[i]=tmp;
    }
}

int main()
{
    freopen("Jin.txt","r",stdin);
    GetLCM();
    GetDivisor();
    while(~scanf("%d%d%d",&N,&M,&K)){
        //memset(dp[0],0,sizeof(dp[0])); 如果用memset代替下面的四行会TLE，o(╯□╰)o
        for(int i=0;i<=N;i++){
            for(int j=0;j<=M;j++){
                dp[0][i][j]=0;
            }
        }
        dp[0][0][1]=1;
        int now=0,pre;
        for(int h=1;h<=K;h++){
            pre=now;
            now^=1;
            //memset(dp[now],0,sizeof(dp[now])); 如果用memset代替下面的四行会TLE，o(╯□╰)o
            for(int i=0;i<=N;i++){
                for(int j=0;j<=M;j++){
                    dp[now][i][j]=0;
                }
            }
            for(int i=h-1;i<=N;i++){ //前h-1个数的和是i
                for(int j=0;j<cnt[M];j++){ //枚举前h-1个数的和是i，LCM是divisor[M][j]的方案
                    if(dp[pre][i][divisor[M][j]]==0) continue;
                    for(int r=0;r<cnt[M];r++){ //枚举第h个数
                        int x=i+divisor[M][r];
                        int y=LCM[divisor[M][j]][divisor[M][r]];
                        if(x>N||M%y!=0) continue; //前h个数的和x>n或者前h个数的最小公倍数y不是M的约数
                        dp[now][x][y]=(dp[now][x][y]+dp[pre][i][divisor[M][j]])%mod;
                    }
                }
            }
        }
        printf("%d\n",dp[now][N][M]);
    }
    return 0;
}