【HDOJ6595】Everything Is Generated In Equal Probability(期望DP)
2024-08-26 06:15:36
题意:给定一个N,随机从[1,N]里产生一个n,
然后随机产生一个n个数的全排列,求出n的逆序数对的数量并累加ans,
然后随机地取出这个全排列中的一个子序列,重复这个过程,直到为空,求ans在模998244353下的期望
思路:期望仅与长度有关,随手推一下式子
听说有通项公式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
#define N 110000
#define M 1100000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=,inv2=(MOD+)/;
double eps=1e-;
ll INF=1e14; ll fac[N],inv[N],dp[N],mi[N]; ll pw(ll x,ll y)
{
ll t=;
while(y)
{
if(y&) t=t*x%MOD;
x=x*x%MOD;
y>>=;
}
return t;
} int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} ll calc(ll n)
{
ll t=n*(n-)/;
return t*inv2%MOD;
} ll c(ll n,ll m)
{
if(n<m||m<) return ;
ll t=fac[n]*inv[m]%MOD*inv[n-m]%MOD;
return t;
} int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
fac[]=;
rep(i,,) fac[i]=fac[i-]*i%MOD;
inv[]=inv[]=;
rep(i,,) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
rep(i,,) inv[i]=inv[i-]*inv[i]%MOD;
mi[]=;
rep(i,,) mi[i]=mi[i-]*inv2%MOD;
rep(i,,)
{
ll t=;
rep(j,,i-) t=(t+dp[j]*c(i,j)%MOD*mi[i]%MOD)%MOD;
dp[i]=(calc(i)+t)%MOD*pw(1ll-mi[i]+MOD,MOD-)%MOD;
}
rep(i,,) dp[i]=(dp[i]+dp[i-])%MOD;
inv[]=inv[]=;
rep(i,,) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
while(scanf("%d",&n)!=EOF)
{
printf("%I64d\n",dp[n]*inv[n]%MOD);
}
return ;
}
最新文章
- Placeholder在IE8的兼容问题
- 构建自己的PHP框架--实现Model类(2)
- 验证LeetCode Surrounded Regions 包围区域的DFS方法
- Laravel 创建数据库
- java selenium (十) 操作浏览器
- 《Continuous Integration》读书笔记
- [Android Pro] proguard.cfg 配置文件
- IPC——信号量
- POJ3630Phone List(字典树)
- 【概率】COGS 1487:麻球繁衍
- ACM2026
- epoll讲解
- 用网页server实现钢琴弹奏(使用Wizwiki-W7500)
- [置顶] Java Web开发教程来袭
- php回调函数的使用
- JAVA常用知识点及面试题总结
- 网络Socket编程及实例
- SQL Server移除事务日志后sys.master_files依然存在记录问题
- nginx 正向代理上网
- excel怎么比较两组或两列数据的相同项和不同项