<span>HDU4658 Integer Partition（整数拆分+判断相同数）</span>
题意：将n划分为最大值不超过n的若干个数之和，每个数最多出现m-1次。问有多少种方案？
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> #include <cmath> #include <stdlib.h> #include <time.h> #include <algorithm> using namespace std; const int mod=1e9+7; int dp[100010]; void init() { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1; i<=100000; i++) { for(int j=1,r=1; i-(3*j*j-j)/2>=0; j++,r*=-1) { dp[i]+=dp[i-(3*j*j-j)/2]*r; dp[i]%=mod; dp[i]=(dp[i]+mod)%mod; if(i-(3*j*j+j)/2>=0) { dp[i]+=dp[i-(3*j*j+j)/2]*r; dp[i]%=mod; dp[i]=(dp[i]+mod)%mod; } } } } int solve(int n,int k) { int ans=dp[n]; for(int j=1,r=-1; n-k*(3*j*j-j)/2>=0; j++,r*=-1) { ans+=dp[n-k*(3*j*j-j)/2]*r; ans%=mod; ans=(ans+mod)%mod; if(n-k*(3*j*j+j)/2>=0) { ans+=dp[n-k*(3*j*j+j)/2]*r; ans%=mod; ans=(ans+mod)%mod; } } return ans; } int main() { init(); int t,n,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); printf("%d\n",solve(n,k)); } return 0; }
