首页 > 代码库 > hdu 4658 Integer Partition
hdu 4658 Integer Partition
http://acm.hdu.edu.cn/showproblem.php?pid=4658
这道题不会做,看着别人的写的。这道题求的是一个数的划分,但是划分中一个数不能重复k次,用到了五边形数定理,没看懂。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 100005 5 using namespace std; 6 const int mod=1000000007; 7 8 int dp[maxn]; 9 10 void inti()//一个数的划分11 {12 dp[0]=1;13 for(int i=1; i<=100000; i++)14 {15 dp[i]=0;16 for(int j=1; ; j++)17 {18 int x=(3*j-1)*j/2;19 if(x>i) break;20 int s=dp[i-x];21 if(x+j<=i) s=(s+dp[i-j-x])%mod;22 if(j&1) dp[i]=(dp[i]+s)%mod;23 else dp[i]=(dp[i]-s+mod)%mod;24 }25 }26 }27 28 int main()29 {30 inti();31 int t;32 scanf("%d",&t);33 while(t--)34 {35 int n,k;36 scanf("%d%d",&n,&k);37 int ans=dp[n];38 for(int i=1; ; i++)39 {40 int x=k*i*(3*i-1)/2;41 if(x>n) break;42 int c=dp[n-x];43 if(x+i*k<=n) c=(c+dp[n-x-k*i])%mod;44 if(i&1) ans=(ans-c+mod)%mod;45 else ans=(ans+c)%mod;46 }47 printf("%d\n",ans);48 }49 return 0;50 }
hdu 4658 Integer Partition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。