Description：

n个人两两之间都有一场比赛，编号小的人胜率是 $p$ 。我们称前 $k$ 名可确定，当且仅当存在一个大小为 $k$ 的集合 $S$ ，使得 $S$ 中的每个人都战胜了不在 $S$ 中的所有人。问能确定前 $k=1,\dots,n−1$ 名的概率。

$1\leqslant n\leqslant 10^6$

Solution：

玄学。

设 $f[i][j]$ 表示前 $i$ 个人可以确定前 $j$ 位的概率。

考虑把第 $i$ 个人插进去，那么为了保证可以确定前 $j$ 名，要么前 $j$ 名都打败了他，要么他打败了后面所有人，即： $$ f[i][j]=f[i-1][j]\times p^{j}+f[i-1][j-1]\times(1-p)^{i-j} $$ 同样的，把第 $1$ 个人插进去，可以得到： $$ f[i][j]=f[i-1][j]\times (1-p)^j+f[i-1][j-1]\times p^{i-j} $$ 把他们联立： $$ \begin{align} f[i-1][j]\times p^j+f[i-1][j-1]\times(1-p)^{i-j}&=f[i-1][j]\times (1-p)^j+f[i-1][j-1]\times p^{i-j}\\ f[i-1][j]\times (p^j-(1-p)^j)&=f[i-1][j-1]\times (p^{i-j}-(1-p)^{i-j})\\ \end{align} $$ 那么就可以得到： $$ f[n][j]\times (p^j-(1-p)^j)=f[n][j-1]\times (p^{n+1-j}-(1-p)^{n+1-j})\\ f[n][j]=f[n][j-1]\times \frac{p^{n+1-j}-(1-p)^{n+1-j}}{p^j-(1-p)^j}\\ $$ 显然有 $f[n][0]=1$ ，于是就可以递推了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,p,q;

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

#define MAXN 1000010

int main()

{

	scanf("%d%d",&n,&p);

	q = (1 - p + P) % P;

	if(p == q)

	{

		int C = 1;

		for(int i = 1;i < n;++i)

		{

			C = 1ll * C * power(i,P - 2) % P * (n - i + 1) % P;

			cout << 1ll * power(power(p,n - i),i) * C % P << " ";

		}

		cout << endl;

	}

	else

	{

		int last = 1;

		for(int i = 1;i < n;++i)

		{

			last = 1ll * last * (power(p,n + 1 - i) - power(q,n + 1 - i) + P) % P * power((power(p,i) - power(q,i) + P) % P,P - 2) % P;

			cout << last << " ";

		}

		cout << endl;

	}

	return 0;

}