GuOJ 1200「HB 省队互测 2019 Round1 Day2」游戏 题解【FWT】【DP】
点击量:377
子集卷积这个东西终于学到了啊,被喷 9012 年还有人不会 FST 的就是我了。
题目背景
北斗是一个爱玩游戏的女孩子。
题目描述
北斗有 $n$ 部游戏要玩,这些游戏以 $0\sim n-1$ 标号。她准备花连续的若干天来玩游戏。每天她至少会玩一部游戏,且不会玩之前已经玩过的游戏。对于每一天,北斗每玩一部游戏,就能够得到一点愉悦值。特别地,有若干对游戏题材相同,或者画师相同,或者是前后作的关系。如果某一对游戏在同一天玩,北斗就会额外获得若干愉悦值。而北斗玩这 $n$ 部游戏的总愉悦值就是每一天的愉悦值之积。
北斗认为两种方案不同,当且仅当存在某一部游戏满足,北斗在这两种方案中不是同一天玩它。
现在北斗想要知道,对于所有的玩游戏方案,她能够得到的愉悦值之和是多少。你很喜欢吃北斗做的菜。为了吃到美味的晚饭,你只好帮助北斗解决这个问题。
输入格式
第一行输入两个非负整数 $n$ 和 $m$,表示游戏个数和有关联的游戏对数。
接下来 $m$ 行,每行输入三个非负整数 $a$,$b$,$c$,表示如果编号为 $a$ 和 $b$ 的游戏在同一天玩,北斗在当天会额外获得 $c$ 的愉悦值。
输出格式
输出一行一个数,表示所有方案北斗能得到的愉悦值之和。由于答案可能很大,只需输出答案对 $100000007$(一个大质数)取模后的结果即可。
样例
样例 1 输入
3 2 2 0 68 1 0 91
样例 1 输出
498
样例 1 解释
对于某一天,玩 $0$ 号游戏的愉悦值是 $1$,玩 $1$ 号游戏的愉悦值是 $1$,玩 $2$ 号游戏的愉悦值是 $1$,玩 $0,1$ 号游戏的愉悦值是 $93$,玩 $1,2$ 号游戏的愉悦值是 $2$,玩 $0,2$ 号游戏的愉悦值是 $70$,玩 $0,1,2$ 号游戏的愉悦值是$162$。
假如分三天玩完,有 $3!=6$ 种方案,每种方案的愉悦值是 $1$,总共能得到 $6$ 点愉悦值。
假如分两天玩完,那么有一天玩两部游戏,还有一天玩一部游戏。
当单独玩 $0$ 号游戏时,这两天的愉悦值是 $2$。
当单独玩 $1$ 号游戏时,这两天的愉悦值是 $70$。
当单独玩 $2$ 号游戏时,这两天的愉悦值是 $93$。
这三种情况又都有先后顺序之分,总共有 $6$ 种方案,愉悦值总和为 $330$。
假如分一天玩完,那么只有一种方案,愉悦值为 $162$。
总愉悦值为 $498$。
样例 2 输入
5 0
样例 2 输出
1305
数据规模与约定
测试点编号 $n$ $m$ $1\sim 4$ $\le 6$ $\le 100000$ $5\sim 10$ $\le 15$ $\le 100000$ $11\sim 12$ $\le 19$ $\le 0$ $13\sim 20$ $\le 19$ $\le 100000$ 对于全部数据,保证 $n\ge 0,m\ge 0,1\le c\le 100$,$0\le a,b\le n-1$,不存在两对关系所涉及的两个游戏分别相同或者某对关系的 $a$ 和 $b$ 相同。
题解
首先这个题有个显然的 $O(n\cdot 3^n)$ 背包做法。
令 $f[i][S]$ 表示前 $i$ 天玩了的游戏集合是 $S$ 的总愉悦值,预处理出 $b[S]$ 表示当集合 $S$ 中的游戏在同一天玩时所产生的愉悦值。
由于是背包,所以枚举子集就可以了。
$$
f[i][S]=\sum_{T\subseteq S,T\ne\varnothing}f[i-1][S\backslash T]\times b[T]
$$
期望得分 $50$ 分。
其中 $m=0$ 的 $10$ 分部分分可以通过容斥来解决。
令 $l$ 是玩完所有游戏所花的天数。
当 $l=1$ 时,有 $1^n$ 种方案,即所有游戏都放在第一天玩;
当 $l=2$ 时,有 $2^n-\mathrm{C}_2^1\times 1^n$ 种方案,即所有方案排除掉全在第一天和全在第二天;
当 $l=3$ 时,有 $3^n-\mathrm{C}_3^2\times 2^n+\mathrm{C}_3^1\times 1^n$ 种方案。
……
以此类推,当 $l=x$ 时,答案是至少用 $x$ 天玩完的方案数 $-$ 至少用 $x-1$ 天玩完的方案数 $+\cdots+(-1)^x\times$ 至少用 $0$ 天玩完的方案数。
时间复杂度 $O(n^2)$。
在上面的 dp 中,实际上是可以用 FWT 优化到 $O(n\cdot2^n)$ 的。
这个做法叫 FST,就是快速子集变换,也叫子集卷积。
对于上面的 dp 方程,我们想要的一个操作是
$$
f[S]=\!\!\!\!\!\!\!\!\!\!\!\!\sum_{A\operatorname{or}B=S,A\operatorname{and}B=0}\!\!\!\!\!\!\!\!\!\!\!\!g[A]\times h[B]
$$
也就是说,我们不希望集合 $A$ 和集合 $B$ 有交集,但 $A\operatorname{or}B=S$。
这个问题我一开始以为是要把原来的 FWT 稍微改一下,因为 $A\operatorname{or}B=S,A\operatorname{and}B=0\Leftrightarrow A\operatorname{or}B=S,A\operatorname{xor}B=S$,但是这样还是做不了 FWT。
事实上我们可以维护集合大小,把原来需要相乘的 $g$ 和 $h$ 数组开成二维 $g[x][A],h[y][B]$,当且仅当 $x=|A|$ 或 $y=|B|$ 时有值。因此对于一个 $|S|=i$ 的集合来说,它可以从大小为 $j$ 和 $i-j$ 的集合转移过来$(j\in(0,i))$。
那么上面的方程就变成了
$$
f[|S|][S]=\sum_{j=0}^{|S|}\sum_{A|B=S}g[j][A]\times h[i-j][B]
$$
这样一来就保证了 $S$ 只由 $j+k=|S|$ 的集合相乘转移,而乘法意味着如果不满足 $j+k$,那么乘法的两个因数一定至少有一个值为 $0$。
我们需要的卷积也就是对于多项式 $f[i]$
$$
f[i]=\sum_{j=0}^ig[j]*f[i-j]
$$
因为对于每个第一维都要做一遍卷积,因此需要做 $O(n)$ 次。
此外,我们可以令 $f[|S|][S]$ 表示用任意多天玩完集合 $S$ 中的游戏的方案数,并不限制前 $i$ 天玩完。因此玩完集合 $|S|$ 中游戏的天数可能是 $1$ 至 $|S|$ 天,我们只需要在用到它的时候更新到位就可以了。这样的话从小到大考虑每个集合,从各个子集转移的时候都是那些子集最终的状态。
那么最后的答案就是 $f[n][U]$,表示玩完所有游戏的方案数。
注意模数是 $10^8+7$。
Code:
#include<cstdio>
#ifdef wjyyy
#define gc getchar
#else
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
#define p 100000007
#define inv 50000004
#define ll long long
char buf[2100000],*p1=buf,*p2=buf;
int read()
{
int x=0;
char ch=gc();
while(ch<'0'||ch>'9')
ch=gc();
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=gc();
}
return x;
}
int a[20][600000],b[20][600000],ppc[600000];
int z[600000],n,tot;
void fwt(int *f,int flag)
{
for(int bs=2;bs<=tot;bs<<=1)
{
int r=bs>>1;
for(int i=0;i<tot;i+=bs)
for(int j=0;j<r;++j)
f[i+j+r]=(f[i+j+r]+flag*f[i+j]+p)%p;
}
}
int main()
{
n=read();
tot=(1<<n);
int m=read(),u,v,w,U=tot-1;
for(int i=0;i<=U;++i)
{
ppc[i]=ppc[i>>1]+(i&1);
b[ppc[i]][i]=ppc[i];
}
for(int i=1;i<=m;++i)
{
u=read();
v=read();
w=read();
int t=(1<<u)|(1<<v);
int y=U^t;
for(int j=y;;j=(j-1)&y)
{
b[ppc[t|j]][t|j]=(b[ppc[t|j]][t|j]+w)%p;
if(!j)
break;
}
}
a[0][0]=1;
fwt(a[0],1);
for(int i=1;i<=n;++i)
{
fwt(b[i],1);
for(int j=0;j<i;++j)
for(int k=0;k<=U;++k)
a[i][k]=(a[i][k]+(ll)a[j][k]*b[i-j][k])%p;
}
fwt(a[n],-1);
printf("%d\n",a[n][U]);
return 0;
}
说点什么