首页 > 代码库 > HDU4945 2048(dp)

HDU4945 2048(dp)

先是看错题意。。然后知道题意之后写了发dp..无限TLE..实在是不知道怎么优化了,跑了遍数据是对的,就当作理论AC掉好了。。

#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <queue>#include <algorithm>#include <cmath>#include <ctime>using namespace std;#define ll long long#define maxn 120000#define mod 998244353ll mod_pow(ll a, ll n){	ll ret = 1;	while (n){		if (n & 1) ret = ret*a%mod;		a = a*a%mod;		n >>= 1;	}	return ret;}ll fac[maxn];ll fac_inv[maxn];int cnt[2500];int dp[13][2500];int two[13] = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 };int two_com[13] = { 0, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1 };int n;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 comb(int n, int m){	return fac[n] * fac_inv[m] % mod*fac_inv[n - m] % mod;}inline void add(int &a, int b){	a += b;	if (a >= mod) a -= mod;}int main(){	//freopen("1001.in", "r", stdin);	//freopen("out.txt", "w", stdout);	//double t1 = clock();	fac[0] = fac_inv[0] = 1;	for (int i = 1; i <= 100000; ++i){		fac[i] = fac[i - 1] * i%mod;	}	fac_inv[100000] = mod_pow(fac[100000], mod - 2);	for (int i = 99999; i >= 0; --i){		fac_inv[i] = fac_inv[i + 1] * (i + 1) % mod;	}	int ca = 0;	while (~scanf("%d", &n) && n){		for (int i = 1; i <= 12; ++i) cnt[two[i]] = 0;		int tmp;		for (int i = 0; i < n; ++i) {			tmp = getint();			cnt[tmp]++;		}		int pn = 0;		for (int i = 1; i <= 12; ++i) pn += cnt[two[i]];		memset(dp, 0, sizeof(dp)); dp[0][0] = 1;		ll sum,cb;		for (int i = 1; i <= 12; ++i){			int num = cnt[two[i]];			for (int j = 0; j <= two_com[i - 1]; ++j){				sum = 0;				int k;				for (k = 0; (j >> 1) + k <= two_com[i] && k <= num; ++k){					cb = comb(num, k);					sum = sum + cb; if (sum >= mod) sum -= mod;					add(dp[i][(j >> 1) + k], dp[i - 1][j] * cb%mod);				}				if ((j >> 1) + num > two_com[i]){					ll res = ((mod_pow(2, num) - sum) % mod + mod) % mod;					add(dp[i][two_com[i]], res*dp[i - 1][j] % mod);				}			}		}		ll ans = dp[12][1] * mod_pow(2, n - pn) % mod;		printf("Case #%d: %I64d\n", ++ca, ans);	}	//double t2 = clock();	//cout << t2 - t1 << endl;	return 0;}