【资料图】
题目链接
首先注意到我们对这个环的扫描是一轮一轮进行的，每轮都会从左到右对每个没被删除的元素以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 #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid 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 rev; void ntt(vector &a,LL G) { LL nn=a.size(),gn,g,x,y;vector tmp=a; rep(i,nn) a[i]=tmp[rev[i]]; for(int len=1;len convolution(vector a,vector b,LL G) { LL nn=1,bt=0,sv=a.size()+b.size()-1;while(nn>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 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();} 
