laekov

BZOJ3851 2048

题号是3851,题目名称是2048。


比较厉害的DP。最初没有想到怎么表示状态。其实就是一个≤2048的自然数就可以表示状态了。


然后转移不能一个一个来,每个值要一起来, 然后拿组合数来算。然后就行了。


虽然hdu上还是过不到。好慢的说。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


#define _l (long long int)


const int maxn = 100009;

const int mod = 998244353;


int n, f[2][2051], c[2051];

int fac[maxn], finv[maxn], p2[maxn];


int modPow(int a, int x) {

int s(1);

for (; x; x >>= 1, a = _l a * a % mod)

if (x & 1)

s = _l s * a % mod;

return s;

}


void pre() {

fac[0] = 1;

finv[0] = 1;

p2[0] = 1;

for (int i = 1; i < maxn; ++ i) {

fac[i] = _l fac[i - 1] * i % mod;

finv[i] = modPow(fac[i], mod - 2);

p2[i] = _l p2[i - 1] * 2 % mod;

}

}


inline int comb(int n, int m) {

return _l fac[n] * finv[m] % mod * finv[n - m] % mod;

}


inline void incm(int& a, int x) {

a += x;

if (a >= mod)

a %= mod;

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


int tc = 0;

pre();

while (scanf("%d", &n) ^ EOF) {

if (!n)

break;

int cn = 0, cur = 0, prv = 1;

memset(f, 0, sizeof(f));

memset(c, 0, sizeof(c));

for (int i = 0; i < n; ++ i) {

int a;

scanf("%d", &a);

if ((a & -a) == a && a >= 1)

++ c[a];

else

++ cn;

}

f[cur][0] = 1;

for (int i = 1; i <= 2048; i <<= 1)

if (c[i]) {

swap(cur, prv);

for (int j = 0; j <= 2048; ++ j)

f[cur][j] = f[prv][j];

int tc = (p2[c[i]] - 1 + mod) % mod;

for (int j = 1; j <= c[i] && j * i < 2048; ++ j) {

int cc = comb(c[i], j);

for (int k = 0; k <= 2048; ++ k)

if (f[prv][k])

incm(f[cur][min(k + j * i, 2048)], _l f[prv][k] * cc % mod);

tc = (tc + mod - cc) % mod;

}

for (int k = 0; k <= 2048; ++ k)

if (f[prv][k])

incm(f[cur][2048], _l f[prv][k] * tc % mod);

}

printf("Case #%d: %d\n", ++ tc, (int)(_l f[cur][2048] * p2[cn] % mod));

}

}


评论

© laekov | Powered by LOFTER