首页 > 代码库 > HDU 4945 2048（dp）

HDU 4945 2048（dp）

2024-07-17 21:29:48   220人阅读

题意：给n（n<=100,000）个数，0<=a[i]<=2048 。一个好的集合要满足，集合内的数可以根据2048的合并规则合并成2048 。输出好的集合的个数%998244353 。

 

比赛的时候想着1跟3可以合并成4 。。。。然后就越搞越复杂了。。。。。2048玩得不多的我没有透彻的合并规则概念。。。。。

看了题解写了发，妥妥地TLE...本地随意n=100,000都TLE了。。。

用dp[i][j]表示当前 i个2^j 的方案数

然后队友提醒优化，就是，当枚举到比如，value = http://www.mamicode.com/2^j 当value是2048的时候，i>=1的都压到1那里去，类似于此。（第45行、第52行）

然后就快很多了，本地那些数据每个case都卡顿一下就出来了。。。提交。还是TLE.....

然后再改一改剪枝，就是压的那一部分可以直接压。（第55-60行）

终于AC....1015ms。。。泪牛满面。。。。

 

#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define ll long long#define maxn 100010#define mod 998244353ll qmod(ll a,ll n){    ll ret=1;    while(n){        if(n&1) ret=ret*a%mod;        a=a*a%mod;        n>>=1;    }    return ret;}ll nn[maxn],mm[maxn];ll C(int n,int m){    return nn[n]*mm[m]%mod*mm[n-m]%mod;}int cnt[2055];ll dp[2055][12];int ma[12];int main(){    nn[0]=mm[0]=1;    for(int i=1;i<maxn;++i) nn[i]=nn[i-1]*i%mod, mm[i]=qmod(nn[i],mod-2);    ma[11]=1;    for(int i=10;i>=0;--i)ma[i]=ma[i+1]*2;    int ca=0;    int n;    while(~scanf("%d",&n) && n){        printf("Case #%d: ",++ca);        for(int i=0;i<=11;++i) cnt[1<<i]=0;        int oth=0;        for(int i=0;i<n;++i){            int tmp; scanf("%d",&tmp);            if((tmp&(-tmp))==tmp && tmp) ++cnt[tmp];            else ++oth;        }        memset(dp,0,sizeof(dp));        dp[0][0] = 1;        for(int j=0;j<11;++j){            for(int i=0;i<=ma[j];++i){                if(dp[i][j]==0) continue;                int sumc=0;                for(int k=0;k<=cnt[1<<j];++k){                    int cc=C(cnt[1<<j],k);                    sumc+=cc;                    if(sumc>=mod) sumc-=mod;                    int ik2=min( (i+k)/2, ma[j+1] );                    dp[ik2][j+1]+=dp[i][j]*cc%mod;                    if(dp[ik2][j+1]>=mod) dp[ik2][j+1]-=mod;                    if(ik2==ma[j+1]){                        int ccc = qmod(2,cnt[1<<j]) - sumc;                        if(ccc<mod) ccc+=mod;                        dp[ik2][j+1]+=dp[i][j]*ccc%mod;                        if(dp[ik2][j+1]>=mod) dp[ik2][j+1]-=mod;                        break;                    }                }            }        }        ll ans=dp[1][11];        ans = ans*qmod(2,oth)%mod + ( cnt[2048]?  (qmod(2,cnt[2048])-1+mod)%mod*qmod(2,n-cnt[2048])%mod  :  0 );        if(ans>=mod) ans-=mod;        printf("%I64d\n",ans);    }    return 0;}

　　


联系
我们