HDU 4945 2048（dp）

题意：给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 = 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 998244353

ll 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
",ans);
    }
    return 0;
}