首先注意到我们对这个环的扫描是一轮一轮进行的，每轮都会从左到右对每个没被删除的元素以p的概率删除。如果我们能对每个\(t(t\in [0,\infin],t是整数)和i\)求出c号点在第\(t+1\)轮被删掉，且是第i个被删除的元素，那么就能求出答案了。不幸的是我们不能枚举所有的t。但是不管怎么样先把式子列出来看看。
令\(f_i=\)最后i+1的答案，\(F(x)=\sum_{i=0}^{n-1}f_ix^i\)。我们要求出这个多项式(生成函数)F。
令\(p=\frac ab,q=1-p\)。我们现在枚举t，把F写成\(\sum_{t=0}^{\infin}\cdots\)的形式。c必须在第t+1轮被删掉发生的概率是\(pq^t\)。c前面的c-1个元素在c被删掉之前经理了t+1轮，每个点被删掉的概率为\(1-q^{t+1}\)，没被删掉的概率为\(q^{t+1}\)。c后面的n-c个元素在c被删掉之前经历了t轮，概率同理。所以\(F(x)=\sum_{t=0}^{\infin}pq^t\cdot(q^{t+1}+(1-q^{t+1})x)^{c-1}\cdot(q^t+(1-q^t)x)^{n-c}\)。这一步是核心思想，后面只要不断化简这个式子就行了。式子的化简并不是很难，用到的技巧也就是二项式定理啥的。
大量公式警告(其实都很容易看懂)
\[\begin{align} F(x)&=\sum_{t=0}^{\infin}pq^t\cdot(q^{t+1}+(1-q^{t+1})x)^{c-1}\cdot(q^t+(1-q^t)x)^{n-c}\\ &=\sum_{t=0}^{\infin}pq^t\cdot (x+q^{t+1}(1-x))^{c-1}\cdot (x+q^t(1-x))^{n-c}\\ &=\sum_{t=0}^{\infin}pq^t\cdot[\sum_{i=0}^{c-1}\binom{c-1}{i}x^iq^{(t+1)(c-1-i)}(1-x)^{c-1-i}]\cdot[\sum_{j=0}^{n-c}\binom{n-c}{j}x^j q^{t(n-c-i)}(1-x)^{n-c-i}]\ \ (二项式定理)\\ &=p\sum_{i=0}^{c-1}\binom{c-1}{i}x^i\sum_{j=0}^{n-c}\binom{n-c}{j}x^j\cdot\sum_{t=0}^{\infin}q^{t(n-i-j)+c-1-i}\cdot(1-x)^{n-1-i-j}\ \ (交换sigma)\\ &=p[\sum_{i=0}^{c-1}\binom{c-1}{i}x^iq^{c-1-i}\sum_{j=0}^{n-c}\binom{n-c}{j}x^j]\cdot[\sum_{t=0}^{\infin}q^{t(n-i-j)}]\cdot[(1-x)^{n-1-i-j}] \end{align} \]上面最后一个式子除了最开头的一个p，其余部分用方括号分成了三部分(方括号仅仅用来划分式子，不表示运算顺序)。先用一次卷积求出第一部分两个sigma的乘积。注意到第二部分是一个等比数列，如果知道了i+j可以直接\(O(1)\)求出；而第一部分在枚举了i和j的情况下它们乘积的下标也是i+j，所以算出第一部分之后把前两部分做一个按位乘就行了。第三部分继续二项式定理展开，与前两部分的乘积再做一次卷积就得到最终结果\(F(x)\)了。
一共就做了两次卷积，总复杂度\(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
if(x==0) return 0;
LL res=x,ret=1;
while(a>0)
{
if((a&1)==1) ret=ret*res%MOD;
a>>=1;
res=res*res%MOD;
}
return ret;
}
namespace NTT
{
vector <LL> rev;
void ntt(vector <LL> &a,LL G)
{
LL nn=a.size(),gn,g,x,y;vector <LL> tmp=a;
rep(i,nn) a[i]=tmp[rev[i]];
for(int len=1;len<nn;len<<=1)
{
gn=qpow(G,(MOD-1)/(len<<1));
for(int i=0;i<nn;i+=(len<<1))
{
g=1;
for(int j=i;j<i+len;++j,(g*=gn)%=MOD)
{
x=a[j];y=a[j+len]*g%MOD;
a[j]=(x+y)%MOD;a[j+len]=(x-y+MOD)%MOD;
}
}
}
}
vector <LL> convolution(vector <LL> a,vector <LL> b,LL G)
{
LL nn=1,bt=0,sv=a.size()+b.size()-1;while(nn<a.size()+b.size()-1) nn<<=1LL,++bt;
while(a.size()<nn) a.pb(0);while(b.size()<nn) b.pb(0);
rev.clear();
rep(i,nn)
{
rev.pb(0);
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bt-1));
}
ntt(a,G);ntt(b,G);
rep(i,nn) (a[i]*=b[i])%=MOD;
ntt(a,qpow(G,MOD-2));
while(a.size()>sv) a.pop_back();
LL inv=qpow(nn,MOD-2);
rep(i,a.size()) (a[i]*=inv)%=MOD;
return a;
}
}
LL n,p,q,c,fac[1000010],inv[1000010];
LL CC(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}
int main()
{
fileio();
fac[0]=1;repn(i,1000005) fac[i]=fac[i-1]*i%MOD;
rep(i,1000003) inv[i]=qpow(fac[i],MOD-2);
int T;
cin>>T;
while(T--)
{
LL a,b;
cin>>n>>a>>b>>c;
p=a*qpow(b,MOD-2)%MOD;
q=(MOD+1-p)%MOD;
vector <LL> A,B,C;
rep(i,c) A.pb(CC(c-1,i)*qpow(q,c-1-i)%MOD);
rep(i,n-c+1) B.pb(CC(n-c,i));
C=NTT::convolution(A,B,3);
rep(i,C.size())
{
LL val=qpow((1-qpow(q,n-i)+MOD)%MOD,MOD-2);
(C[i]*=val)%=MOD;
}
A.clear();B.clear();
rep(i,C.size()) A.pb(C[i]*fac[n-1-i]%MOD);
rep(i,n)
{
LL val=inv[i];
if(i%2) val=(MOD-val)%MOD;
B.pb(val);
}
C=NTT::convolution(A,B,3);
rep(i,n) (C[i]*=inv[n-1-i])%=MOD;
rep(i,n) (C[i]*=p)%=MOD;
rep(i,n) printf("%lld\n",C[i]);
}
termin();
}