传送门：QAQQAQ
题意：给你一个数$n$，把它拆分成至多$k$个正整数，使得这些数的和等于$n$且每一个正整数的个数不能超过$4$
拆分的顺序是无序的，但取出每一个数方案是不同的（例如我要拆$1$，就有$4$种方案，因为$4$个“1”是不同的）
思路：依旧神仙题。。满分现阶段无望，现在逐步深入讲部分分的做法
40分：暴力，我们把$n$种数拆分成$4*n$个数，然后跑01背包就可以了，防止MLE，可以开滚动，但注意转移时要反着来
#include<bits/stdc++.h> using namespace std; const int MOD=1000000009; int dp[10001][21],n,k,a[40005]; int main() { while(scanf("%d%d",&n,&k)!=EOF) { if(k>n) k=n; if(n==0) break; memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=4*n;i++) a[i]=(i+3)/4; for(int i=1;i<=4*n;i++) { for(int j=min(i,k);j>=1;j--) { for(int t=n;t>=a[i];t--) { dp[t][j]=(dp[t][j]+dp[t-a[i]][j-1])%MOD; } } } int ans=0; for(int i=1;i<=k;i++) ans=(ans+dp[n][i])%MOD; printf("%d\n",ans); } return 0; }
60分：我们考虑转移时优化一维——即把枚举数的ID这一维优化掉
我们对于转移进行分类讨论：
1.若转移前数列中没有1，那么我们就可以一次性往现数列中加1，并对新加上的1进行“不同化”——即对加进的t个1乘上C(4,t)（这样可以保证2,3,4……都已进行“不同化”）
2.若转移中有1，那么我们就把数列中所有数都加一，使其没有1
我们可以设$dp[i][j][bl]$为和为$i$，取了$j$个数，数列中是否含有1（这种设状态较好理解）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD=1000000009; ll dp[100001][21][2],n,k; void add(ll &x,ll y) { x+=y; if(x>=MOD) x-=MOD; } ll c4[5]={1,4,6,4,1}; int main() { while(scanf("%lld%lld",&n,&k)!=EOF) { if(k>n) k=n; if(n==0&&k==0) break; memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(ll i=1;i<=n;i++) { for(ll j=1;j<=min(i,k);j++) { if(i>j) { add(dp[i][j][0],dp[i-j][j][0]); add(dp[i][j][0],dp[i-j][j][1]); } for(ll t=1;t<=min(j,4LL);t++) add(dp[i][j][1],dp[i-t][j-t][0]*c4[t]%MOD); } } ll ans=0; for(ll i=1;i<=k;i++) { add(ans,dp[n][i][0]); add(ans,dp[n][i][1]); } printf("%lld\n",ans); } return 0; }
当然，为了后面的八十分代码更方便，我们考虑对状态进行降维，我们把最后bl去掉，把“所有数加1”和“往数组里加1”两个操作一起进行
考虑到80分是矩阵快速幂，我们把剩下的两位压进一维（k比较小，所以可以压）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD=1000000009; ll dp[1000001],n,k; void add(ll &x,ll y) { x+=y; if(x>=MOD) x-=MOD; } ll c4[5]={1,4,6,4,1}; ll id(ll x,ll y) { return x*10+y; } int main() { while(scanf("%lld%lld",&n,&k)!=EOF) { if(k>n) k=n; if(n==0&&k==0) break; memset(dp,0,sizeof(dp)); dp[0]=1; for(ll i=1;i<=n;i++) { for(ll j=1;j<=min(i,k);j++) { for(ll t=0;t<=min(j,4LL);t++) add(dp[id(i,j)],dp[id(i-j,j-t)]*c4[t]%MOD); //先让原数组j-t个数都加1，再加入t个1 } } ll ans=0; for(ll i=1;i<=k;i++) { add(ans,dp[id(n,i)]); } printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/Forever-666/p/11291697.html