Comet OJ Contest 11 F arewell

Description

给定一张 $n$ 个点 $m$ 条边的图，一条边 $(u,v)$ 有 $\frac{1}{3}$ 的概率消失，$\frac{1}{3}$ 的概率定向成 $u\rightarrow v$ ，$\frac{1}{3}$ 的概率定向成 $v\rightarrow u$ 。求最后的图是 $\rm{DAG}$ 的概率。

$n\leq 20,m\leq \frac{n(n-1)}{2}$

Solution

一个很自然的想法是设 $f_{s}$ 表示当点集 $S$ 内的点为 $\rm{DAG}$ 时的概率。设 $g_{s,t}$ 表示点集 $s$ 到点集 $t$ 的边的数量初步考虑转移时可能会考虑这样的式子：

$f_s\leftarrow f_t \times f_{s\setminus t}\times \frac{1}{3}^{g_{t,s\setminus t}}$

这个式子有一点问题。因为同一张图可能对应了多个 $s$ ，这样会算重。而且也不太好容斥，因为相当于最后一张图被多算的次数应该是 $2$ 的 图中入度非零的点集大小 次幂减一，不太好做。

但是这个式子指明了一个方向，就是在 $\rm{DP}$ 所有的 $\rm{DAG}$ 时，可以枚举一个点集，让点集内的点成 $\rm{DAG}$ ，然后再向点集外的点连单向边。之前的 $\rm{DP}$ 之所以不好容斥，是因为枚举的点集是任意选的，而我们可以从「钦定选择的点集的性质」入手来。

比如，我们可以钦定点集 $S$ 内入度为 $0$ 的点集 $T$，也就是 $T$ 内的边全部消失，并且 $T$ 和 $S\setminus T$ 连的边要么单向指着 $S\setminus T$， 要么删掉。设 $g_s$ 表示点集 $s$ 内的边数，我们可以得到如下转移：

$f_S = \sum_{T\subseteq S\cap T\not=\emptyset}\frac{1}{3}^{g_{T}}\times f_{S\setminus T}\times \frac{2}{3}^{g_S-g_T-g_{S\setminus T}}$

但事实上，正如上面所说，我们只能「钦定」点集 $S$ 内的入度为 $0$ 的点集 $T$ ，而不能确保 $S\setminus T$ 内的点入度也为 $0$ 。所以我们要容斥，而这个容斥就很方便了。考虑最后一张图入度为 $0$ 的点集是确定的，假设为 $\mathcal{P}$ ，那么根据下式，我们可以方便地写出容斥系数为 $(-1)^{|T|+1}$

$\sum_{T\subseteq\mathcal{P} \cap T\not=\emptyset}(-1)^{|T|+1}=1$

于是我们将 $\rm{DP}$ 式子稍加变形（我们将 $\frac{1}{3}$ 都提出来，最后再乘上 $\frac{1}{3}^{m}$ ）：

$\frac{f_S}{2^{g_S}}=\sum_{T\subseteq S\cap T\not=\emptyset}\frac{(-1)^{|T|+1}}{2^{g_{T}}}\times \frac{f_{S\setminus T}}{2^{g_{S\setminus T}}}$

设 $f'_S=\frac{f_S}{2^{g_S}}$， $h_S=\frac{(-1)^{|S|+1}}{2^{g_S}}$ ，很明显上式是个子集卷积的形式，但是似乎是 $f'$ 自己和另一个函数卷 ......

考虑到子集卷积时，我们加了一维集合大小，所以直接做是没有后效性的。

复杂度 $\mathcal{O}(n^22^n)$ 。

通过这个题学到了蛮多东西的...有时候转移是枚举一个任意的东西，正因为这个枚举的是任意的，所以极容易算重，并且难以容斥。事实上，反正也是枚举，完全可以给枚举的东西增加一点限制——也就是「钦定」一个性质。这样子没准就能去掉很多重复情况，做到不算重/方便容斥。不加白不加呢...🤡

Kewth 神仙推荐 nb 题 Orz Orz

Code

const int N = 21, S = (1 << 20), mod = 998244353;
using namespace std;
int n, m;
int g[S], sz[S], h[N][S], f[N][S];
inline void Plus(int &a, int b){a += b - mod, a += (a >> 31) & mod;}
int qpow(long long b, int t){
    long long ret = 1;
    for(unsigned i = 1; i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
void FWT(int *a, int tp){
    int len = (1 << n);
    for(int i = 1; i < len; i <<= 1)
    for(int j = 0; j < len; j += (i << 1))
    for(int k = j; k < i + j; ++k)
        if(tp) Plus(a[i + k], a[k]);
        else Plus(a[i + k], mod - a[k]);
}
int main(){

    //cerr << 1.0 * (sizeof g + sizeof sz + sizeof h + sizeof f) / 1024 / 1024 << endl;

    fin >> n >> m;
    for(int i = 1, u, v; i <= m; ++i)
        fin >> u >> v, g[(1 << u - 1) | (1 << v - 1)] = 1;
    FWT(g, 1);

    int len = (1 << n);

    for(int i = 1; i < len; ++i){
        sz[i] = sz[i >> 1] + (i & 1);
        h[sz[i]][i] = (sz[i] & 1) ? qpow(2, mod - 1 - g[i]) : mod - qpow(2, mod - 1 - g[i]);
    }
    
    for(int i = 1; i <= n; ++i)
        FWT(h[i], 1);
    f[0][0] = 1;
    FWT(f[0], 1);

    
    for(int i = 1; i <= n; ++i)
    for(int j = 0; j <  i; ++j)
    for(int s = 0; s < len; ++s)
        Plus(f[i][s], 1ll * f[j][s] * h[i - j][s] % mod);

    FWT(f[n], 0);

    int ans = 1ll * f[n][len - 1] * qpow(2, g[len - 1]) % mod * qpow(3, mod - 1 - m) % mod;

    cout << ans << endl;
    return 0;
}