P7330

xujindong_ · 2025-05-22 17:41:11 · 题解

我们需要维护维护一个长 n=2^{12} 的动态 FFT，支持单点修改，单点查询 DFT，运算次数 2.5n\sqrt n。

如果直接在外面用数据结构的手法维护，因为 FFT 有 \log，最后很难纯正根号。考虑对 FFT 的结构动手。高低位分治，在 FFT 的某一层中，每对数 x,y 若只有这一位不同，会变为 f'_x\gets f_x+\omega f_y,f'_y\gets f_x-\omega f_y。只做 k 层，每个数会贡献到 2^k 个位置。维护 FWT 做完前 \frac k2(k=12) 层的结果，修改和查询都只涉及 O(\sqrt n) 个位置。系数容易比较两个数的位计算。复杂度 O(n\log n+q\sqrt n)，其中 O(q\sqrt n) 的常数是 2，可以通过。

下面的代码是经过位逆序置换后的 DIT，可能和正常写法有差别。

#include<bits/stdc++.h>
using namespace std;
const int n=4096,bn=64,bd=6,mod=998244353,w=63912897;
int m,l,wn[4096],rev[4096],a[4096],f[4096],c1[64][64],c2[4096];
ostringstream ans;
void modify(int x,int k){
  ans<<"S "<<k<<'\n',l++;
  ans<<"* "<<a[x]<<' '<<l-1<<'\n',l++;
  ans<<"- "<<l-1<<' '<<a[x]<<'\n',l++;
  a[x]=l-2,k=l-1;
  for(int i=0;i<bn;i++){
    ans<<"* "<<k<<' '<<c1[x>>bd][i]<<'\n',l++;
    ans<<"+ "<<f[i<<bd|(x&(bn-1))]<<' '<<l-1<<'\n',l++;
    f[i<<bd|(x&(bn-1))]=l-1;
  }
}
void query(int x){
  int pos=l++;
  ans<<"S 0\n",x=rev[x];
  for(int i=1,b;i<bn;i++)b=__builtin_ctz(i),c2[i]=(c2[i&(i-1)]+(rev[x>>(b+1)]>>1)+(x>>b&1?n/2:0))%n;
  for(int i=0;i<bn;i++){
    ans<<"* "<<f[(x&(n-bn))|i]<<' '<<c2[i]<<'\n',l++;
    ans<<"+ "<<pos<<' '<<l-1<<'\n',pos=l++;
  }
  ans<<"< "<<pos<<'\n',l++;
}
int main(){
  wn[0]=1;
  for(int i=1;i<n;i++)wn[i]=1ll*w*wn[i-1]%mod,rev[i]=rev[i>>1]>>1|(i&1?n>>1:0);
  for(int i=0;i<n;i++)ans<<"S "<<wn[i]<<'\n',l++;
  for(int x=0;x<bn;x++)for(int y=0;y<bn;y++)for(int i=0;i<bd;i++)if(x>>i&1)c1[x][y]=(c1[x][y]+(rev[y>>(i+1)]>>1)+(y>>i&1?n/2:0))%n;
  cin>>m;
  for(int i=0;i<n;i++)ans<<(i<m?">\n":"S 0\n"),a[i]=f[i]=l++;
  for(int i=n>>1;i>=bn;i>>=1){
    for(int j=0,p=0;j<n;j+=i<<1,p++){
      for(int k=j,y;k<j+i;k++){
        ans<<"* "<<f[k+i]<<' '<<(rev[p]>>1)<<'\n',y=l++;
        ans<<"- "<<f[k]<<' '<<y<<'\n',f[k+i]=l++;
        ans<<"+ "<<f[k]<<' '<<y<<'\n',f[k]=l++;
      }
    }
  }
  cin>>m;
  for(int i=1,opt,x,k;i<=m;i++){
    cin>>opt;
    if(opt==1)cin>>x>>k,modify(x,k);
    else cin>>k,k%=n,query(k);
  }
  return cout<<l<<'\n'<<ans.str(),0;
}