[hdu4906]Our happy ending

发布于 2018-09-21  316 次阅读


题目大意

给定序列a_1,a_2,...,a_n,如果我们可以取其中的一些(每个a_i只能使用一次),并且它们总和为k,那么我们说这个序列是一个好的序列。
有多少好的序列?假设每个a_i是一个整数且0 <= a_i <= L.
您应该输出模10 ^ 9 + 7的结果。

数据范围 T<=20, n,k<=20 , 0<=L<=10^9.

发现数据范围很小,考虑数位dp
数位dp??? 不可做,没法记状态。
那我就状压,
设dp[i][j]表示考虑到第i个数,已经选的数能组成数的集合为j时的方案数。

j在二进制下第k为1表示能组成k。

考虑转移。
显然我需要枚举第i位选哪个数。
然而他说使和为k,
所以我选比k大的数是没意义的。
但是也是一种方案。
所以我们可以记l=min(l,k);
然后算出if(l>k) cha=l-k;差值。
然后就是对于第i位选择1到K中的数。
假设是x。
那么 dp[i-1][j]->dp[i][nxt];
int nxt=st&(j|(j<<x))|(1<<x);(st表示全集)

最后统计答案,只要有第k位是1就符合。
注意要滚动数组滚掉第一维。
提供一组hack数据
1
1 0 1
答案:2
能hack掉网上大部分题解。

#include <cstdio>
#include <algorithm>
#include <cstring>

//#define int long long
using namespace std;
const int mod=1e9+7;

int n,k,l;
int T;
long long dp[(1<<21)+5];
int st,cha;
long long ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d%d%d",&n,&k,&l);memset(dp,0,sizeof dp);
        cha=l-k;
        if(cha<0) cha=0;
        l=min(l,k);
        st=(1<<(k+1))-1;dp[1]=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=st;j>0;--j)
            {
                if(dp[j]==0) continue;
                long long tmd=dp[j];
                for(int x=1;x<=l;++x)
                {
                    int nxt=st&(j|(j<<x))|(1<<x);
                    dp[nxt]+=tmd;
                    if(dp[nxt]>=mod) dp[nxt]-=mod;
                }
            //  printf("dp[%d]=%d\n",j,dp[j]);
                if(cha){dp[j]=dp[j]+tmd*cha;dp[j]%=mod;}
            }
        }
        for(int i=1<<k;i<=st;++i) 
        {
            ans+=dp[i];
            if(ans>=mod) ans-=mod;
        }
        printf("%lld\n",ans);
    }
}


0.00 avg. rating (0% score) - 0 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。