题解 CF1119H 【Triple】

command_block · 2019-07-30 12:37:06 · 题解

前置芝士:位运算卷积FWT

或许有用的文章

约定: 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位置,可以得到:

众所周知 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) ,仍然无通过

形式化地讲:

那么 IFWT(S) 就是答案。

后面的乘积项一共只有八种可能(正负号)

我们分别求出这八种可能的个数就能用快速幂求答案了。

八种可能太烦了,有一种巧妙的化简方法 :

由异或的自反性,每个把三元组 \{a_i,b_i,c_i\} 异或上 a_i ,变为 \{0,b_i⊕a_i,c_i⊕a_i\}。

那么最后的结果异或上 ⊕_{i=1}^na_i 就能得到原来的答案。

反映到多项式上就是做一个下标映射。

回到这个式子:

我们现在经过改造之后所有的 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)

我们有 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) ,可以通过。

#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;
}