首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。