题解 P9660 [ICPC2021 Macao R] Pass the Ball!

· · 题解

首先一个排列可以划分为若干个置换环，每个置换环是独立的。

先考虑只有一个置换环的情况。我们按照环上的顺序提取出元素 a_{1\cdots n}，并令 b_i=b_{n+i}=a_i。那么进行 j(0\le j< n) 次操作的答案就是 c_j=\sum_{i=1}^na_ib_{i+j}。如果将 a 翻转，就变成了 c_j=\sum_{i=1}^na'_{n-i+1}b_{i+j}。j\ge n 时将 j 对 n 取模即可。

这是经典的多项式形式，考虑 NTT 加速。（由于 FFT 被卡精度了，这里使用三模 NTT）

我们已经用 O(n\log n) 的时间复杂度解决了一个置换环的问题。对于多个环的情况，由于置换环的大小和为 n，所以总的时间复杂度依然为 O(n\log n)。但是每一个置换环都需要 O(q) 来回答询问，置换环太多的时候会被卡成 O(nq)。

一个经典结论就是这些环中本质不同的大小只有 O(\sqrt n) 个，因为 \sum_{i=1}^{\sqrt n}i 是 O(n) 级别的。对于每个本质不同的大小分别回答一遍询问即可。时间复杂度 O(n\log n+q\sqrt n)。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=3e5;

inline int Pow(int x,int y,int p)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%p;
        x=1ll*x*x%p,y>>=1;
    }
    return res;
}
inline int Inv(int x,int p) {return Pow(x,p-2,p);}
const int Mod1=998244353,Mod2=1004535809,Mod3=469762049,g=3;
const long long Modx=1ll*Mod1*Mod2;
const int inv1=Inv(Mod1,Mod2),inv2=Inv(Modx%Mod3,Mod3);
struct Int
{
    int a,b,c;
    inline Int() {}
    inline Int(int _x): a(_x),b(_x),c(_x) {}
    inline Int(int _a,int _b,int _c): a(_a),b(_b),c(_c) {}
    inline void Rev() {a=Inv(a,Mod1),b=Inv(b,Mod2),c=Inv(c,Mod3);}
    inline ll Count()
    {
        long long res=1ll*(b-a+Mod2)%Mod2*inv1%Mod2*Mod1+a;
        return (1ll*(c-res%Mod3+Mod3)%Mod3*inv2%Mod3*Modx+res);
    }
} F[Maxn+5],G[Maxn+5];
inline Int operator+(Int x,Int y) {return Int((x.a+y.a)%Mod1,(x.b+y.b)%Mod2,(x.c+y.c)%Mod3);}
inline Int operator-(Int x,Int y) {return Int((x.a-y.a%Mod1+Mod1)%Mod1,(x.b-y.b%Mod2+Mod2)%Mod2,(x.c-y.c%Mod3+Mod3)%Mod3);}
inline Int operator*(Int x,Int y) {return Int(1ll*x.a*y.a%Mod1,1ll*x.b*y.b%Mod2,1ll*x.c*y.c%Mod3);}

int n,m,K,p[Maxn+5],vis[Maxn+5]; ll ans[Maxn+5];
int A[Maxn*4+5],B[Maxn*4+5],q[Maxn+5]; ll C[Maxn*4+5];
vector<int> v[Maxn+5];
vector<ll> h[Maxn+5];

struct Poly
{
    int lim=1,len,rev[Maxn*4+5];
    Int F[Maxn*4+5],G[Maxn*4+5];
    inline void GetLim(int n)
    {
        lim=1,len=0;
        while(lim<=n) lim<<=1,len++;
        For(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<len-1);
    }
    inline void NTT(Int *A,int opt)
    {
        Int ninv=Int(Inv(lim,Mod1),Inv(lim,Mod2),Inv(lim,Mod3));
        For(i,0,lim-1) if(i<rev[i]) swap(A[i],A[rev[i]]);
        for(int l=2,mid=1;l<=lim;l<<=1,mid<<=1)
        {
            Int wi=Int(Pow(g,(Mod1-1)/l,Mod1),Pow(g,(Mod2-1)/l,Mod2),Pow(g,(Mod3-1)/l,Mod3));
            if(opt==-1) wi.Rev();
            for(int j=0;j<lim;j+=l)
            {
                Int w=Int(1);
                for(int k=0;k<mid;++k)
                {
                    Int f=A[j+k],t=A[j+k+mid]*w;
                    A[j+k]=f+t,A[j+k+mid]=f-t;
                    w=w*wi;            
                }
            }
        }
        if(opt==-1) For(i,0,lim-1) A[i]=A[i]*ninv;
    }
    inline void GetMul(int *A,int *B,ll *C)
    {
        For(i,0,lim-1) F[i]=A[i],G[i]=B[i];
        NTT(F,1),NTT(G,1);
        For(i,0,lim-1) F[i]=F[i]*G[i];
        NTT(F,-1);
        For(i,0,lim-1) C[i]=F[i].Count();
    }
} P;

inline void Solve(int id)
{
    int s=v[id].size(); P.GetLim(s*3);
    For(i,0,P.lim-1) A[i]=B[i]=C[i]=0;
    For(i,1,s) A[i]=B[i]=B[s+i]=v[id][i-1];
    reverse(A+1,A+s+1),P.GetMul(A,B,C);
    if(h[s].empty()) h[s].resize(s+2);
    For(i,0,s-1) h[s][i]+=C[s+i+1];
}

int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>K;
    For(i,1,n) cin>>p[i];
    For(i,1,n) if(!vis[i])
    {
        ++m; for(int j=i;!vis[j];j=p[j])
            v[m].push_back(j),vis[j]=1;
    }
    For(i,1,m) Solve(i);
    For(i,1,K) cin>>q[i];
    For(i,1,n) if(!h[i].empty())
        For(j,1,K) ans[j]+=h[i][q[j]%i];
    For(i,1,K) cout<<ans[i]<<endl;
    return 0;
}