拆贡献 + 推式子，对性质的观察。
拆一下贡献得到：
已知：
$(1)-(2)$ 即可得到：
所以最终 $f(p)=\sum_i i^2-i\cdot p_i$。$\sum_i i^2$ 为定值，我们相当于求 $E(\sum_i i\cdot p_i)$ 。
地第一反应是 DP，每个数的贡献显然是独立的。我们考虑计算将位置 $i$ 上的数交换到位置 $j$ 上的概率。所有状态直接构成一个矩阵，直接矩阵快速幂优化一下 就可以做到 $\mathcal 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$ 被不被操作的概率及其期望。时间复杂度为 $\mathcal O(n\log m)$。瓶颈为快速幂。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #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;
}
|