Description
L i n k \rm Link L i n k
Solution
为了方便,做如下定义:
设 F F F 为集合幂级数,则 F s F_s F s 表示 [ x s ] F [x^{s}]F [ x s ] F 。
这道题和 RNG and XOR \text{RNG and XOR} RNG and XOR 做法类似,感觉挺常考的,遂总结一下。
设 f s f_s f s 表示从初始状态开始,达到「只有集合 s s s 中含有的开关打开,其余的开关关闭的」状态的期望步数。
设 p s p_s p s 表示一次按开关的集合为 s s s 的概率(显然只有元素个数为 1 1 1 的集合有值,其余均为 0 0 0 )。
那么可以得到:
f s = { 0 s = ∅ ∑ a ⊕ b = s f a p b + 1 s ≠ ∅ f_s=
\begin{cases}
0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s=\emptyset\\
\sum\limits_{a\oplus b=s} f_ap_b+1\ \ \ \ \ \ s\neq \emptyset
\end{cases}
f s = ⎩ ⎨ ⎧ 0 s = ∅ a ⊕ b = s ∑ f a p b + 1 s = ∅
这是方程的形式。
令 F F F 为一个「下标和指数为集合的多项式」,并且 F = ∑ s ⫅ [ n ] f s x s F=\sum_{s\subseteqq [n]}f_sx^s F = ∑ s ⫅ [ n ] f s x s 。同理定义 P = ∑ s ⫅ [ n ] p s x s P=\sum_{s\subseteqq [n]}p_sx^s P = ∑ s ⫅ [ n ] p s x s 。
这也就是 V F K \rm VFK V F K 所说的「集合幂级数」。
定义该多项式的乘法为异或卷积,那么我们可以写出如下方程:
F = F ∗ P + I F=F*P+I
F = F ∗ P + I
事实上这个方程有点问题。观察可以发现,左右两边在 x ∅ x^{\emptyset} x ∅ 处的系数是不一样的,而且只有这个位置不同。
设 S ( G ) S(G) S ( G ) 表示多项式 G G G 的系数和。则我们可以列出:
S ( F ) = S ( F ) × S ( P ) + S ( I ) S(F)=S(F)\times S(P)+S(I)
S ( F ) = S ( F ) × S ( P ) + S ( I )
显然,S ( P ) = 1 , S ( I ) = 2 n S(P)=1,S(I)=2^n S ( P ) = 1 , S ( I ) = 2 n 。所以左边在 x ∅ x^{\emptyset} x ∅ 处应该还有一个 2 n 2^n 2 n 的系数。于是可以写出最终方程:
2 n + F = F ∗ P + I 2^n+F=F*P+I
2 n + F = F ∗ P + I
变形可得:
F = I − 2 n ( 1 − P ) F=\frac{I-2^n}{(1-P)}
F = ( 1 − P ) I − 2 n
设 F ^ \widehat{F} F 表示多项式 F F F F W T \rm FWT F W T 后的多项式。则有:
F ^ s = I − 2 n ^ s 1 − P ^ s ( s = ∅ ) \widehat{F}_s=\frac{\widehat{I-2^n}_s}{\widehat{1-P}_s}\ \ \ \ \ \ \ \ (s\not ={\emptyset})
F s = 1 − P s I − 2 n s ( s = ∅ )
这个式子不够简洁,我们进一步化简。在 F W T \rm FWT F W T 前在 x ∅ x^{\emptyset} x ∅ 处加常数 c c c ,相当于在 F W T \rm FWT F W T 后每一位加该常数 c c c 。 据此可以转化上式得(I ^ s \widehat{I}_s I s 在 s = ∅ s\not ={\emptyset} s = ∅ 时恒等于 0 0 0 ):
F ^ s = − 2 n 1 − P ^ s ( s = ∅ ) \widehat{F}_s=\frac{-2^n}{1-\widehat{P}_s}\ \ \ \ \ \ \ \ \ (s\not ={\emptyset})
F s = 1 − P s − 2 n ( s = ∅ )
由该式易知当 s = ∅ s=\emptyset s = ∅ 时右边分母为 0 0 0 ,所以之前规定 s = ∅ s\not ={\emptyset} s = ∅ 。
A G C \rm AGC A G C 那道题目到这里就结束了... 直接 F W T \rm FWT F W T 再 I F W T \rm IFWT I F W T 回去即可求出 F F F 。
但是这道题到这里还没完。目前已经有 40 p t s \rm 40pts 4 0 p t s 了,可喜可贺。
事实上,我们最后相当于求出来了所有状态的期望。而题目只要求某一项的值。我们不应该笼统地 F W T \rm FWT F W T 和 I F W T \rm IFWT I F W T ,我们必须从 F W T \rm FWT F W T 和 I F W T \rm IFWT I F W T 的本质入手,直接求出最后要求的 F S F_S F S 。这就要求我们拆 F W T \rm FWT F W T 和 I F W T \rm IFWT I F W T 的式子。
F W T \rm FWT F W T 变换的式子如下:
F ^ x = ∑ s ⫅ [ n ] ( − 1 ) ∣ s and x ∣ F s \widehat{F}_x=\sum_{s\subseteqq [n]}(-1)^{|s\text{ and } x|}F_s
F x = s ⫅ [ n ] ∑ ( − 1 ) ∣ s and x ∣ F s
I F W T \rm IFWT I F W T 变换的式子如下:
F x = 1 2 n ∑ s ⫅ [ n ] ( − 1 ) ∣ s and x ∣ F ^ s F_x=\frac{1}{2^n}\sum_{s\subseteqq [n]}(-1)^{|s\text{ and } x|}\widehat{F}_s
F x = 2 n 1 s ⫅ [ n ] ∑ ( − 1 ) ∣ s and x ∣ F s
最后相当于是要求 F S F_S F S 的值。那么我们用 I F W T \rm IFWT I F W T 展开它:
F S = 1 2 n ∑ s ⫅ [ n ] ( − 1 ) ∣ S and s ∣ F ^ s = F ^ ∅ 2 n − ∑ s ⫅ [ n ] , s = ∅ ( − 1 ) ∣ S and s ∣ 1 1 − P ^ s \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 S = 2 n 1 s ⫅ [ n ] ∑ ( − 1 ) ∣ S and s ∣ F s = 2 n F ∅ − s ⫅ [ n ] , s = ∅ ∑ ( − 1 ) ∣ S and s ∣ 1 − P s 1
因为 F ∅ = 0 F_{\emptyset}=0 F ∅ = 0 ,根据 I F W T \rm IFWT I F W T 变换的式子可得:
F ^ ∅ 2 n = − ∑ s ⫅ [ n ] , s = ∅ F ^ s 2 n = ∑ s ⫅ [ n ] , s = ∅ 1 1 − P ^ s \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}
2 n F ∅ = − 2 n s ⫅ [ n ] , s = ∅ ∑ F s = s ⫅ [ n ] , s = ∅ ∑ 1 − P s 1
再带回去可以得到:
F S = 2 ∑ s ⫅ [ n ] [ ∣ s and S ∣ ≡ 1 ( m o d 2 ) ] 1 1 − P ^ s F_S=2\sum_{s\subseteqq [n]}[|s\text{ and } S|\equiv 1\pmod{2}]\frac{1}{1-\widehat{P}_s}
F S = 2 s ⫅ [ n ] ∑ [ ∣ s and S ∣ ≡ 1 ( m o d 2 ) ] 1 − P s 1
而 1 − P ^ s 1-\widehat{P}_s 1 − P s 可以用之前 F W T \rm FWT F W T 变换的式子转化。考虑到 P i P_i P i 中事实上只有 n n n 个集合有值,那么我们完全可以把枚举集合转化为枚举元素,然后再化简式子:
1 − P ^ s = ∑ i = 1 n ( P i − ( − 1 ) [ i ∈ s ] P i ) = ∑ i ∈ s 2 P i \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}
1 − P s = i = 1 ∑ n ( P i − ( − 1 ) [ i ∈ s ] P i ) = i ∈ s ∑ 2 P i
所以可以得到最后的式子为
F S = ∑ s ⫅ [ n ] [ ∣ s and S ∣ ≡ 1 ( m o d 2 ) ] 1 ∑ i ∈ s P i F_S=\sum_{s\subseteqq [n]}[|s\text{ and } S|\equiv 1\pmod{2}]\frac{1}{\sum_{i\in s}P_i}
F S = s ⫅ [ n ] ∑ [ ∣ s and S ∣ ≡ 1 ( m o d 2 ) ] ∑ i ∈ s P i 1
最后这个式子组合意义就十分明显了,直接 D P \rm DP D P 即可。
不会有人看到这里了看不出来这个 DP \sout{\text{DP}} DP 吧 不会吧不会吧
复杂度 O ( n ∑ p ) \mathcal{O}(n\sum p) O ( n ∑ 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;
}