HDU4658 Integer Partition（整数拆分+判断相同数）

题意：将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; }

 

转载于:https://www.cnblogs.com/d-e-v-i-l/p/4899238.html

总结

以上是生活随笔为你收集整理的HDU4658 Integer Partition（整数拆分+判断相同数）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。