Codeforces 960G：Bandit Blues（倍增FFT/第一类斯特林数）

传送门

题解：
答案等于$begin{bmatrix} n-1 \ a+b-2 end{bmatrix} *binom{a+b-2}{a-1}$

将最多的袋子剔除后，每个能看到的袋子与他挡住的袋子形成圆排列。我们从这$a+b-2$个圆排列中取出$a-1$个放到左边。

注意$begin{bmatrix} n \ m end{bmatrix} = [x^m] x^{ overline{n}}$ 。我们直接求$x^{overline{n}}$即可。

$O(n log^2 n)$可以启发式合并多项式。

可以$O(n log n)$，记$l = frac{n}{2}$。我们先求$x^overline{l}$，得到：

$$F=sum_{i=0}^la_ix^i$$
要求 $$G =sum_{i=0}^n a_i (x+l)^i$$
二项式展开：
$$begin{aligned} G &=sum_{i=0}^n a_i(x+l)^i \&=sum_{i=0}^na_isum_{j=0}^i binom{i}{j}x^jl^{i-j} \&=sum_{j=0}^nx_j sum_{i=j}^n binom{i}{j}a_il^{i-j} end{aligned}$$

记$b_i = frac{[x^i] G}{j!}, A_i = a_ii!, B_i = frac{l^j}{j!}$，那么：

$$b_j = sum_{i=j}^nA_iB_{i-j}$$

我们把$B$reverse，发现这就是个卷积形式，直接迭代下去做即可，时间复杂度：
$T(n) = T(frac{n}{2}) + O(n log n) = O(n log n)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int RLEN=1<<18|1;
inline char nc() {
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
    char ch=nc(); int i=0,f=1;
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
    while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
    return i*f;
}
inline void W(int x) {
    static int buf[50];
    if(!x) {putchar('0'); return;}
    if(x<0) {putchar('-'); x=-x;}
    while(x) {buf[++buf[0]]=x%10; x/=10;}
    while(buf[0]) {putchar(buf[buf[0]--]+'0');}
}

const int N=8e5+50, mod=998244353, G=3;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<0) ? (x-y+mod) : (x-y);}
inline int mul(int x,int y) {return (LL)x*y%mod;}
inline int power(int a,int b,int rs=1) {for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a); return rs;}

int n,A,B,k,pos[N],w[N],a[N],b[N],tp[N],fac[N],ifac[N],pw[N];
inline int C(int ai,int bi) {
    if(ai<bi) return 0; 
    return mul(fac[ai],mul(ifac[bi],ifac[ai-bi]));
}
inline void init(int len) {
    for(k=1;k<=len;k<<=1);
    for(int i=1;i<k;i++) pos[i]=(i&1) ? ((pos[i>>1]>>1)^(k>>1)) : (pos[i>>1]>>1);
}
inline void dft(int *ai) {
    for(int i=1;i<k;i++) if(pos[i]>i) swap(ai[pos[i]],ai[i]);
    for(int bl=1;bl<k;bl<<=1) {
        int tl=bl<<1, wn=power(G,(mod-1)/tl);
        w[0]=1; for(int i=1;i<bl;i++) w[i]=mul(w[i-1],wn);
        for(int bg=0;bg<k;bg+=tl)
            for(int j=0;j<bl;++j) {
                int &t1=ai[bg+j],&t2=ai[bg+j+bl],t=mul(t2,w[j]);
                t2=dec(t1,t); t1=add(t1,t);
            }
    }
}
inline void mul(int *ai,int *bi) {
    dft(ai); dft(bi);
    for(int i=0;i<k;i++) bi[i]=mul(ai[i],bi[i]);
    dft(bi); reverse(bi+1,bi+k);
    const int inv=power(k,mod-2);
    for(int i=0;i<k;i++) bi[i]=mul(bi[i],inv);
}
inline void solve(int len ) {
    if(len==1) {a[1]=1; return;}
    if(len&1) {
        solve(len-1);
        for(int i=len;i>=1;i--) a[i]=add(a[i-1],mul(a[i],len-1)); 
    } else {
        solve(len>>1); int l2=len/2; pw[0]=1; 
        init(len);
        for(int i=1;i<=l2;i++) pw[i]=mul(pw[i-1],l2);
        for(int i=0;i<=l2;i++) tp[i]=mul(a[i],fac[i]);
        for(int i=0;i<=l2;i++) b[i]=mul(pw[i],ifac[i]);
        for(int i=l2+1;i<k;i++) tp[i]=b[i]=0;
        reverse(b,b+l2+1);
        mul(tp,b); 
        for(int i=0;i<=l2;i++) b[i]=b[i+l2], b[i]=mul(b[i],ifac[i]);
        for(int i=l2+1;i<k;i++) b[i]=0;
        mul(b,a);
    }
}
int main() {
    n=rd(), A=rd(), B=rd();
    if(n==1) {cout<<(A==1 && B==1); return 0;}
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
    ifac[n]=power(fac[n],mod-2);
    for(int i=n-1;~i;i--) ifac[i]=mul(ifac[i+1],i+1);
    solve(n-1); 
    cout<<mul(a[A+B-2],C(A+B-2,A-1));
}

最后

以上就是怕孤单黄蜂为你收集整理的Codeforces 960G：Bandit Blues（倍增FFT/第一类斯特林数）的全部内容，希望文章能够帮你解决Codeforces 960G：Bandit Blues（倍增FFT/第一类斯特林数）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。