OI - Game on a Circle(HDU) | Lucky

写了半天发现是减法卷积写挂了 QwQ

# 题面

> Linked HDU 6801

点击展开/折叠题面

有 $n$ 个石子编号为 $1\sim n$，按顺序排列为一个环。

你一开始在石子 $1$。在石子 $i$ 时，你有 $p$ 的概率将这块石子丢掉（$1-p$ 的概率什么都不做），然后按环上的顺序移动到下一个没有丢掉的石子。

给定 $c$，对于每个 $i\in[1,n]$，求石子 $c$ 是第 $i$ 个被丢掉的石子的概率。

# 解析

设 $f_i$ 是恰好有 $i$ 个石子在 $c$ 之后被扔掉的概率，它不太好求，于是转化成 $g_i$ 表示钦定 $i$ 个石子在 $c$ 之后被扔掉的概率，照例二项式反演一波：

$g_i=\sum_{j=i}^n\binom jif_j\Rightarrow f_i=\sum_{j=i}^n(-1)^{j-i}\binom jig_j$

为了计算 $g_i$，还得先算出 $h_{i,j}$——

现在还剩 $i$ 个石子排成环其中（原本的环中）第 $c$ 个石子排在（剩下的环中）第 $j$ 个，当前要操作的石子是（剩下的环中）第一个石子，则 $h_{i,j}$ 表示石子 $c$ 是这些石子中第一个被扔掉的概率。

> Tab. $p$ 是丢掉的概率，$q$ 是不丢的概率

比较简单的：

$h_{i,j}=q^{j-1}\sum_{k=0}^{+\infty}q^{ik}p=\frac{pq^{j-1}}{1-q^i}$

则 $g_i$ 可以表示为：

$g_i=\sum_{j+k=i}\binom{c-1}j\binom{n-c}kh_{i+1,j+1}$

上式 $j,k$ 分别表示 $[1,c-1]$ 中有 $j$ 个石子在 $c$ 之后丢、$[c+1,n]$ 中有 $k$ 个石子在 $c$ 之后丢。

化化式子变成卷积的形式：

$\frac{1-q^{i+1}}p\cdot g_i=\sum_{j+k=i}\binom{c-1}jq^{j-1}\cdot\binom{n-c}k$

先卷一遍，算出 $g_i$，然后再卷一遍算出 $f_i$（注意是减法卷积）。

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define cs const int &
const int N=1<<21,MOD=998244353;
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}
inline int Ri(){
    register int r=0,c=getchar();
    while(c<'0' || '9'<c) c=getchar();
    while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r;
}

int p,q,len,lglen;
int powG[30],invG[30],rev[N];
int fac[N+1],ifac[N+1];
int polA[N],polB[N];

void Init(){
    for(int i=0;i<22;i++){
        powG[i]=Pow(3,(MOD-1)>>i);
        invG[i]=Pow(powG[i],MOD-2);
    }
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=Mul(fac[i-1],i);
    ifac[N]=Pow(fac[N],MOD-2);
    for(int i=N-1;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
}
void NTT(int *A,int tpo){
    rev[0]=0;
    for(int i=1;i<len;i++){
        rev[i]=rev[i>>1]>>1|((i&1)<<(lglen-1));
        if(rev[i]<i) swap(A[i],A[rev[i]]);
    }
    for(int L=2,T=1,lgL=1;L<=len;L<<=1,T<<=1,lgL++){
        int per=tpo==1? powG[lgL]:invG[lgL];
        for(int i=0;i<len;i+=L)
            for(int j=i,cur=1;j<i+T;j++,cur=Mul(cur,per)){
                int Ajt=Mul(cur,A[j+T]);
                A[j+T]=Sub(A[j],Ajt);
                A[j]=Add(A[j],Ajt);
            }
    }
    if(tpo==1) return;
    int dv=Mul(ifac[len],fac[len-1]);
    for(int i=0;i<len;i++) A[i]=Mul(A[i],dv);
}
inline int Comb(cs a,cs b){return a>b? 0:Mul(Mul(ifac[a],ifac[b-a]),fac[b]);}
int main(){
    Init();
    int cas=Ri();
    while(cas--){
        int n=Ri(),tmpa=Ri(),tmpb=Ri(),c=Ri();
        p=Mul(tmpa,Pow(tmpb,MOD-2)),q=Sub(1,p);
        len=1,lglen=0;
        while(len<=n*2) len<<=1,lglen++;
        memset(polA,0,sizeof(int)*len);
        memset(polB,0,sizeof(int)*len);
        for(int i=0,powq=1;i<=c-1;i++,powq=Mul(powq,q))
            polA[i]=Mul(Comb(i,c-1),powq);
        for(int i=0;i<=n-c;i++) polB[i]=Comb(i,n-c);
        NTT(polA,1),NTT(polB,1);
        for(int i=0;i<len;i++) polA[i]=Mul(polA[i],polB[i]);
        NTT(polA,-1);
        for(int i=0,powq=q;i<n;i++,powq=Mul(powq,q)){
            polB[i]=Mul(Mul(polA[i],Mul(Pow(Sub(1,powq),MOD-2),p)),fac[i]);
            polA[i]=(i&1)? Sub(0,ifac[i]):ifac[i];
        }
        for(int i=n;i<len;i++) polA[i]=polB[i]=0;
        reverse(polB,polB+n);
        NTT(polA,1),NTT(polB,1);
        for(int i=0;i<len;i++) polA[i]=Mul(polA[i],polB[i]);
        NTT(polA,-1);
        for(int i=0;i<n;i++) printf("%d\n",Mul(polA[i],ifac[n-i-1]));
    }
    return 0;
}

THE END

Thanks for reading!

$\begin{split} “\ &在坠入深渊的时候\\ &抬头仰望\\ &仰望寻觅温暖目光\\ &残风迎浪\\ &眼底星河荡漾\\ &踏着梦\ 走过时光\\ &仰望是你站的方向\\ &俯视是含泪的过往\ ”\\ ——&\text{《梦与星海之间(Cover》By 司南} \end{split}$

> Linked 梦与星海之间-网易云