HDU 4906. Our happy ending

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=4906

題意

給定n k L,求從區間[0,L]之間選n個數字滿足
從n個數字選取幾個使得選取的數字的和等於k
求這樣的n元素集合的個數

解法

動態規劃解法
f[i][s]表示選取了i個數字,i個數字中選某集合求和可以達到的狀態為s
總共20位,假設求和為sum,那麼sum位就置1
直接這樣超內存,可以用滾動數組也可以像背包問題那樣省略一維
具體看代碼

typedef long long LL;
const int mod=1000000007;
const int N=(1<<22)+5;
LL f[N];
void solve() {
    int n,k,l;
    scanf("%d%d%d",&n,&k,&l);
    memset(f,0,sizeof(f));
    f[0]=1;
    LL tmp=0;
    if(l>k) {
        tmp=l-k;
        l=k;
    }
    int all=(1<<k)-1;
    for(int i=0;i<n;i++) {
        for(int s=all;s>=0;s--) {
            if(f[s]==0) continue;
            LL now=f[s];
            LL add=f[s]*tmp;
            for(int j=1;j<=l;j++) {
                int st=(s|(1<<(j-1))|((s<<j)&all));
                f[st]+=now;
                f[st]%=mod;
            }
            f[s]+=add;
            f[s]%=mod;
        }
    }
    LL ans=0;
    for(int i=0;i<=all;i++) {
        if((i>>(k-1))&1) {
            ans+=f[i];
            ans%=mod;
        }
    }
    cout<<ans<<endl;
}