题目概述

给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。

解题报告

对于一个固定的 $\{a_n\}$ ，根据康托展开，可以得到排名：

$$ 1+\sum_{i=1}^{n-1}\sum_{a_i>a_j,j>i}(n-i)! $$

考虑每一个循环同构的贡献：

$$ n+\sum_{k=1}^{n-1}\sum_{a_i>a_{(i+k)\bmod n}}\sum_{j=k}^{n-1}j! $$

因此现在的核心问题就是求出：

$$ cnt_k=\sum_{i=1}^{n}\sum_{j=1}^{n}[a_i>a_j][j-i\equiv k\pmod n] $$

令 $p_{a_i}=i$ ，然后不难想到按照值域分治，统计 $[L,mid]$ 和 $[mid+1,R]$ 的贡献：

$$ F(x)=\sum_{i=L}^{mid}x^{p_i},G(x)=\sum_{i=mid+1}^{R}x^{-p_i}\\ cnt_k=\sum_{i\bmod n=k}[x^i]F(x)G(x) $$

但是 $p_i$ 的值域和 $[L,R]$ 无关，这样做复杂度完全不对，由于在 $[L,R]$ 个数少的时候可以采用暴力枚举的方法统计，因此考虑值域优化。

• 当 $[L,R]\le S$ 时，直接 ${S\choose 2}$ 暴力枚举。
• 当 $[L,R]>S$ 时，采用卷积，复杂度 $2n\log_2 2n$ 。

分治的形态是一棵线段树，由于 $[L,R]\le S$ 就不再分治，因此线段树叶子有 $n\over S$ 个，根据线段树性质易知总节点数 $2n\over S$ 。因此两部分的复杂度分别为 ${n\over S}{n\choose 2}$ 和 ${2n\over S}2n\log_2 2n$ 。解得 $S$ 为 $O(\sqrt{8n\log_2 2n})$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=250000,maxt=1<<19,S=6164,MOD=998244353;

int n,a[maxn+5],p[maxn+5],cnt[maxn+5],ans;
int T,wn[maxt+5],F[maxt+5],G[maxt+5],fac[maxn+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Count(int L,int R){
    for (int i=L;i<R;i++)
        for (int j=i+1;j<=R;j++){
            int d=(p[i]-p[j]+n)%n;
            cnt[d]=ADD(cnt[d],1);
        }
}
void Solve(int L,int R){
    if (R-L+1<=S) return Count(L,R);
    int mid=L+(R-L>>1);
    for (int i=0;i<T;i++) F[i]=G[i]=0;
    for (int i=L;i<=mid;i++) F[p[i]]++;
    for (int i=mid+1;i<=R;i++) G[n-p[i]]++;
    NTT(F,T,1);NTT(G,T,1);
    for (int i=0;i<T;i++) F[i]=MUL(F[i],G[i]);
    NTT(F,T,-1);
    for (int i=1;i<(n<<1);i++) cnt[i%n]=ADD(cnt[i%n],F[i]);
    Solve(L,mid);Solve(mid+1,R);
}
int main(){
    NTTPre();
    scanf("%d",&n);for (T=1;T<(n<<1);T<<=1);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]]=i;
    Solve(1,n);
    fac[0]=1;for (int i=1;i<n;i++) fac[i]=MUL(fac[i-1],i);
    for (int i=n-2;i>=0;i--) fac[i]=ADD(fac[i],fac[i+1]);
    ans=n;for (int i=1;i<n;i++) ans=ADD(ans,MUL(cnt[i],fac[i]));
    printf("%d\n",ans);
    return 0;
}