ZOJ 3662 Math Magic | The 2012 ACM-ICPC Asia Changchun Regional Contest – H

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3662

dp；

LCM的状态一定是M的约数，每次加入的数也是M的约数；

可以压缩LCM的状态到M的约数个； 需要预处理LCM；

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>

using namespace std;

#define MOD 1000000007
int N, M, K;
int restore[1010], compress[1010];
int dp[2][1010][110];
int LCM[1010][1010];
int cnt;

int gcd (int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm (int a, int b)
{
    return a / gcd(a, b) * b;
}
int main()
{
    for (int i = 1; i <= 1000; i++)
        for (int j = 1; j <= 1000; j++)
            LCM[i][j] = lcm(i, j);

    while (scanf("%d%d%d", &N, &M, &K) == 3)
    {
        memset(compress, -1, sizeof(compress));
        memset(restore, -1, sizeof(restore));
        cnt = 0;
        for (int i = 1; i <= M; i++)
            if (M % i == 0)
            {
                restore[cnt] = i;
                compress[i] = cnt++;
            }
        memset(dp[0], -1, sizeof(dp[0]));
        dp[0][0][0] = 1;
        for (int i = 1; i <= K; i++)
        {
            memset(dp[i&1], -1, sizeof(dp[i&1]));
            for (int j = i-1; j <= N; j++)
            {
                for (int k = 0; k < cnt; k++)
                {
                    if (dp[(i+1)&1][j][k] == -1)    continue;
                    for (int r = 0; r < cnt && j+restore[r] <= N; r++)
                    {
                        int jj = j + restore[r];
                        int kk = LCM[ restore[k] ][ restore[r] ];
                        if (kk <= M && compress[kk] != -1)
                        {
                            kk = compress[kk];
                            if (dp[i&1][jj][kk] == -1)      dp[i&1][jj][kk] = 0;
                            dp[i&1][jj][kk] += dp[(i+1)&1][j][k];
                            if (dp[i&1][jj][kk] >= MOD)     dp[i&1][jj][kk] %= MOD;
                        }
                    }
                }
            }
        }
        printf("%dn", dp[K&1][N][compress[M]] == -1 ? 0 : dp[K&1][N][compress[M]]);
    }
    return 0;
}