link

contest link

考场上推出来了式子,手算样例算错,然后扔了,赛后发现算错,重算了一遍发现是对的。

「你每次会等概率随机选一个没有满的燃料舱」

考虑也可以选择满了的燃料舱,这不会影响答案

这样每次选每个燃料舱的概率都是一样的。

考虑枚举最后一个到b的燃料舱,再枚举一个满了的燃料舱计算方案数

记$S(i)=\frac{\frac{x}{n}^i}{i!}$

满了的方案数的指数生成函数为$e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)$

其它的不一定满,方案数为$e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i)$

最后这个燃料舱的第b次操作一定在最后,所以$\cdot \frac{1}{n}$然后只考虑前面的操作$S(b-1)$

那么满足条件的概率的指数生成函数为$(n-1)(e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i))(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}S(b-1)$

设生成函数为$F(x)=\sum \frac{a_ix^i}{i!}$,则设$G(x)=\sum a_ix^i$,答案为$G(1)$,也就是$\sum a_i$。

考虑计算这个函数。

由于exp很难处理,考虑把式子展开成$\sum e^{\frac{ix}{n}}F_i(x)$的形式。

先考虑$(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}$,则答案是$\sum_{i=0}^{n-2}\binom{n-2}{i}e^{\frac{ix}{n}}(-\sum_{i=0}^{b-1}S(i))^{n-2-i}$,

乘上$e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)$也类似。

由于得到的多项式次数$\lt na$,所以可以先DFT,乘完再IDFT

这一部分的复杂度是$O(n^2a\log(na))$,也就是$n$次IDFT的复杂度。

考虑计算答案。生成函数可以拆成$c\cdot e^{ax}\frac{x^b}{b!}$的形式,对于每个这种式子计算答案。

$e^{ax}\frac{x^b}{b!}=\sum_{i=0}^{\infty}\frac{a^ix^{i+b}}{i!b!}=\sum_{i=0}^{\infty}a^{i}\binom{i+b}{i}\frac{x^{i+b}}{(i+b)!}$

那么得到的普通型生成函数为$\sum_{i=0}^{\infty}\binom{i+b}{i}a^ix^{i+b}=\frac{x^b}{(1-ax)^{b+1}}$。

于是做完了。

代码(已define int long long):

const int p=998244353,G=114514;
int inv[62505],fac[62505],invf[62505],pw[62505];
int cnt[255],n,a,b,s,k,ans,w=1;
int f[255][65537],iN,N;
int fpm(int a,int b){
    int c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
int f1[65537],f2[65537];
int _w[1<<17|5],rev[1<<16|5];
int Sum(int a,int b){return (a+=b)>=p?a-p:a;}
void dft(int *a){
    for(int i=0;i<N;++i)if(i>rev[i])swap(a[i],a[rev[i]]);
    for(int i=1;i<N;i<<=1){
        for(int j=0;j<N;j+=i+i){
            for(int k=0;k<i;++k){
                int u=a[j+k],v=a[j+k+i]*_w[k+i]%p;
                a[j+k]=Sum(u,v);
                a[j+k+i]=Sum(u,p-v);
            }
        }
    }
}
void idft(int *a){
    reverse(a+1,a+N);
    dft(a);
    for(int i=0;i<N;++i)a[i]=a[i]*iN%p;
}
signed main(){
#ifdef QAQAutoMaton 
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    read(n,a,b);
    int w=(a-1)+(n-1)*b;
    fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
    for(int i=2;i<=w;++i){
        fac[i]=fac[i-1]*i%p;
        inv[i]=(p-p/i)*inv[p%i]%p;
        invf[i]=inv[i]*invf[i-1]%p;
    }
    int in=inv[n];
    pw[0]=1;
    for(int i=1;i<=w;++i){
        pw[i]=pw[i-1]*in%p;
    }
    N=1;
    while(N<=w)N<<=1;
    for(int i=1;i<N;i<<=1){
        int ww=fpm(G,(p+1)/(i<<1)),w=1;
        for(int j=0;j<i;++j){
            _w[i+j]=w;
            w=w*ww%p;
        }
    }
    for(int i=1;i<N;++i){
        rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
    }
    iN=fpm(N,p-2);
    for(int i=0;i<b;++i)f1[i]=p-pw[i]*invf[i]%p;
    for(int i=0;i<a;++i)f2[i]=p-pw[i]*invf[i]%p;

    dft(f1);dft(f2);
    for(int i=0;i<N;++i)f[0][i]=1;
    for(int i=1;i<=n-2;++i){
        for(int j=0;j<N;++j)f[i][j]=f[i-1][j]*f1[j]%p;
    }
    for(int i=0;i<=n-2;++i){
        int C=fac[n-2]*invf[i]%p*invf[n-2-i]%p;
        for(int j=0;j<N;++j)f[i][j]=f[i][j]*C%p;
    }
    for(int i=n-2;~i;--i){
        for(int j=0;j<N;++j)f[i+1][j]=(f[i+1][j]+f[i][j]*f2[j])%p;
    }
    for(int i=0;i<=n-1;++i){
        idft(f[i]);
    }
    for(int i=0;i<=n-1;++i){
        int wx=n*inv[i+1]%p,cur=invf[b-1]*pw[b-1]%p;
        for(int j=0;j<b-1;++j)cur=cur*wx%p;
        for(int j=0;j<=w;++j){
            cur=cur*wx%p;
            ans=(ans+f[i][j]*fac[j+b-1]%p*cur)%p;
        }
    }
    write(ans*(n-1)%p,'\n');
    return 0;
}

标签: 计数

已有 2 条评论

  1. 最后的函数的分母是(1-ax)^(b+1)吧(

添加新评论