hdu 4945 2048(DP)-白红宇

hdu 4945 2048(DP)

阅读量：6402 次

发布时间：2019-06-23

本文共 2687 字，大约阅读时间需要 8 分钟。

题意：对于一个序列。能够进行这种操作：选择两个同样的数，将它们替换为它们的和。假设一个序列能够得到2048，那么就说这个序列式good的。给出一个序列，问这个序列有多少个子序列是good 的。

思路：開始卡超时卡傻了。这题时限真是太紧。还得加读写优化。

。。

事实上思路还不算难想。因为选一个子序列。因此给出的数的顺序是无用的，另外。能够发现。仅仅用形如2^i这种数才是实用的，其它数对于构成2048是没有影响的。

因此，统计一下2^i这种数有多少个，还有其它的数有多少个，那么先用前面的东西求出来的结果再乘上2^x即可了。x是其它的数的个数。用dp[i][j]表示使用前i种数，最多能得到j个2^i的序列有多少个，那么首先能够发现不使用2^i的话，dp[i][j] = dp[i-1][j/2]。

然后枚举一下使用了多少个2^i，这里不能枚举太多，让j*2^i <= 2048即可了，剩下的通过组合数算一算。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define inf 0x3f3f3f3f#define Inf 0x3FFFFFFFFFFFFFFFLL#define eps 1e-8#define pi acos(-1.0)using namespace std;typedef long long ll;const int maxn = 2048+10;const int maxm = 100000+10;const int mod = 998244353;int cnt[15],convert[maxn],mx[15];ll dp[15][maxn];ll p[maxm],pinv[maxm],pw[maxm];ll pow_mod(ll x,ll n){ ll res = 1; while(n) { if(n&1) res = res * x %mod; x = x * x %mod; n >>= 1; } return res;}ll inv(ll x){ return pow_mod(x,mod-2);}inline void Update(ll & a,ll b){ a += b; if(a >= mod) a -= mod;}inline ll C(ll n,ll m){ return p[n]*pinv[m]%mod*pinv[n-m]%mod;}void reads(int & x){ char c; bool neg=false; while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-') { neg=true; while((c=getchar())<'0'||c>'9'); } x=c-'0'; while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0'; if(neg) x=-x;}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); pw[0] = 1; for(int i = 1;i 
                
                 < maxm;++i) { p[i] = p[i-1] * i %mod; pinv[i] = inv(p[i]); } int tmp = 1; memset(convert,0,sizeof(convert)); for(int i = 1; tmp < maxn ;++i) { convert[tmp] = i; tmp *= 2; } mx[1] = 2048; mx[0] = 0; for(int i = 2;i < 15;++i) mx[i] = mx[i-1]/2; int n,tcase = 0; while(~scanf("%d",&n)) { if(n == 0) break; int a ; memset(cnt,0,sizeof(cnt)); for(int i = 0;i < n;++i) { reads(a); cnt[convert[a]]++; } ll v; ll sum; memset(dp,0,sizeof(dp)); dp[0][0] = 1; int ww; for(int i = 1;i <= 11;++i) { for(int j = 0;j <= mx[i-1];++j) Update(dp[i][j>>1],dp[i-1][j]); sum = 0; ww = min(mx[i],cnt[i]); for(int j = 1;j <= ww;++j) { v = C(cnt[i],j)%mod; Update(sum,v); for(int k = 0;k <= mx[i-1];++k) { if(dp[i-1][k]) Update(dp[i][min((k>>1)+j,mx[i])],v*dp[i-1][k]%mod); } } if(cnt[i] > mx[i]) { v = (pw[cnt[i]] - sum - 1)%mod; v = (v + mod)%mod; for(int k = 0;k <= mx[i-1];++k) Update(dp[i][mx[i]],v*dp[i-1][k]%mod); } } ll ans = 0; for(int i = 2;i <= mx[11];++i) Update(ans,dp[11][i]); if(cnt[12]) { v = pw[cnt[12]] - 1; v = v*pw[n-cnt[12]-cnt[0]]%mod; v = (v%mod + mod)%mod; Update(ans,v); } if(cnt[0]) { v =pw[cnt[0]]; ans = ans * v %mod; } ans = (ans%mod +mod) %mod; printf("Case #%d: %I64d\n",++tcase,ans); } return 0;}

转载地址：http://ghjea.baihongyu.com/

你可能感兴趣的文章

51单机片编译hex_单片机爬坑记-05-编译环境（完）