Zoj 3662 Math Magic
littlechai
2020-12-25 15:42:42
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 1005;
const int p = 1e9+7;
int n, m, k;
int a[maxn], cnt, lcm[maxn][maxn];
int dp[2][maxn][maxn];
int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x%y);
}
int LCM(int x, int y){
return x*y/gcd(x, y);
}
void init(){
memset(dp, 0, sizeof(dp));
cnt = 0;
}
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) != EOF){
init();
for(int i = 1; i <= m;i ++){
if(m%i == 0) a[++ cnt] = i;
}
dp[0][0][1] = 1;
int l = 0;
for(int i = 0;i < k;i ++){
l ^= 1;
memset(dp[l],0,sizeof(dp[l]));
for(int j = 0;j <= n;j ++){
for(int w = 1;w <= cnt;w ++){
int y = a[w];
if(dp[l^1][j][y] == 0) continue;
for(int o = 1;o <= cnt;o ++){
int x = a[o];
if(lcm[y][x] <= m && j+x <= n){
dp[l][j+x][lcm[y][x]] += dp[l^1][j][y];
dp[l][j+x][lcm[y][x]] %= p;
}
}
}
}
}
printf("%d\n",dp[l][n][m]);
}
return 0;
}
```