AT_arc205_e

· · 题解

动态 FMT 问题有复杂度更优的随机化做法，来源是 [集训队互测 2024] 观虫我，复杂度 O(n(\frac43)^{\log V})。

首先我们可以想到高低位分块的根号做法。考虑这个做法的实质是什么。现在对于每一位，有两种贡献的路径：修改时 0\to 0,1\to 1，查询时 0\to 0/1,1\to 1；修改时 0\to 0/1,1\to 1，查询时 0\to 0,1\to 1。要求最后修改对查询的贡献路径是 0\to 0/1,1\to 1。我们发现还存在第三种做法：修改时 0\to 0,1\to 0/1，查询时 0\to 0/1,1\overset{-1}{\to}0。其实际意义是维护 g_S=\prod_{S\subseteq T}f_T，则 f_S=\prod_{S\subseteq T}g_T^{(-1)^{|T|-|S|}},\prod_{T\subseteq S}f_T=\prod_{T\in S}\prod_{S\subseteq A}g_A^{(-1)^{|A|-|T|}}=\prod_{A\subseteq U}g_A^{\sum_{T\subseteq A\cap S}(-1)^{|A|-|T|}}=\prod_{T\subseteq U}g_T^{(-1)^{|T|}[T\cap S=\varnothing]}。这相当于把 \begin{bmatrix}1&1\\0&1\end{bmatrix} 分解为两个矩阵的乘积，有 \begin{bmatrix}1&1\\0&1\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix}=\begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}1&0\\1&1\end{bmatrix}\begin{bmatrix}1&1\\-1&0\end{bmatrix}。

现在有三种做法，可以证明，对每一位随机取一种规则，最后的期望复杂度是 O(n(\frac43)^{\log V})，这是因为每次操作每一位有 \frac 13 的概率被枚举两次，则每一位平均被枚举 \frac 43 次。还有一个问题是这样不太稳定，只要有一次随出较多的位被枚举两次就寄了。因此离线下来，随机 20 种规则，取开销最小的即可。这个题是乘法，查询时把除掉的乘在一起，求一次逆元。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
const int mod=998244353;
int n,x[400005],a,b,c,f[1048576];
long long minn=0x3f3f3f3f3f3f3f3f;
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
template<typename T>T inv(T a,T b){
  return qpow(a,b-2,b);
}
int main(){
  srand(time(0));
  for(int i=0;i<1<<20;i++)f[i]=1;
  in(n);
  for(int i=1;i<=n;i++)in(x[i]);
  for(int j=1;j<=20;j++){
    int maska=0,maskb=0,maskc=0;
    long long sum=0;
    for(int i=0;i<20;i++){
      int temp=rand()%3;
      if(temp==0)maska|=1<<i;
      else if(temp==1)maskb|=1<<i;
      else maskc|=1<<i;
    }
    for(int i=1;i<=n;i++){
      sum+=1<<__builtin_popcount((~x[i]&maskb)|(x[i]&maskc));
      sum+=1<<__builtin_popcount((x[i]&maska)|(~x[i]&maskc));
    }
    if(sum<minn)minn=sum,a=maska,b=maskb,c=maskc;
  }
  for(int i=1;i<=n;i++){
    int mask1=(x[i]&a)|(x[i]&b),mask2=(~x[i]&b)|(x[i]&c),u=1,d=1;
    for(int j=mask2;;j=(j-1)&mask2){
      f[j|mask1]=1ll*f[j|mask1]*x[i]%mod;
      if(!j)break;
    }
    mask1=x[i]&b,mask2=(x[i]&a)|(~x[i]&c);
    for(int j=mask2;;j=(j-1)&mask2){
      if(__builtin_parity(j&c))d=1ll*d*f[j|mask1]%mod;
      else u=1ll*u*f[j|mask1]%mod;
      if(!j)break;
    }
    cout<<1ll*u*inv(d,mod)%mod<<'\n';
  }
  return 0;
}