⭐

Problem

一个博弈游戏：给定一棵有根树，放一个石子在根节点，轮流执手，每次往任意叶子节点方向移一步，不能移则为输。

现在给你 $n$ 个点，生成任意一棵有根树，问先手获胜的概率。有 $q$ 次询问。

$n,q \leq 10^5$

Solution

令 $f(x), g(x)$ 分别为后手和先手必胜的 EGF ，则 $f(x)+g(x)=\sum \frac{(i-1)!}{i!}x^i$ 。所以有 $g(x)=-ln(1-x)-f(x)$ 。其中 $(i-1)!$ 为无标号有根树的方案数，$\sum \frac{(-1)^{i+1}}{i}x^i$ 为 $ln(x+1)$ 的麦克劳林级数。

根据SG函数，因为后手必胜的子树皆为先手必胜，那么有 $xe^{g(x)}=f(x)$ 。解方程得 $f(x)=ln(1-ln(1-x))$ 。并不知道过程。

所以可以得到最终的概率：$\frac{(n-1)!-n!f_n}{(n-1)!}=1-nf_n$ 。

Code

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;

const int N=4e5+10;
int f[N], g[N], h[N], r[N], n;

void gen(int m) {
    int l=0;
    for(n=1; n<=m; n<<=1) l++;
    for(int i=1; i<n; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}

int qpow(int x, int y) {
    assert(y>=0);
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD, y>>=1;
    }
    return ret;
}

void dft(int x[], int d) {
    for(int i=1; i<n; i++) if(r[i]>i) swap(x[i], x[r[i]]);
    int t, w, o;
    for(int i=1; i<n; i<<=1) {
        o=qpow(3, d*(MOD-1)/(i<<1)+MOD-1);
        for(int j=0; j<n; j+=(i<<1)) {
            w=1;
            for(int k=0; k<i; k++, w=1ll*w*o%MOD)
                t=1ll*x[i+j+k]*w%MOD, x[i+j+k]=(x[j+k]-t+MOD)%MOD,
                (x[j+k]+=t)%=MOD;
        }
    }
}

void mul(int x[], int y[], int z[], int m, int mode=0) {
    gen(m<<1);
    int a[N]={0}, b[N]={0};
    copy(x, x+m, a), copy(y, y+m, b);
    dft(a, 1), dft(b, 1);
    for(int i=0; i<n; i++)
        if(!mode) a[i]=1ll*a[i]*b[i]%MOD;
        else a[i]=(2ll*b[i]-1ll*a[i]*b[i]%MOD*b[i]%MOD+MOD)%MOD;
    dft(a, -1);
    int inv=qpow(n, MOD-2); for(int i=0; i<m; i++) z[i]=1ll*a[i]*inv%MOD;
}

void inv(int a[], int f[], int deg) {
    assert(deg>0);
    if(deg==1) { f[0]=qpow(a[0]%MOD, MOD-2); return; }
    inv(a, f, (deg+1)>>1);
    mul(a, f, f, deg, 1);
}

void deri(int x[], int n) {
    for(int i=0; i<n; i++) x[i]=1ll*(i+1)*x[i+1]%MOD;
    x[n-1]=0;
}
void inte(int x[], int n) {
    for(int i=n-1; i>0; i--) x[i]=1ll*x[i-1]*qpow(i, MOD-2)%MOD;
    x[0]=0;
}
void pln(int x[], int y[], int n) {
    int a[N]={0}, b[N]={0}; copy(x, x+n, a);
    inv(a, b, n);
    deri(a, n);
    mul(a, b, a, n);
    inte(a, n);
    for(int i=0; i<n; i++) y[i]=a[i];
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n=1e5+10;
    f[0]=1, f[1]=MOD-1;
    pln(f, g, n);
    for(int i=0; i<n; i++) g[i]=(MOD-g[i])%MOD;
    g[0]++;
    pln(g, h, n);
    int q;
    cin>>q;
    while(q--) {
        int na; cin>>na;
        cout<<(1-1ll*na*h[na]%MOD+MOD)%MOD<<'\n';
    }
    return 0;
}