题解 CF1119H 【Triple】
command_block
2019-07-30 12:37:06
**前置芝士**:位运算卷积FWT
[或许有用的文章](https://www.luogu.org/blog/command-block/wei-yun-suan-juan-ji-yu-ji-kuo-zhan)
**约定**: $F$ 是一个幂级数, $F[n]$ 是幂级数第 $n$ 项系数,幂级数之间的$*$指**异或卷积**。
------------
这题是真的妙啊! Orz出题人!!!
如果你熟悉生成函数卷积计数那一套,那么容易得到 :
把一个三元组 $\{a_i,b_i,c_i\}$ ,变成一个 $F_i[a_i]=x,\ F_i[b_i]=y,\ F_i[c_i]=z$ 的一个幂级数。
然后把所有幂级数都异或卷积起来就能得到答案了。
可是这题值域 $2^{17}=131072$ ,幂级数有 $10^5$ 个,直接卷积 $O(nk2^k)$ 肯定无法通过。
每个幂级数只有3个非零值,我们考虑找找规律。
设 $c(i,j)$ 为异或卷积的变换系数。
即 $FWT(F_k)[i]=\sum\limits_{j=0}^{n-1}c(i,j)F_k[j]$
由于$F_i$只有三个非0位置,可以得到:
$FWT(F_k)[i]=c(i,a_k)x+c(i,b_k)y+c(i,c_k)z$
众所周知 $c(i,j)=(-1)^{cnt(i\&j)}$
( $cnt(i)$ 是 $i$ 在二进制下 $1$ 的个数。)
则$FWT(F_k)[i]=(-1)^{cnt(i\&a_k)}x+(-1)^{cnt(i\&b_k)}y+(-1)^{cnt(i\&c_k)}z$
推导到这里,如果按照上式暴力算出每个幂级数的“点值”然后点乘,再 $IFWT$ ,复杂度是 $O((n+k)2^k)$ ,仍然无通过
形式化地讲:
$S[i]=\prod\limits_{k=1}^n{FWT(F_k)[i]}$
那么 $IFWT(S)$ 就是答案。
$\prod\limits_{k=1}^n{FWT(F_k)[i]}$
$=\prod\limits_{k=1}^n{(-1)^{cnt(i\&a_k)}x+(-1)^{cnt(i\&b_k)}y+(-1)^{cnt(i\&c_k)}z}$
后面的乘积项一共只有八种可能(正负号)
我们分别求出这八种可能的个数就能用快速幂求答案了。
八种可能太烦了,有一种巧妙的化简方法 :
由异或的自反性,每个把三元组 $\{a_i,b_i,c_i\}$ 异或上 $a_i$ ,变为 $\{0,b_i⊕a_i,c_i⊕a_i\}$。
那么最后的结果异或上 $⊕_{i=1}^na_i$ 就能得到原来的答案。
反映到多项式上就是做一个下标映射。
回到这个式子:
$S[i]=\prod\limits_{k=1}^n{(-1)^{cnt(i\&a_k)}x+(-1)^{cnt(i\&b_k)}y+(-1)^{cnt(i\&c_k)}z}$
我们现在经过改造之后所有的 $a_k=0$ ,所以 $cnt(i\&a_k)$ 一定是0.
那么就只剩四种情况 : $x+y+z;\ x+y-z;\ x-y+z;\ x-y-z;$
设这四种情况的方案数分别是 $c_1,c_2,c_3,c_4$ (注意,是针对 $S[i]$ 而言)
我们求出这些 $c$ 之后就能快速幂求 $S[i]$ 了。
我们考虑弄出 $4$ 个方程然后把四个 $c$ 解出来。
显然有 $c_1+c_2+c_3+c_4=n\quad(1)$
- 如果仅令 $F_k[b_k]=1$ ,即 $x=0,y=1,z=0$
那么此时 $FWT(F_k)[i]=(-1)^{cnt(i\&b_k)}$
这样就只考虑$y$的符号的贡献,有 $\sum\limits_{k=1}^nFWT(F_k)[i]=p1=c_1+c_2-c_3-c_4\quad(2)$
- $x+y+z$ 中 $y$ 为正,所以 $c_1$ 的系数为正。
- $x+y-z$ 中 $y$ 为正,所以 $c_2$ 的系数为正。
- $x-y+z$ 中 $y$ 为负,所以 $c_3$ 的系数为负。
- $x-y-z$ 中 $y$ 为负,所以 $c_4$ 的系数为负。
我们有 $FWT(F+G)=FWT(F)+FWT(G)$ 。
( 因为这东西是一个线性变换,其实就是向量乘矩阵 )
那么我们计算 $FWT(\sum\limits_{k=1}^nF_k)$ 就好了,其实就是计算 $G[k]=\sum\limits_{i=1}^n[b_i=k]$ 这样一个幂级数的 $FWT$。
- 如果令$F_k[c_k]=1$,即$x=0,y=0,z=1$
那么此时 $FWT(F_k)[i]=(-1)^{cnt(i\&c_k)}$
只考虑$z$的符号的贡献,有 $\sum\limits_{k=1}^nFWT(F_k)[i]=c_1-c_2+c_3-c_4\quad(3)$
同样是算$DWT(\sum\limits_{k=1}^nF_k)$就好了。
- 如果只令$F_k[b_k⊕c_k]=1$
那么就相当于把上面两种情况卷积,也就是**点值点积**。
那么此时 $FWT(F_k)[i]=(-1)^{cnt(i\&b_k)}(-1)^{cnt(i\&c_k)}$
那么$\sum\limits_{k=1}^nFWT(F_k)[i]=c_1-c_2-c_3+c_4\quad(4)$
(同时考虑$y,z$的符号贡献)
现在$4$个方程都齐了,那么手动解方程就好了。
具体的方程是:
原式$\begin{cases}n=c_1+c_2+c_3+c_4\\p1=c_1+c_2-c_3-c_4\\p2=c_1-c_2+c_3-c_4\\p3=c_1-c_2-c_3+c_4\end{cases}$
解得$\begin{cases}c_1=(n+p1+p2+p3)/4\\c_2=(n+p1-2c_1)/2\\c_3=(n+p2-2c_1)/2\\c_4=(n+p3-2c_1)/2\end{cases}$
注意这里不用考虑取模问题,因为 $c\leq n$.
最后再$IFWT$回去就好了。
复杂度 $O((k+\log n)2^k)$ ,可以通过。
```cpp
#include<algorithm>
#include<cstdio>
#define Maxn 140000
#define mod 998244353
#define inv2 499122177ll
#define ll long long
using namespace std;
inline int read()
{
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
ll powM(ll a,ll t=mod-2)
{
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int m;
ll x,y,z;
ll f1[Maxn],f2[Maxn],f3[Maxn],f[Maxn];
void DWT(ll *a)
{
for (int len=1;len<m;len<<=1)
for (int p=0;p<m;p+=len+len)
for (int i=p;i<p+len;i++){
ll sav0=a[i];
a[i]+=a[i+len];
a[i+len]=sav0-a[i+len];
}
}
void IDWT(ll *a)
{
for (int len=1;len<m;len<<=1)
for (int p=0;p<m;p+=len+len)
for (int i=p;i<p+len;i++){
ll sav0=a[i];
a[i]=(a[i]+a[i+len])*inv2%mod;
a[i+len]=(sav0-a[i+len])*inv2%mod;
}
}
int n;
int main()
{
n=read();m=(1<<read());
x=read();y=read();z=read();
int sav=0;
for (int i=0,a,b,c;i<n;i++){
a=read();b=read();c=read();
sav^=a;b^=a;c^=a;
f1[b]++;f2[c]++;f3[b^c]++;
}
DWT(f1);DWT(f2);DWT(f3);
ll s1=(x+y+z)%mod,s2=(x+y-z)%mod,
s3=(x-y+z)%mod,s4=(x-y-z)%mod;
for (int i=0;i<m;i++){
ll c1=(n+f1[i]+f2[i]+f3[i])/4;
f[i]=powM(s1,c1)*
powM(s2,(n+f1[i]-c1-c1)/2)%mod*
powM(s3,(n+f2[i]-c1-c1)/2)%mod*
powM(s4,(n+f3[i]-c1-c1)/2)%mod;
}IDWT(f);
for (int i=0;i<m;i++)
printf("%lld ",(f[i^sav]+mod)%mod);
return 0;
}
```