HDU 4945 2048
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 590 Accepted Submission(s): 136
Problem Description
Teacher Mai is addicted to game 2048\. But finally he finds it's too hard to get 2048\. So he wants to change the rule:
You are given some numbers. Every time you can choose two numbers of the same value from them and merge these two numbers into their sum. And these two numbers disappear meanwhile.
If we can get 2048 from a set of numbers with this operation, Teacher Mai think this multiset is good.
You have n numbers, A1,...,An. Teacher Mai ask you how many subsequences of A are good.
The number can be very large, just output the number modulo 998244353.
Input
There are multiple test cases, terminated by a line "0".
For each test case, the first line contains an integer n (1<=n<=10^5), the next line contains n integers ai (0<=ai<=2048).
Output
For each test case, output one line "Case #k: ans", where k is the case number counting from 1, ans is the number module 998244353.
Sample Input
4 1024 512 256 256 4 1024 1024 1024 1024 5 1024 512 512 512 1 0
Sample Output
Case #1: 1 Case #2: 11 Case #3: 8
_Hint_
In the first case, we should choose all the numbers. In the second case, all the subsequences which contain more than one number are good.
Source
[ 2014 Multi-University Training Contest 8 ](http://acm.hdu.edu.cn/search.php?field=problem&key=2014%20Multi-University%20Training%20Contest%208&source=1&searchmode=source)
Recommend
hujie | We have carefully selected several similar problems for you: [4955](http://acm.hdu.edu.cn/showproblem.php?pid=4955) [4954](http://acm.hdu.edu.cn/showproblem.php?pid=4954) [4953](http://acm.hdu.edu.cn/showproblem.php?pid=4953) [4952](http://acm.hdu.edu.cn/showproblem.php?pid=4952) [4951](http://acm.hdu.edu.cn/showproblem.php?pid=4951)
貌似这几天第一次做的DP题啊。想象一下二进制就能明白——当子序列的2次幂数字之和大于等于2048时这个序列就是good序列了。正面dp要dp出2048~100000肯定要超时，而反面dp只需要dp出0~2047就够了。复杂度大大降低O（11＊2048*2048）。
标程写的很厉害！尤其是逆元的处理！
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cassert>
#include<utility>
#include<numeric>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define pr pair
#define PR pair<int,int>
#define MP make_pair
#define SI(x) set<x>::iterator
#define VI(x) vector<x>::iterator
#define MI(x,y) map<x,y>::iterator
#define SRI(x) set<x>::reverse_iterator
#define VRI(x) vector<x>::reverse_iterator
#define MRI(x,y) map<x,y>::reverse_iterator
#define F first
#define S second
#define Sz(x) (int)x.size()
#define clrQ(x) while(!x.empty)x.pop();
#define clr(x,y) memset(x,y,sizeof(x));
#if defined (_WIN32) || defined (__WIN32) || defined (WIN32) || defined (__WIN32__)
#define LL __int64
#define LLS "%" "I" "6" "4" "d"
#define LLU "%" "I" "6" "4" "u"
#define LL_MAX _I64_MAX
#else
#define LL long long
#define LLS "%" "l" "l" "d"
#define LLU "%" "l" "l" "u"
#define LL_MAX _I64_MAX
#endif
const int inf = ~0u >> 1;
const LL lnf = ~0ull >> 1;
/*start*/
#define MOD 998244353
int cnt[3010];
LL f[101000], g[101000];
int pn, n, __;
int dp[13][1025]; //表示取了2^0、2^1、2^2、……、2^i种元素，总和加起来等于j*2^(i+1)的所有情况
inline int getint() {
int ret = 0;
bool ok = 0;
for (;;) {
int c = getchar();
if (c >= '0' && c <= '9') ret = (ret << 3) + ret + ret + c - '0', ok = 1;
else if (ok) return ret;
}
}
inline LL powmod(LL b, int x) {
LL res = 1;
for (b %= MOD; x; x >>= 1) {
if (x & 1) res = res * b % MOD;
b = b * b % MOD;
}
return res;
}
int main(int argc, char **argv) {
f[0] = 1;
for (int i = 1; i <= 100000; i++)
f[i] = f[i - 1] * i % MOD;
g[100000] = powmod(f[100000], MOD - 2);
for (int i = 99999; i >= 0; i--)
g[i] = g[i + 1] * (i + 1) % MOD;
while (1) {
n = getint();
if (n == 0) break;
for (int k = 1; k <= 2048; k <<= 1)
cnt[k] = 0;
for (int i = 0; i < n; i++) {
cnt[getint()]++;
}
pn = 0;
for (int k = 1; k <= 2048; k <<= 1)
pn += cnt[k];
for (int i = 0, m = 1024; i <= 11; i++, m >>= 1) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
int ct = cnt[1];
LL cof = f[ct];
for (int i = 0; i <= ct && i < 2048; i++) {
dp[0][i >> 1] += g[ct - i] * g[i] % MOD;
if (dp[0][i >> 1] > MOD) dp[0][i >> 1] -= MOD;
}
for (int i = 1, m = 1024; i <= 11; i++, m >>= 1) {
ct = cnt[1 << i];
cof = cof * f[ct] % MOD;
for (int j = 0; j < m; j++) {
if (dp[i - 1][j]) {
for (int k = 0; k <= ct && j + k < m; k++) {//不要把满足good的序列转移上去。
dp[i][(j + k) >> 1] += dp[i - 1][j] * g[k] % MOD * g[ct - k] % MOD;
if (dp[i][(j + k) >> 1] > MOD) dp[i][(j + k) >> 1] -= MOD;
}
}
}
}
int ans = (powmod(2, pn) - dp[11][0] * cof) % MOD
* powmod(2, n - pn)%MOD;
if (ans < 0) ans += MOD;
printf("Case #%d: %d\n", ++__, ans);
}
}