HDU4427 Math Magic

2012长春, DP

　　2012 ACM/ICPC 长春赛区现场赛

　　题意：求选定k个数，使得这k个数的和为n、最小公倍数为m的方案数。 - 原题链接

　　初步想法是用f[i][j][k]表示i个数的和为j且最小公倍数为k的方案数，但时间复杂度过大，考虑如何优化，这里就要orz我队的DP大佬天神了。

　　首先我们有一个很显然的数学结论，如果若干数的最小公倍数是k，则它们每个数都是k的约数。打表不难发现，1000以内的数约数个数是很少的，所以我们修改f[i][j][k]的定义为i个数的和为j且最小公倍数是第k个约数的方案数，就能有效地降低时间复杂度。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>  
#include <algorithm>  
#include <string.h>  
#include <vector>  
#include <cmath>  
using namespace std;
const int maxn=1000+10, N=35, mod=(1e9)+7;
int n, m, k, p, f[100+10][maxn][N];
int lcm[maxn][maxn], val[N], pos[maxn];
int main()
{
	for(int i=1; i<maxn; i++)
		for(int j=1; j<maxn; j++)
			lcm[i][j]=i*j/__gcd(i, j);
	while(scanf("%d%d%d", &n, &m, &k)!=EOF)
	{
		p=0;
		memset(val, 0, sizeof val);
		memset(pos, 0, sizeof pos);
		for(int i=1; i<=m; i++)	if(m%i==0) val[++p]=i, pos[i]=p;
		
		memset(f, 0, sizeof f);
		f[0][0][1]=1;
		for(int i=1; i<=k; i++)
			for(int j=i-1; j<=n; j++)
				for(int x=1; x<=p; x++)
					for(int y=1; y<=p && j+val[y]<=n; y++)
					{
						int _lcm=lcm[val[x]][val[y]];
						if(_lcm<=m && pos[_lcm])	f[i][j+val[y]][pos[_lcm]]=(f[i][j+val[y]][pos[_lcm]]+f[i-1][j][x])%mod;
					}
		printf("%d\n", f[k][n][pos[m]]);
	}
	return 0;
}