专栏文章

AT_arc205_e

xxujindong_
AT_arc205_e题解参与者 10已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@minyirfe
此快照首次捕获于
2025/12/02 10:26
3 个月前
此快照最后确认于
2025/12/02 10:26
3 个月前
查看原文
动态 FMT 问题有复杂度更优的随机化做法，来源是 [集训队互测 2024] 观虫我，复杂度 O(n(43)log⁡V)O(n(\frac43)^{\log V})。
首先我们可以想到高低位分块的根号做法。考虑这个做法的实质是什么。现在对于每一位，有两种贡献的路径：修改时 0→0,1→10\to 0,1\to 1，查询时 0→0/1,1→10\to 0/1,1\to 1；修改时 0→0/1,1→10\to 0/1,1\to 1，查询时 0→0,1→10\to 0,1\to 1。要求最后修改对查询的贡献路径是 0→0/1,1→10\to 0/1,1\to 1。我们发现还存在第三种做法：修改时 0→0,1→0/10\to 0,1\to 0/1，查询时 0→0/1,1→−100\to 0/1,1\overset{-1}{\to}0。其实际意义是维护 gS=∏S⊆TfTg_S=\prod_{S\subseteq T}f_T，则 fS=∏S⊆TgT(−1)∣T∣−∣S∣,∏T⊆SfT=∏T∈S∏S⊆AgA(−1)∣A∣−∣T∣=∏A⊆UgA∑T⊆A∩S(−1)∣A∣−∣T∣=∏T⊆UgT(−1)∣T∣[T∩S=∅]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]}。这相当于把 [1101]\begin{bmatrix}1&1\\0&1\end{bmatrix} 分解为两个矩阵的乘积，有 [1101]=[1001][1101]=[1101][1001]=[1011][11−10]\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(43)log⁡V)O(n(\frac43)^{\log V})，这是因为每次操作每一位有 13\frac 13 的概率被枚举两次，则每一位平均被枚举 43\frac 43 次。还有一个问题是这样不太稳定，只要有一次随出较多的位被枚举两次就寄了。因此离线下来，随机 2020 种规则，取开销最小的即可。这个题是乘法，查询时把除掉的乘在一起，求一次逆元。
CPP
#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;
}

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...