Description
有一个n个点的环，有一个指针会从1号点开始向后扫描，每次扫描有p的概率删除当前点
询问每个点最后一个被删除的概率。
答案对998244353取模
n<=200000
Solution
直接计算要考虑前后两部分比较麻烦，我们不妨先考虑1号点如何计算。
记(f_n)表示n个点的环1号点最后一个被删除的概率。
枚举一轮中删去了几个
[f_n=sumlimits_{i=0}^{n-1}p^i(1-p)^{n-i}{n-1choose i}f_{n-i}
]
把i=0那一项移过来，可以得到一个递推式，显然可以用分治FFT加速。
这样是两个log的，我们有更优秀的做法。
枚举1号点最后在第k+1轮被淘汰，那么其他点至多在第k轮就被淘汰
[f_n=sumlimits_{kgeq 0}p(1-p)^k(1-(1-p)^k)^{n-1}
]
二项式展开
[=sumlimits_{kgeq 0}p(1-p)^ksumlimits_{j=0}^{n-1}(-1)^j(1-p)^{kj}{n-1choose j}
]
交换主体，整理
[=psumlimits_{j=0}^{n-1}(-1)^j{n-1choose j}sumlimits_{kgeq 0}(1-p)^{k(j+1)}
]
[=psumlimits_{j=0}^{n-1}(-1)^j{n-1choose j}{1over 1-(1-p)^{j+1}}
]
直接FFT，就是一个log的了
有了f考虑计算最后的答案，我们只需要枚举第一轮中这一个点前面删除了多少个即可，剩下的部分这个点就是第一个人了。
记(S_i)为i号点的答案。
易得
[S_i=sumlimits_{j=0}^{i-1}{i-1choose j}p^j(1-p)^{i-1-j}f_{n-i}
]
也是一个FFT解决
总的时间复杂度(O(nlog n))
Code
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
const int M=524288;
const int mo=998244353;
typedef long long LL;
using namespace std;
LL js[M+1],ny[M+1];
LL n,pl;
LL ksm(LL k,LL n)
{
LL s=1;
for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;
return s;
}
namespace poly
{
int wi[M+1],bit[M+1],ns;
void prp()
{
wi[0]=1,wi[1]=ksm(3,(mo-1)/M);
fo(i,1,M)
{
wi[i]=(LL)wi[i-1]*wi[1]%mo;
bit[i]=(bit[i>>1]>>1)|((i&1)<<18);
}
ns=ksm(M,mo-2);
}
void DFT(int *a)
{
fo(i,0,M-1) if(i<bit[i]) swap(a[i],a[bit[i]]);
for(int h=1,l=M>>1;h<M;h<<=1,l>>=1)
{
for(int j=0;j<M;j+=h<<1)
{
int *x=a+j,*y=x+h,wn=wi[l],w=1,v;
for(int i=0;i<h;i++,x++,y++,w=(LL)w*wn%mo)
{
v=(LL)*y *w%mo;
*y=(*x-v+mo)%mo,*x=(*x+v)%mo;
}
}
}
}
void IDFT(int *a)
{
DFT(a);
fo(i,0,M-1) a[i]=(LL)a[i]*ns%mo;
reverse(a+1,a+M);
}
}
using namespace poly;
int a[M+1],b[M+1],f[M+1];
int main()
{
LL al,bl;
cin>>n>>al>>bl;
js[0]=1;
fo(i,1,n) js[i]=js[i-1]*i%mo;
ny[n]=ksm(js[n],mo-2);
fod(i,n-1,0) ny[i]=ny[i+1]*(i+1)%mo;
pl=al*ksm(bl,mo-2)%mo;
LL v=1,r=(mo+1-pl)%mo;
fo(i,0,n-1)
{
a[i]=ny[i],b[i]=v*ksm((mo+1-r)%mo,mo-2)%mo*ny[i]%mo;
r=(1-pl+mo)%mo*r%mo;
v=mo-v;
}
prp();
DFT(a),DFT(b);
fo(i,0,M-1) a[i]=(LL)a[i]*b[i]%mo;
IDFT(a);
fo(i,1,n) f[i]=(LL)a[i-1]*js[i-1]%mo*pl%mo;
memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
r=1;LL r1=1;
fo(i,0,n-1)
{
a[i]=ny[i]*r%mo*f[n-i]%mo,b[i]=ny[i]*r1%mo;
r=r*pl%mo,r1=r1*(mo+1-pl)%mo;
}
DFT(a),DFT(b);
fo(i,0,M-1) a[i]=(LL)a[i]*b[i]%mo;
IDFT(a);
fo(i,1,n) printf("%lld
",(LL)a[i-1]*js[i-1]%mo);
}