【数论 dp】2048
考场上一个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
最新文章
- Linux字符集的查看及修改
- Esfog_UnityShader教程_遮挡描边(原理篇)
- 腾讯web前端笔试题及个人答案
- Cocoa编程中视图控制器与视图类详解
- VS 2013的初配置
- oracle删除列
- Penetration test
- 解决m2eclipse之Unable to update index for central |
- IM 融云 之 安装cocoapods 安装 SDK
- ORACLE-EXP和IMP方法介绍
- 如何给网站添加CNZZ站长统计功能代码的常用办法
- C# 使用反射获取界面并传参
- 深入解读XML解析
- ES6基础
- JAVA第二次实训作业
- SQL Alias(别名)
- mysql-unsha1:在未知密码情况下,登录任意MYSQL数据库
- Linux中 /proc/[pid] 目录各文件简析
- [Python] 正确复制列表的方法
- Python模拟登陆淘宝并统计淘宝消费情况的代码实例分享
热门文章
- spark sql 的metastore 对接 postgresql
- vue 生命周期钩子函数
- __enter__,__exit__上下文管理协议
- [poj 2104] K-th Number【主席树】
- Codeforces Round #388 (Div. 2) D
- Hive_Hive和数据仓库简介
- ubuntu dpkg命令总结
- SpringBoot项目取消数据库配置
- kafka基础二
- error c2243:";类型转换"; 转换存在,但无法访问