题目大意:问有多少组满足,个数为k个,和为n最小公倍数为m
解题思路:首先我想到这个可能是dp,状态为前i个数组成和为j最小公倍数是k的方案数,但是这个时间复杂度和空间复杂度都很高。最后我的优化是将最小公倍数这个状态改变一下,事实上可以用到的数并不多,最多也就32个,(eg:10: 1 2 5 10)这样的话,我就解决了问题.
但是我写的总是超时,后来分析了很久,原来这个其实最大的一组数据状态只有10^6,并不是我分析的那么高,而且,这个如果用menset初始化数组的话,容易超时,原因可能是,这个题用到的状态并没有分析的那么多
code:
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <map> using namespace std; #define mod 1000000007 #define N 1010 int dp[102][N][33]; int n,m,k; int b[100],num; int get(int n) { int re = 0; for(int i = 1;i <= n;i++) { if(n % i == 0) b[re++] = i; } return re; } inline int gcd(int a,int b){ return b?gcd(b,a%b):a; } inline int LCM(int a,int b){ return a/gcd(a,b)*b; } map <int,int> mm; int LL[40][40]; int main() { while(scanf("%d%d%d",&n,&m,&k) != EOF) { mm.clear(); num = get(m); for(int i = 0;i < num;i++) mm[b[i]] = i; for(int i = 0;i < num;i++) for(int j = 0;j < num;j++) { LL[i][j] = mm[ LCM(b[i],b[j]) ]; } for(int i = 0;i <= k;i++) for(int j = 0;j <= n;j++) for(int k = 0;k <= num;k++) dp[i][j][k] = 0; dp[0][0][0] = 1; for(int i = 1;i <= k;i++) { for(int j = 0;j <= n;j++) for(int k = 0;k < num;k++) { for(int kk = 0;kk < num && j + b[kk] <= n;kk++) dp[i][j+b[kk]][LL[k][kk]] =(dp[i][j+b[kk]][LL[k][kk]] + dp[i-1][j][k])%mod; } } cout << dp[k][n][num-1] << "\n"; } return 0; }