题意: 给定一个 n,k,l.
问有多少长度为 n 的序列满足选出一些数使得他们相加为 k, 数列中每个数都在 1-l 以内.
Solution
正解还是很妙的.
状压 dp, 设 dp[i][j] 表示长度为 i 的序列, 能表示出集合为 j 的序列个数.
这个状态非常好, 我们每局下一个可填的数, 可选集合就变成了 j|(1<<p-1)|(j<<p&size)
- Code
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int mod=1e9+7;
- ll dp[1<<20],ans;
- int n,k,l,t,ma;
- int main(){
- scanf("%d",&t);
- while(t--){
- scanf("%d%d%d",&n,&k,&l);
- memset(dp,0,sizeof(dp));
- ma=(1<<k)-1;dp[0]=1;
- for(int i=1;i<=n;++i)
- for(int j=ma;j>=0;--j)if(dp[j]){
- ll pu=dp[j];
- for(int p=1;p<=min(k,l);++p) {
- int x=(1<<p-1)|j|((j<<p)&ma);
- dp[x]+=pu;
- if(dp[x]>mod)dp[x]-=mod;
- }
- if(l>k){
- dp[j]+=(pu*(l-k))%mod;
- if(dp[j]>mod)dp[j]-=mod;
- }
- }ans=0;
- for(int i=1;i<=ma;++i)if(i&(1<<k-1)){ans+=dp[i];if(ans>mod)ans-=mod;}
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2774954.html