[ARC154E] Reverse and Inversion

拆贡献 + 推式子，对性质的观察。

拆一下贡献得到：

f (p) = \sum_{i} i \cdot (\sum_{i > j} [p_{i} < p_{j}] - \sum_{i < j} [p_{i} > p_{j}])

已知：

\begin{aligned} (1) & \sum_{i > j} [p_{i} < p_{j}] + \sum_{i > j} [p_{i} > p_{j}] = \sum [i > j] = i - 1 \\ (2) & \sum_{i > j} [p_{i} > p_{j}] + \sum_{i < j} [p_{i} > p_{j}] = \sum [p_{i} > p_{j}] = p_{i} - 1 \end{aligned}

$(1) - (2)$ 即可得到：

\sum_{i > j} [p_{i} < p_{j}] - \sum_{i < j} [p_{i} > p_{j}] = i - p_{i}

所以最终 $f (p) = \sum_{i} i^{2} - i \cdot p_{i}$ 。 $\sum_{i} i^{2}$ 为定值，我们相当于求 $E (\sum_{i} i \cdot p_{i})$ 。

地第一反应是 DP，每个数的贡献显然是独立的。我们考虑计算将位置 $i$ 上的数交换到位置 $j$ 上的概率。所有状态直接构成一个矩阵，直接矩阵快速幂优化一下就可以做到 $O (n^{3} \log m)$ 。

注意观察从 $i \to j$ 的可行操作数为 $min (i, j, n - i + 1, n - j + 1)$ ，这意味着 $i \to j$ 和 $i \to n - j + 1$ 的概率是一样的，那么 $i$ 如果被操作了的话，那么它的期望位置就是 $\frac{n + 1}{2}$ 。于是我们只需要分别计算 $i$ 被不被操作的概率及其期望。时间复杂度为 $O (n \log m)$ 。瓶颈为快速幂。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10,mod=998244353,inv2=mod+1>>1;
template <class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,k,mid;
int p[N];
int ans;
inline int adj(int x){return x>=mod?x-mod:x;}
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline int calc(int n){return 1ll*n*(n+1)/2%mod;}
inline int qpow(int x,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}

int main()
{
    read(n,k);
    m=qpow(calc(n),k);
    mid=1ll*(n+1)*inv2%mod;
    for(int i=1;i<=n;i++)read(p[i]);
    for(int i=1;i<=n;i++)
    {
        upd(ans,1ll*i*i%mod*m%mod);
        int d=qpow(adj(calc(i-1)+calc(n-i)),k);
        upd(ans,mod-1ll*adj(1ll*d*i%mod+1ll*adj(m-d+mod)*mid%mod)*p[i]%mod);
    }
    printf("%d\n",ans);
    return 0;
}