[ZJOI2019] 开关

Description

$\rm Link$

Solution

为了方便，做如下定义：
设 $F$ 为集合幂级数，则 $F_s$ 表示 $[x^{s}]F$ 。

这道题和 $\text{RNG and XOR}$ 做法类似，感觉挺常考的，遂总结一下。

设 $f_s$ 表示从初始状态开始，达到「只有集合 $s$ 中含有的开关打开，其余的开关关闭的」状态的期望步数。
设 $p_s$ 表示一次按开关的集合为 $s$ 的概率（显然只有元素个数为 $1$ 的集合有值，其余均为 $0$）。
那么可以得到：

$f_s= \begin{cases} 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s=\emptyset\\ \sum\limits_{a\oplus b=s} f_ap_b+1\ \ \ \ \ \ s\neq \emptyset \end{cases}$

这是方程的形式。

令 $F$ 为一个「下标和指数为集合的多项式」，并且 $F=\sum_{s\subseteqq [n]}f_sx^s$。同理定义 $P=\sum_{s\subseteqq [n]}p_sx^s$ 。

这也就是 $\rm VFK$ 所说的「集合幂级数」。

定义该多项式的乘法为异或卷积，那么我们可以写出如下方程：

$F=F*P+I$

事实上这个方程有点问题。观察可以发现，左右两边在 $x^{\emptyset}$ 处的系数是不一样的，而且只有这个位置不同。
设 $S(G)$ 表示多项式 $G$ 的系数和。则我们可以列出：

$S(F)=S(F)\times S(P)+S(I)$

显然，$S(P)=1,S(I)=2^n$ 。所以左边在 $x^{\emptyset}$ 处应该还有一个 $2^n$ 的系数。于是可以写出最终方程：

$2^n+F=F*P+I$

变形可得：

$F=\frac{I-2^n}{(1-P)}$

设 $\widehat{F}$ 表示多项式 $F$ $\rm FWT$ 后的多项式。则有：

$\widehat{F}_s=\frac{\widehat{I-2^n}_s}{\widehat{1-P}_s}\ \ \ \ \ \ \ \ (s\not ={\emptyset})$

这个式子不够简洁，我们进一步化简。在 $\rm FWT$ 前在 $x^{\emptyset}$ 处加常数 $c$ ，相当于在 $\rm FWT$ 后每一位加该常数 $c$。 据此可以转化上式得（$\widehat{I}_s$ 在 $s\not ={\emptyset}$ 时恒等于 $0$）：

$\widehat{F}_s=\frac{-2^n}{1-\widehat{P}_s}\ \ \ \ \ \ \ \ \ (s\not ={\emptyset})$

由该式易知当 $s=\emptyset$ 时右边分母为 $0$ ，所以之前规定 $s\not ={\emptyset}$。

$\rm AGC$ 那道题目到这里就结束了... 直接 $\rm FWT$ 再 $\rm IFWT$ 回去即可求出 $F$ 。

但是这道题到这里还没完。目前已经有 $\rm 40pts$ 了，可喜可贺。

事实上，我们最后相当于求出来了所有状态的期望。而题目只要求某一项的值。我们不应该笼统地 $\rm FWT$ 和 $\rm IFWT$ ，我们必须从 $\rm FWT$ 和 $\rm IFWT$ 的本质入手，直接求出最后要求的 $F_S$ 。这就要求我们拆 $\rm FWT$ 和 $\rm IFWT$ 的式子。

$\rm FWT$ 变换的式子如下：

$\widehat{F}_x=\sum_{s\subseteqq [n]}(-1)^{|s\text{ and } x|}F_s$

$\rm IFWT$ 变换的式子如下：

$F_x=\frac{1}{2^n}\sum_{s\subseteqq [n]}(-1)^{|s\text{ and } x|}\widehat{F}_s$

最后相当于是要求 $F_S$ 的值。那么我们用 $\rm IFWT$ 展开它：

$\begin{aligned} F_S&=\frac{1}{2^n}\sum_{s\subseteqq [n]}(-1)^{|S\text{ and } s|}\widehat{F}_s\\ &=\frac{\widehat{F}_{\emptyset}}{2^n}-\sum_{s\subseteqq[n],s\not ={\emptyset}}(-1)^{|S\text{ and }s|}\frac{1}{1-\widehat{P}_s} \end{aligned}$

因为 $F_{\emptyset}=0$，根据 $\rm IFWT$ 变换的式子可得：

$\frac{\widehat{F}_{\emptyset}}{2^n}=-\frac{\sum\limits_{s\subseteqq [n],s\not ={\emptyset}}\widehat{F}_s}{2^n}=\sum_{s\subseteqq [n],s\not ={\emptyset}}\frac{1}{1-\widehat{P}_s}$

再带回去可以得到：

$F_S=2\sum_{s\subseteqq [n]}[|s\text{ and } S|\equiv 1\pmod{2}]\frac{1}{1-\widehat{P}_s}$

而 $1-\widehat{P}_s$ 可以用之前 $\rm FWT$ 变换的式子转化。考虑到 $P_i$ 中事实上只有 $n$ 个集合有值，那么我们完全可以把枚举集合转化为枚举元素，然后再化简式子：

$\begin{aligned} 1-\widehat{P}_s=\sum_{i=1}^{n}(P_i-(-1)^{[i\in s]}P_i)=\sum_{i\in s}2P_i \end{aligned}$

所以可以得到最后的式子为

$F_S=\sum_{s\subseteqq [n]}[|s\text{ and } S|\equiv 1\pmod{2}]\frac{1}{\sum_{i\in s}P_i}$

最后这个式子组合意义就十分明显了，直接 $\rm DP$ 即可。
不会有人看到这里了看不出来这个 $\sout{\text{DP}}$ 吧 不会吧不会吧

复杂度 $\mathcal{O}(n\sum p)$ 。

Code

const int N = 1e2 + 5, M = 5e4 + 23, mod = 998244353;
using namespace std;
int n, sum;
int s[N], v[N];
int f[2][2][M];
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(; t; t >>= 1, b = b * b % mod)
        if(t & 1) ret = ret * b % mod;
    return ret;
}
int main(){

    fin >> n;
    for(int i = 1; i <= n; ++i) 
        fin >> s[i];
    for(int i = 1; i <= n; ++i)
        fin >> v[i], sum += v[i];
    
    f[0][0][0] = 1;
    for(int i = 0; i < n; ++i){
        int p = i & 1, q = p ^ 1;
        memset(f[q], 0, sizeof f[q]);
        for(int j = 0; j <= 1; ++j)
        for(int k = 0; k <= sum; ++k) if(f[p][j][k]) {
            Plus(f[q][j][k], f[p][j][k]);
            Plus(f[q][j ^ s[i + 1]][k + v[i + 1]], f[p][j][k]);
        }
    }

    int ans = 0;
    for(int i = 1; i <= sum; ++i)
        Plus(ans, 1ll * qpow(i, mod - 2) * f[n & 1][1][i] % mod);
    
    cout << 1ll * ans * sum % mod << endl;
    return 0;
}