Problem Description
一天，Y_UME得到一个整数N和一个有趣的程序，如下图所示:
大致意思:
这是一个递归程序。
1.答案加上数组中逆序对的个数。
2.对数组等概率地取一个子序列(可以为空序列)
3.递归计算子序列, 并把结果加到答案中
4.返回答案
Y_UME想玩这个程序。首先，随机生成一个等概率的整数n∈[1,n]。然后他随机生成一个长度为n的排列，概率相等。然后，他运行有趣的程序(function calculate())，将这个排列作为参数，然后获得一个返回值。请输出此值的期望值998244353。
长度n的置换是长度n的数组，其中只包含一对不同的整数∈[1,n]。
置换p中的反转对是一对索引(i,j)，使得i>j和<pj。例如，一个置换[4,1,3,2]包含4个逆序:(2,1)，(3,1)，(4,1)，(4,1)，(4,3)。
在数学中，子序列是一个序列，它可以从另一个序列中派生出来，方法是删除一些或不删除元素，而不改变其余元素的顺序。注意，空子序列也是原始序列的子序列。
为了更好地理解，请参考https://en.wikipedia.org/wiki/ence
Input
有多个测试用例。
每种情况都以包含一个整数N(1≤N≤3000)的行开始。
保证所有测试用例的N之和不大于5×104。
Output
对于每个测试用例，输出一行包含一个表示答案的整数。
Sample Input
1
2
3
Sample Output
0
332748118
554580197
Solution
首先考虑一个长度为n的全排列期望产生多少逆序对
n长序列则最多有(frac{n(n-1)}{2})组逆序对, 其中每对出现的概率为(frac12), 所以期望为(frac{n(n-1)}{4})
然后考虑在n长序列中取m长子序列的长度的概率是多少
因为有(2^n)种取法, 在n中取m个有(C^m_n)种取法, 所以(P=frac{C^m_n}{2^n})
考虑f(n)表示n长序列的贡献
边界(f(0)=f(1)=0)
那么先加上其全排列的贡献: (f(n)+=frac{n(n-1)}{4})
再加上其子序列对其贡献: (f(n)+=sumlimits_{m=0}^{n}frac{C^m_n}{2^n}f(m))
所以得出柿子:
移项得:
最后答案就是:
Code
#include<iostream>
#define int unsigned long long
using namespace std;
const int N=4e3+28,p=998244353;
int Pow(int x,int y=p-2){
int re=1;
while(y){
if(y&1)re=re*x%p;
x=x*x%p;
y>>=1;
}
return re;
}
int mul[N],inv[N],two[N];
int inv4;
int pre(){
mul[0]=inv[1]=two[0]=1;
for(int i=1;i<=4000;i++)mul[i]=mul[i-1]*i%p;
for(int i=0;i<=4000;i++)inv[i]=Pow(mul[i]);
int inv2=Pow(2);
inv4=inv2*inv2%p;
for(int i=1;i<=4000;i++)two[i]=two[i-1]*inv2%p;
}
int C(int n,int m){
int re=mul[n];
re=re*inv[m]%p;
re=re*inv[n-m]%p;
return re;
}
int g(int x){
if(x==0)return 0;
int re=x*(x+p-1)%p;
re=re*inv4%p;
return re;
}
int f[N];
signed main(){
pre();
for(int i=2;i<=4000;i++){
f[i]=g(i);
for(int j=2;j<i;j++){
int tmp=f[j];
tmp=tmp*C(i,j)%p;
tmp=tmp*two[i]%p;
f[i]=(f[i]+tmp)%p;
}
f[i]=f[i]*Pow(1+p-two[i])%p;
}
int n;
while(scanf("%lld",&n)!=EOF){
int ans=0;
for(int i=2;i<=n;i++)ans=(ans+f[i])%p;
ans=ans*Pow(n)%p;
printf("%lld
",ans);
}
return 0;
}