首页 > 代码库 > HDU 4945 2048 DP 组合

HDU 4945 2048 DP 组合

2024-08-01 05:00:31   212人阅读

思路：

　　这个题写了一个背包的解法，超时了。搜了下题解才发现我根本不会做。

　　思路参见这个：

　　其实我们可以这样来考虑，求补集，用全集减掉不能组成2048的集合就是答案了。

　　因为只要达到2048就可以了，所以求补集会大大减小枚举的次数。

代码：

　　

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 typedef __int64 ll;20 21 const int INF = 1<<30;22 const int MAXN = 1e5+55;23 const int MAXM = 2055;24 const ll MOD = 998244353;25 26 int cnt[MAXM];27 ll dp[20][MAXM];28 ll fact[MAXN], inv[MAXN];29 int n;30 31 ll myPow(ll x, int d) {32     ll res = 1;33     while (d>0) {34         if (d&1) res = (res*x)%MOD;35         x = (x*x)%MOD;36         d >>= 1;37     }38     return res;39 }40 41 inline ll C(int x, int y) {42     return ((fact[x]*inv[y])%MOD * inv[x-y])%MOD;43 }44 45 inline int lowBit(int x) {46     return x&(-x);47 }48 49 void solve() {50     int sum = n;51     for (int i = 0; i < 12; i++) sum -= cnt[1<<i];52 53     memset(dp, 0, sizeof(dp));54 55     for (int j = min(2048, cnt[1]); j >= 0; j--) dp[0][j] = C(cnt[1], j);56 57     for (int i = 1; i < 12; i++) {58         int cc = 2048>>i;59         for (int k = min(cc, cnt[1<<i]); k >= 0; k--) { //选k个60             ll CC = C(cnt[1<<i], k);61             for (int j = k; j <= cc; j++) { //62                 dp[i][j] = (dp[i][j] + (((dp[i-1][(j-k)<<1]+dp[i-1][(j-k)<<1|1])%MOD)*CC)%MOD )%MOD;63             }64         }65     }66 67     ll ans = ((myPow(2, n-sum)-dp[11][0])%MOD+MOD)%MOD;68     ans = (ans*myPow(2, sum))%MOD;69     printf("%I64d\n", ans);70 }71 72 int main() {73     #ifdef Phantom0174         freopen("HDU4945.txt", "r", stdin);75     #endif //Phantom0176 77     fact[0] = 1;78     for (int i = 1; i < MAXN; i++) fact[i] = (fact[i-1]*i)%MOD;79     inv[MAXN-1] = myPow(fact[MAXN-1], MOD-2);80     for (int i = MAXN-1; i > 0; i--) inv[i-1] = (inv[i]*i)%MOD;81 82     int T = 1;83 84     while (scanf("%d", &n)!=EOF && n!=0) {85         printf("Case #%d: ", T++);86         memset(cnt, 0, sizeof(cnt));87         int x;88         for (int i = 0; i < n; i++) {89             scanf("%d", &x);90             cnt[x]++;91         }92         solve();93     }94 95     return 0;96 }
View Code

 

HDU 4945 2048 DP 组合


联系
我们