首页 > 代码库 > HDU 4945 2048 DP 组合
HDU 4945 2048 DP 组合
思路:
这个题写了一个背包的解法,超时了。搜了下题解才发现我根本不会做。
思路参见这个:
其实我们可以这样来考虑,求补集,用全集减掉不能组成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 }
HDU 4945 2048 DP 组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。