题意：给定一个n，k，l。

问有多少长度为n的序列满足选出一些数使得他们相加为k，数列中每个数都在1-l以内。

Solution

正解还是很妙的。

状压dp，设dp[i][j]表示长度为i的序列，能表示出集合为j的序列个数。

这个状态非常好，我们每局下一个可填的数，可选集合就变成了j|(1<<p-1)|(j<<p&size)

Code

#include
     
      #include
      
       #include
       
        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<
        
         =0;--j)if(dp[j]){             ll pu=dp[j];             for(int p=1;p<=min(k,l);++p) {                int x=(1<
         
          <
          
           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<
           
            mod)ans-=mod;} printf("%lld\n",ans); } return 0;}