题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6595
题目:
给出一个数n,在【1,n】等概率的选择一个数i,在【1,i】内每次等概率的选择一个数字组成长度为i的序列,这个序列中所有数都在【1,i】内,且两两互不相同(也就是说这个长度为i的序列是1->n的一种排列),以这个长度为i的序列为参数array运行程序:
1.统计array中的逆序对数目
2.统计array的子序列的逆序对数目(子序列的长度为0->length(array)),
3.array长度为0结束程序,否则以这个子序列为参数array运行程序,重复1,2
求最终逆序对数目的期望值,对998244353取模
程序如下:
input:
0
1
2
output:
0
332748118
554580197
解题思路:
对于一个长度为n的排列,它共有对数,每对数有的概率是逆序对,故一个长度为n的排列含有的逆序对数目的期望值=
对于一个长度为i的原序列,可以产生个子序列,它的长度为j的子序列有个,且概率都是。对于这个长度为j的子序列,它又可以当作一个原序列得到它的子序列,同理,它的子序列也可以当成一个原序列得到子序列。。。。所以这是一个很深的问题,但是我们可以用递推解决,依据是期望的可加性。
对于一个长度为i的原序列,它长度为j的子序列对应的逆序对数目的期望值已经求得,那么在求原序列逆序对的期望值时可以用到这个结果,不难推出下面这个式子:
但是在求f(i)的时候因为有边的式子中也有f(i),而f(i)是未知的,待求的,所以直接用上面这个式子解不出f(i),左右同乘,并移项可以得到如下式子:
这样就可以O()预处理得到所有的长度为i的原序列对应的逆序对数目的期望值,f(i)是取模后的结果
对于输入的x,,每一个i产生的概率是,值是f(i),所以最终结果是
时间复杂度分析:预处理O()9e6,查询O()≤5e4 ,故总的时间复杂度最大为:9e6+5e4
做的时候群里说有人蒙了个公式过了,真的是猛:O(1)的做法,公式是,再取模,求逆元就ok了
ac代码:
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 3005;
const int mod = 998244353;
ll mu[maxn], zi[maxn], f[maxn], c[maxn][maxn];
ll qkpow(ll a,ll p,ll mod)
{
ll t=1,tt=a%mod;
while(p)
{
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
}
return t;
}
ll getInv(ll a,ll mod)
{
return qkpow(a,mod-2,mod);
}
void init()
{
//组合数
for(int i = 1; i < maxn;i++)
{
c[i][i] = 1, c[i][0] =1;
for(int j = 1; j < i; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
//分母
mu[1] = 2;
for(int i = 2; i < maxn; i++)
mu[i] = (mu[i - 1] * 2) % mod;
f[0] = 0, f[1] = 0;
for(int i = 2; i < maxn; i++)
{
//或者不用单开一个分子数组,存到f[i]里
zi[i] = (c[i][2] * mu[i-1]) % mod;//原序列的逆序对期望值!!不要写成c[i][2]/2 * mu[i-1] 因为c[2][2]/2=0,而应该是0.5
for(ll j = 0; j < i; j++)
zi[i] = (zi[i] + (c[i][j] * f[j]) % mod) % mod;
f[i] = (zi[i] * getInv(mu[i] -1 , mod)) % mod;//得到第二个式子的f[i]
//printf("f[%d]: %lld\n", i, f[i]);
}
}
int main()
{
ios::sync_with_stdio(false);
int x;
init();
while(cin >> x)
{
int ans = 0;
for(int i = 1; i <= x; i++)
ans = (ans + f[i]) % mod;
ans = (ans * getInv(x, mod) ) % mod;
cout << ans << endl;
}
return 0;
}