首页 > 代码库 > bzoj 3851: 2048 dp优化
bzoj 3851: 2048 dp优化
3851: 2048
Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 22 Solved: 9
[Submit][Status]
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
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
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.
sro卡常数orz。。。。。。
题解什么的可以参见hdu4945，我用的是组合数，逆元什么的，具体来说，只有2^i的数是有用的（这个地方有点坑，如果用x==x&(-x)判定，则会把0算进去）然后我是枚举每一个数x选了多少个，顶多2048/x个，用组合数优化背包。但是这个办法还是很慢，经过面目全非的常数优化，八中2500ms过的，hdu就根本过不了了。
这个方法实在太渣，优化后卡时过的，童鞋们最好用其他方法额。
顺便总结一下这道题用的常数优化技巧：
- register 这次我实践证明register是有作用的
- [2][n]的二维数组改成两个数组。
- 数组下标索引改成指针。
- 如果会多次调用几个数的乘积，可以提前预处理出来。
- 改变for语句嵌套顺序，省略for内部的条件判断。
- 读入优化x*10可改成 (x<<3)+(x<<2)
- 少用取模才是终极目标。
/************************************************************** Problem: 3851 User: mhy12345 Language: C++ Result: Accepted Time:2520 ms Memory:17536 kb****************************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MOD 998244353#define MAXN 510000#define deal(x,y) \ (x)=((x)+(y))%MOD;inline int nextInt(){ register int x=0; register char ch; while (ch=getchar(),ch<‘0‘ || ch>‘9‘); while (x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x;}const int mod=MOD;typedef long long qword;qword pow_mod(qword x,qword y){ qword ret=1; while (y) { if (y&1)ret=ret*x%MOD; x=x*x%MOD; y>>=1; } return ret;}qword dp[20][2049];qword fact[MAXN];int tot[2049];qword inv[MAXN];qword val[MAXN];pair<int,int> pl[MAXN];int topp=-1;int main(){ //freopen("input.txt","r",stdin); register int i,j,k,k2; int x,y,z,n,m; int nn; fact[0]=1; for (i=1;i<MAXN;i++) fact[i]=fact[i-1]*i%MOD; inv[0]=1; for (i=0;i<MAXN;i++) inv[i]=pow_mod(fact[i],MOD-2); int cnt=0; register qword *dp1,*dp2; register qword a=0; while (scanf("%d",&n),cnt++,n) { printf("Case #%d: ",cnt); memset(dp[0],0,sizeof(dp[0])); memset(tot,0,sizeof(tot)); dp[0][0]=1; for (i=1;i<=n;i++) { x=nextInt(); tot[x]++; } int ttr=0; for (i=0;i<=2048;i++) if (!i || i!=(i&(-i))) ttr+=tot[i]; int cnt=0; bool flag=false; for (i=1;i<=2048;i<<=1,cnt^=flag) { memset(dp[cnt^1],0,sizeof(dp[cnt^1])); dp1=dp[cnt]; dp2=dp[cnt^1]; flag=false; if (!tot[i])continue; flag=true; for (j=0;j<=tot[i];j++) val[j]=*(fact+*(tot+i)) * *(inv+j)%MOD * *(inv+tot[i]-j)%MOD; for (a=0,j=2048/i+(2048%i!=0);j<=tot[i];j++) a=(a+ * (val+j))%MOD; for (k=2048;k>=0;k--) if (dp1[k]) { for (j=0,k2=k;j<=tot[i] && k2<2048;j++,k2+=i) deal(dp2[k2],*(dp1+k) * *(val+j)); qword &b=dp2[2048]; k2-=k; for (;k2<2048 && j<=tot[i];j++,k2+=i) deal(b,*(dp1+k)* *(val+j)); if (j<=tot[i]) deal(b,*(dp1+k)*a); } } printf("%lld\n",dp[cnt][2048]*pow_mod(2,ttr)%MOD); }}
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MOD 998244353#define MAXN 510000#define deal(x,y) \ (x)=((x)+(y))%MOD;inline int nextInt(){ register int x=0; register char ch; while (ch=getchar(),ch<‘0‘ || ch>‘9‘); while (x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x;}const int mod=MOD;typedef long long qword;qword pow_mod(qword x,qword y){ qword ret=1; while (y) { if (y&1)ret=ret*x%MOD; x=x*x%MOD; y>>=1; } return ret;}qword dp[2][2049];qword fact[MAXN];int tot[2049];qword inv[2049];pair<int,int> pl[MAXN];int topp=-1;int main(){ freopen("input.txt","r",stdin); int i,j,k,x,y,z,n,m; int k2; int nn; fact[0]=1; for (i=1;i<MAXN;i++) fact[i]=fact[i-1]*i%MOD; inv[0]=1; for (i=0;i<MAXN;i++) inv[i]=pow_mod(fact[i],MOD-2); int a1,a2; int cnt=0; while (scanf("%d",&n),cnt++,n) { printf("Case #%d: ",cnt); memset(dp,0,sizeof(dp)); memset(tot,0,sizeof(tot)); dp[0][0]=1; for (i=1;i<=n;i++) { x=nextInt(); tot[x]++; } int ttr=0; for (i=0;i<=2048;i++) if (!i || i!=(i&(-i))) ttr+=tot[i]; int cnt=0; bool flag=false; for (i=1;i<=2048;i<<=1,cnt^=flag) { memset(dp[cnt^1],0,sizeof(dp[cnt^1])); flag=false; if (!tot[i])continue; flag=true; qword a=0; for (j=2048/i+(2048%i!=0);j<=tot[i];j++) a=(a+inv[j]*inv[tot[i]-j])%MOD; a=a*fact[tot[i]]%MOD; for (k=2048;k>=0;k--) if (dp[cnt][k]) { for (j=0,k2=k;j<=tot[i] && k2<2048;j++,k2+=i) deal(dp[cnt^1][k2],dp[cnt][k]*fact[tot[i]]%MOD*inv[j]%MOD*inv[tot[i]-j]); qword &b=dp[cnt^1][2048]; k2-=k; for (;k2<2048 && j<=tot[i];j++,k2+=i) deal(b,dp[cnt][k]*fact[tot[i]]%MOD*inv[j]%MOD*inv[tot[i]-j]); if (j<=tot[i]) deal(dp[cnt^1][2048],dp[cnt][k]*a); } } printf("%lld\n",dp[cnt][2048]*pow_mod(2,ttr)%MOD); }}
bzoj 3851: 2048 dp优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。