【2022 NOIP 模拟赛 18】比赛 做题记录

有 $n$ 个人，等概率随机一个 $n$ 的排列作为他们的编号。每两个人都会进行且仅进行一场比赛，编号为 $i,j$ 的两个人（$i<j$）比赛时，编号为 $i$ 的人有 $p$ 的概率获胜，编号为 $j$ 的人有 $1-p$ 的概率获胜。

设 $f(k)$ 表示能把这 $n$ 个人分成两个集合 $S,T$ 满足 $|S|=k,|T|=n-k$ 且对于所有 $u\in S,v\in T$，$u$ 和 $v$ 比赛都是 $u$ 获胜的概率。

设 $g(1)=1,g(i)=g(i-1)^2+2$，你需要求出 $\sum\limits_{k=1}^{n-1}f(k)g(k)\operatorname{mod}998244353$。

$2\le n\le 10^6$，$0<p<1$。

首先易证明若能选出 $k$ 个人做胜者，那么这 $k$ 个人的集合一定是唯一的。

那么设 $f_{n,k}$ 表示 $n$ 个人中能选出 $k$ 个人做胜者的概率，那么考虑编号为 $n$ 的人被分到哪一组，有：

$f_{n,k}=f_{n-1,k-1}\times p^{n-k}+f_{n-1,k}\times q^{k}$

其中 $q=1-p$。

换一个角度，考虑编号为 $1$ 的人被分到哪一组，有：

$f_{n,k}=f_{n-1,k-1}\times q^{n-k}+f_{n-1,k}\times p^{k}$

那么有：

$f_{n-1,k-1}\times p^{n-k}+f_{n-1,k}\times q^{k}=f_{n-1,k-1}\times q^{n-k}+f_{n-1,k}\times p^{k}\\ f_{n-1,k-1}\times (p^{n-k}-q^{n-k})=f_{n-1,k}\times (p^{k}-q^{k})\\ f_{n-1,k-1}\times \frac{p^{n-k}-q^{n-k}}{p^{k}-q^{k}}=f_{n-1,k}\\ f_{n-1,k}=\prod\limits_{i=1}^{k}\frac{p^{n-i}-q^{n-i}}{p^{i}-q^{i}}\\ f_{n,k}=\prod\limits_{i=1}^{k}\frac{p^{n+1-i}-q^{n+1-i}}{p^{i}-q^{i}}\\$

这样就可以 $O(n\log n)$ 递推出 $f_{n,[1,n-1]}$，求出答案了。

但是有个特殊情况，当 $p=\frac{1}{2}$ 时，分母为 $0$，无法计算，所以需要额外讨论。

不难发现 $p=\frac{1}{2}$ 时，编号的大小关系对比赛结果没有任何影响，所以有 $f_{n,k}=\binom{n}{k}\times\frac{1}{2^{k(n-k)}}$。

那么这题就真的做完了。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

const int S=1000005,p=998244353;

int n,P,Q;
int fra[S],inv[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
	fio("contest");
	scanf("%d",&n);
	int a,b;
	scanf("%d%d",&a,&b);
	P=1ll*a*qpow(b,p-2)%p,Q=(1-P+p)%p;
	if(P!=Q)
	{
		int g=1,f=1,ans=0;
		for(int i=1;i<=n-1;i++)
		{
			int up=(qpow(P,n+1-i)-qpow(Q,n+1-i)+p)%p;
			int dwn=(qpow(P,i)-qpow(Q,i)+p)%p;
			f=1ll*f*up%p*qpow(dwn,p-2)%p;
			ans=(ans+1ll*f*g%p)%p;
			g=(1ll*g*g%p+2)%p;
		}
		printf("%d\n",ans);
	}
	else
	{
		fra[0]=1;
		for(int i=1;i<=n;i++) fra[i]=1ll*fra[i-1]*i%p;
		inv[n]=qpow(fra[n],p-2);
		for(int i=n;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
		int g=1,ans=0;
		for(int i=1;i<=n-1;i++)
		{
			ans=(ans+1ll*C(n,i)*qpow(qpow(2,1ll*i*(n-i)%(p-2))%p,p-2)*g%p)%p;
			g=(1ll*g*g%p+2)%p;
		}
		printf("%d\n",ans);
	}
	return 0;
}