考场上一个DFS优化乱加就对了一个无解的点
题目描述
给定一个长度为 n 的数列，在这个数列中选取一个子序列使得这个子序列中的数能合出2048
对于合并操作，可以选择这个序列中的任意两个数进行合并，当然这两个数必须是相同的(即2个x合并后成为一个2x)
对于每个序列，只要进行若干次合并操作后，这个序列中至少有一个2048(可以有其他数剩余)，就称这个序列是合法的
我们可以认为只要选取的数在原数列中的位置不同，这些序列就是不同的
对于给定的数列，小朋友们需要算出有多少子序列是合法的，并把这个数 对 998244353 取模
输入格式
第一行一个正整数n表示数列长度。
第二行 n 个数 Ai，表示这个数列。
输出格式
输出一行，为序列数模 998244353 后的值。
一些说明与提示
与原版2048不同，这个数列中的数可以是2048以内的任意正整数。
998244353=119×2^23+1，与本题的解题无关。
数据规模与约定
40%的数据，n≤20
70%的数据， n≤500
100%的数据， n≤100000,1≤Ai≤2048
时间限制：1s
空间限制：256MB
题目分析
首先在题意里显然的是，只有2的幂次数能够最终合并出2048。
那么自然先考虑纯粹的dfs。
裸的DFS
枚举出一种方案之后只需要将所有是2的幂的数加起来，如果合法则和必定大于2048（有些单个无法合并的并不造成影响，因为它们既然合并不了（个数为奇数个）那么加上去就不会大于2048）
优化的DFS
1.把a[]从大到小排序，dfs时候先枚举选当前数
2.dfs时如果check()已经合法，那么显然的，后面的x个数无论怎么选都一定符合条件。
可以发现存在这个恒等式，于是直接加上
即可（当然要快速幂或者事先打好一个表。要知道直接右移100000位会炸到哪里去都不知道）
3.测试数据会发现，在最后的几个数（通常为0或1）dfs时，会因sum为2046/2047这样的东西被卡很久。那么我们维护对2的幂次维护一个后缀和，加判断 if sum+suffix[now]< return 意即如果后面全部数选上，都还达不到2048那就一定不合法了。
#include<bits/stdc++.h>
using namespace std;
int n,nx,a[],tr,tot;
long long ans,suf[],m2[],ss;
bool vis[];
set<int>f;
const int MO = ;
int read()
{
char ch = getchar();int num = ;
while (ch<''||ch>'')ch = getchar();
while (ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return num;
}
bool cmp(int a, int b)
{
return a>b;
}
bool check() //原始的check
{
tot = ;
int ax[],x,y,z;
memset(ax, , sizeof(ax));
register int i;
//a1:1 a2:2 a3:4 a4:8 a5:16 a6:32 a7:64 a8:128 a9:256 a10:512 a11:1024
for (i=; i<=n; i++)
if (vis[i])
{
x = a[i];
if (x==)return ;
if (x==||x==||x==||x==||x==||x==||x==||x==||x==||x==||x==){
y = x;z = ;
while (y!=){y>>=;++z;}
ax[z]++;
}
}
for (i=; i<=; i++)
ax[i+] += ax[i]/;
if (ax[])return ;
return ;
}
bool new_check() //略有升级的check
{
int cnt = ;
for (int i=; i<=n; i++)
if (vis[i] && f.count(a[i]))
cnt+=a[i];
return cnt>=;
}
void search(int now, int sum) //check 是O(n)的，浪费很多。直接保存sum每次传递
{
if (now==n+)
{if (sum>=){ans++;if (ans>=MO)ans-=MO;}return;}
if (sum>=){
ans += m2[n-now+];
if (ans>=MO)ans-=MO;
return;
}
if (sum+suf[now]<)return;
vis[now] = ;
if (f.count(a[now]))
search(now+, sum+a[now]);
else search(now+, sum);
vis[now] = ;
search(now+, sum);
}
int main()
{
register int i,j;
for (int i=; i<=; i++)
f.insert(<<i);
memset(vis, , sizeof(vis));
n = read();nx = ;
for (i=; i<=n; i++)
{
tr = read();
a[++nx] = tr;
}
n = nx;
sort(a+, a+n+, cmp);
m2[] = ;
for (int i=; i<=n; i++)
m2[i] = m2[i-]*%MO;
for (i=n; i>=; i--)
if (f.count(a[i]))
suf[i] = suf[i+]+a[i];
search(, );
printf("%lld\n",ans);
return ;
}
嗯这样优化之后就可以过5个点（不过还有四个点WA，最后的点TLE?这不是幂数模数的问题，玄学）
假的DFS优化
像我这样在读入的时候只读2的幂次数的人已经不多了
数学考虑
既然我们都已经在dfs优化中想到：如何计算一个集合元素为n的所有子集个数。
我们再往dp靠一靠就可以得到一个比标算的代码复杂度还要少的算法了。先贴上：
#include<bits/stdc++.h>
using namespace std;
const int maxx = ;
const int MO = ;
int read()
{
char ch = getchar();int num;
for (num = ; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar())num = (num<<)+(num<<)+ch-;
return num;
}
long long qmi(long long a, long long b)//快速幂
{
long long ret = , xx = a;
for(;;)
{
if (b&)ret=(xx*ret)%MO;
if (b>>=)xx=(xx*xx)%MO;
else break;
}
return ret;
}
int n,m,x;
long long f[],ss;
int main()
{
n = read();
f[] = ;
for (int i=; i<=n; i++)
{
x = read();
if (x & (x-))continue; //判断是否为2的幂次
m++;
for (int j=maxx-; j>=x; j--)
f[j] = (f[j]+f[j-x])%MO;
}
for (int i=; i<maxx; i++)
ss = (f[i]+ss)%MO;
printf("%lld\n",(qmi(, m)-ss+MO)%MO*qmi(, n-m)%MO);
return ;
}
我们先算出有2的幂次数m个
记m个数共可以表示出方案数a
记m个数可表示出小于2048的数的方案为b
显然这m个数可表示出大于等于2048的方案数即a-b，就是上述的 (qmi(, m)-ss+MO)%MO ，至于在模之前加上MO是因为这个qmi()和ss取模过，故不能保证取模后依然qmi()>ss
后面的 *qmi(, n-m)%MO 就是乘上对答案无关的方案数。
至此，我们用41行就跑过了这题……
标算
最后贴一发标算
一个子序列或者说子集合法的条件是：只要二的次幂的和 不小于 2048 即可
可以想象，二进制加法即2048合并的过程
转化为用DP统计有多少子集的和不小于 2048 ，很简单的一个背包问题
大概大佬都是这样简洁的“很简单的xx问题”的吧
不过好像现在做完再看这题也“很简单的数学+dp问题”
我对标算的理解都写在注释里了
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll; inline char nc(){
static char buf[],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,,,stdin); if (p1==p2) return EOF; }
return *p1++;
} inline void read(int &x){ //指针快读
char c=nc(),b=;
for (;!(c>='' && c<='');c=nc()) if (c=='-') b=-;
for (x=;c>='' && c<='';x=x*+c-'',c=nc()); x*=b;
} const int P=; //神奇的模数
const int N=; int n,a[N];
ll f[][],sum[];
int tag[N],cnt[N]; ll fac[N],inv[N]; //fac[]阶乘 inv[]逆元
inline void Pre(){ //预处理阶乘及逆元(inv[])
fac[]=;
for (int i=;i<=n;i++) fac[i]=fac[i-]*i%P;
inv[]=;
for (int i=;i<=n;i++) inv[i]=(P-P/i)*inv[P%i]%P;
inv[]=;
for (int i=;i<=n;i++) (inv[i]*=inv[i-])%=P;
} inline ll Pow(ll a,int b){ //快速幂
ll ret=;
for (;b;b>>=,a=a*a%P) if (b&) ret=ret*a%P;
return ret;
} #define C(n,m) (fac[(n)]*inv[(m)]%P*inv[(n)-(m)]%P) //跑组合数 int main(){
read(n); Pre();
for (int i=;i<=n;i++) read(a[i]);
for (int i=;i<=;i<<=) tag[i]=; //2的幂次
int tem=;
for (int i=;i<=n;i++)
tag[a[i]]?cnt[a[i]]++:(tem*=)%=P; //cnt[] 2的幂次的数的个数
f[][]=; sum[]=;
int t=;
for (int i=;i<=;i<<=,t++){ //背包转移
ll tsum=;
for (int k=;i*k<= && k<=cnt[i];k++){
int tmp=i*k; // n
(tsum+=C(cnt[i],k))%=P; //实际上std似乎没有意识到ΣC(i, n)=2^n?
// i=0
for (int j=;~j;j--) (f[t][min(tmp+j,)]+=f[t-][j]*C(cnt[i],k)%P)%=P;
}
(f[t][]+=(Pow(,cnt[i])-tsum+P)*sum[t-]%P)%=P;
for (int j=;j<=;j++) (sum[t]+=f[t][j])%=P;
}
printf("%lld\n",f[t-][]*tem%P);
return ;
}
END