BSOJ4836 -- 【模拟试题】篮球比赛 hzwer noip模拟赛

BSOJ4836 -- 【模拟试题】篮球比赛   Description 由于Czhou举行了众多noip模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。 而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当天状态从中选出若干名选手，使他们的能力值和等于k。 Input 一行三个数n,k,l。表示机房有n个神牛，选出队员能力值和为k，每个神牛的能力最大值<=L且>=0。 Output 输出一个数，表示方案数，方案满足选出若干选手使能力和为k。因为答案比较大，最后模10^9+7。 Sample Input 2 2 2 Sample Output 6 Hint 【样例说明】神牛的能力值可能为(0,2)(1,2)(1,1)(2,0)(2,1)(2,2)，这样都可以选出一些数字使他们的能力值和为2。 对于（0,2）表示第一只牛能力值为0，第二只牛能力为2 类似的 对于（1,2）选出2即满足要求。 对于（1,1）选出全部选手即满足要求。 所以（0,2）（1，1）都是满足要求的方案。 数据范围： n,k<=20 ,0<=L<=10^9.
来自hzwer的某次noip模拟赛 对于小数据，我们可以考虑直接暴力枚举最后用01背包判断k能否达到。 而想要过100%的数据，我们考虑使用状压DP 定义f[i][j]表示在第i位状态（盘面）为j，用j的二进制来表示某个数能否取到（从1到k） 再试对代码进行分析
#include<iostream>#include<iomanip>#include<cstring>#include<cmath>#include<cstdio>#define mod 1000000007using namespace std;int f[25][1050000],n,k,l;long long ans;int main(){    cin>>n>>k>>l;    int ed=(1<<k)-1;                         //局面总数    for(int i=1;i<=min(l,k);i++)      f[1][1<<(i-1)]=1;                      //初始化，因为是从当前推以后，所以要预处理使用第一个人的局面下的方案数    if(k<=l)      f[1][0]=l-k+1;                         //0表示取不到的，l-k+1就是高于l的那些值都不能取，各算方案    for(int i=1;i<=n-1;i++)    {        f[i][0]=max(f[i][0],1);              //至少有0        for(int j=0;j<=ed;j++)          if(f[i][j])            {                for(int x=0;x<=min(l,k);x++)                {                    int to=((j<<x)|j|(1<<(x-1)))&ed;             //j<<x表示在j中放入x，j表示j本身，1<<(x-1)表示加入x本身                    f[i+1][to]=(f[i+1][to]+f[i][j])%mod;                }                if(k<=l)                  f[i+1][j]=(f[i+1][j]%mod+(long long)f[i][j]*(l-k)%mod)%mod; // 比k高，可以不选，但是仍然算方案数            }    }
    for(int i=0;i<=ed;i++)      if(i&(1<<(k-1)))                                             //取出第k位看是否为1，若为1就表示可以        ans=(ans%mod+f[n][i]%mod)%mod;    cout<<ans;    return 0;}
//from 07 xioooooooooooooo#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<algorithm>#define mod 1000000007typedef long long ll;using namespace std;int n,k,l,t,stan,note[27]={0},f[23][1550007]={0};/*note记 (l+1)的i次幂  f是搜索备忘录.f[i][j]的j表示vis数组状态压缩后的数字。f[i][j]记当计算到第i个人状态为j时能够取到的值的的方案数。*/int dfs(int v,int ff)//v表示第几个人，ff表示当前能得到的值的状态{    if(f[v][ff]!=-1) return f[v][ff];//取备忘录    if(ff&t) return f[v][ff]=note[n-v+1];    /*如果此时已经可以取到k，则后面的人无论取多少都可以      后面的人取0~l的方案数为(l+1)的后面的人数(n-v+1)次方     */    if(v==n+1) return f[v][ff]=(ff&t);//边界    int ans=0;    long long temp;    //用long long 临时存储，避免乘爆同时也避免冗长复杂的 long long强转    for(int i=0;i<=min(k,l);i++)//枚举第v个人的取值    {        temp=((ll)dfs(v+1,(ff|(ff<<i))&stan))%mod;        //ff左移得到用当前取值计算后的状态与当前状态取与得到新状态        //和stan取与防止左移后超出n的范围        ans=(ans+temp)%mod;    }    if(l>k)    {        temp=(((ll)((ll)dfs(v+1,ff)%mod*(ll)(l-k))%mod))%mod;        //如果当前的人取值大于k就一定不会做出贡献，对后面的状态的影响是等价的        //所以直接计算一次再乘以(l-k)        ans=(ans+temp)%mod;//返回    }    return f[v][ff]=ans%mod;}int main(){    scanf("%d%d%d",&n,&k,&l);//输入    memset(f,-1,sizeof(f));//备忘录初始化    note[0]=1;    for(int i=1;i<=n;i++) note[i]=(ll)((ll)note[i-1]*(ll)(l+1))%mod;    //递推计算(l+1)的i次方    t=(1<<k);//取与判断是否能得到k的标准    stan=(1<<(k+1))-1;//用于去与防止左移后 超出n的范围 的标准    printf("%d\n",dfs(1,1)%mod);    return 0;}//2 2 2  ans:6//10 10 5  ans:60293642
//from zy#include<iostream>#include<cstdio>#include<cstring>using namespace std;long long n,m,k,i,j,l,r,f[2100000],g[2100000],ans;//防止MLE，使用滚动数组int main(){cin>>n>>m>>k;r=1<<(m+1);f[1]=1;//第一位（1<<0）表示可以取0,1<<i表示可以取ifor(i=1;i<=n;i++){    for(l=1;l<r;l++) g[l]=(f[l]*max(0ll,k-m))%1000000007;//第i个数为0或大于和    for(l=1;l<r;l++)       if(f[l])//l状态为有效状态          for(j=0;j<=min(m,k);j++)//枚举各个有效数字              g[(l|(l<<j))%r]=(g[(l|(l<<j))%r]+f[l])%1000000007;//第i个数为j        memcpy(f,g,sizeof(f));//拷贝    }    for(i=(1<<m);i<r;i++) ans=(ans+f[i])%1000000007;//对所有可以组成指定和的状态求和    cout<<ans;    return 0;}