GuOJ 1200「HB 省队互测 2019 Round1 Day2」游戏 题解【FWT】【DP】

作者: wjyyy 分类: DP,FWT,多项式,数学,解题报告 发布时间: 2019-06-18 22:30

点击量:58

子集卷积这个东西终于学到了啊,被喷 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;
}

说点什么

avatar
  Subscribe  
提醒
/* */