首页 > 代码库 > HDU 4906 Our happy ending（2014 Multi-University Training Contest 4）

HDU 4906 Our happy ending（2014 Multi-University Training Contest 4）

2024-07-15 03:55:14   223人阅读

题意:构造出n个数 这n个数取值范围0-L，这n个数中存在取一些数之和等于k，则这样称为一种方法。给定n，k，L，求方案数。

思路：装压 每位 第1为表示这种方案能不能构成1（1表示能0表示不能）  第2为表示能不能构成2 。。。  这样用d[1<<n] 的DP  像背包那样背 n次就可以 最后状态中第k位为1的就可以加上方法数。

 

#include<cstring>#include<cstdio>#include<cmath>#include <iostream>#include<algorithm>#define LL long long#define MOD 1000000007#define debug(x) printf(#x"=%d\n",x);using namespace std;int d[(1<<20)+50];int main(){    int tt,n,k,L;    scanf("%d",&tt);    while(tt--)    {        scanf("%d%d%d",&n,&k,&L);        memset(d,0,sizeof(d));        d[0]=1;        int w=(1<<k)-1;        int tot=0;        if(L>k)        {            tot=L-k;            L=k;        }        while(n--)        {            for(int i=w;i>=0;--i)            {                if(d[i]==0)continue;                int now=d[i];                LL tmp=((LL)tot*d[i])%MOD;                for(int j=1;j<=L;++j)                {                    int sta=i|(1<<(j-1))|((i<<j)&w);                    d[sta]+=now;                    if(d[sta]>MOD)d[sta]-=MOD;                }                d[i]+=tmp;                if(d[i]>MOD)d[i]-=MOD;            }        }        int ans=0;        for(int i=0;i<=w;++i)            if((i>>(k-1))&1)            {                ans+=d[i];                if(ans>MOD)                    ans-=MOD;            }        printf("%d\n",ans);    }}

 


联系
我们