our happy ending(状压dp） _状压DP

得意犹堪夸世俗，诏黄新湿字如鸦。这篇文章主要讲述our happy ending(状压dp）相关的知识，希望能为你提供帮助。
题意：给定一个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 ",ans); } return 0; }

【our happy ending(状压dp）】