Wannafly挑战赛20D挑选队友题解

题意：

有m组，每组s_i个人(两两不同)，满足 $\Sigma_{i=1}^ms_i=n$ ，求有多少种方案使得在每组中至少挑一人，可以凑出k个人来。

思路：

n≤10⁵说明这个数据范围支持log方的做法

考虑对每组都单独做一个生成函数

第j组的生成函数为 $F_j(x)=\Sigma_{i=1}^{s_j}C(s_j,i)*x^i$ ，

这样的a_ixⁱ表示的是选i个人时有a_i种方案，

对于任意F_j(x)中的a₀=0可以满足每组中至少挑一人的要求。

因此答案为 $[x^k]\Pi_{i=1}^mF_i(x)$ ，

就是把所有生成函数乘起来，取第k项系数，即为答案。

这里的多项式乘法可以做分治FFT

复杂度为O(n*logn*logm)

内容板块

数学：生成函数多项式分治FFT

#include<cstdio>
#include<iostream>
#include<algorithm>
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#define _rep(i,s,t) for(register int i=s;i>=t;--i)
#define Rep(i,s,t) for(register int i=s;i<t;++i)
#define go(x) for(register int e=las[x];e;e=nxt[e])
#define re register
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define insert is
#define erase es
#define pii pair<int,int>
#define ms(f,x) memset(f,x,sizeof f)
#define mc(f,x) memcpy(f,x,sizeof f)
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define gi(x) read(x)
#define gii(x,y) read(x),read(y)
#define giii(x,y,z) read(x),read(y),read(z)
namespace IO{
    #define gc getchar()
    #define pc(x) putchar(x)
    template<typename T>inline void read(T &x){
        x=0;int f=1;char ch=gc;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=gc;}
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc;x*=f;return;
    }
    template<typename T>inline void write(T x=0){
        T wr[51];wr[0]=0;if(x<0)pc('-'),x=-x;if(!x)pc(48);
        while(x)wr[++wr[0]]=x%10,x/=10;while(wr[0])pc(48+wr[wr[0]--]);return;
    }
}
using IO::read;
using IO::write;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const int N=8e5+11,mod=998244353;
int n,m,k;
int s[N],sum[N],p[N],fac[N];
inline int fp(int a,int b){
    if(b<0)b+=mod-1;
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1)
            res=1ll*res*a%mod;
    return res;
}
inline void dft(int *a,int n,int f){
    Rep(i,0,n)
        if(i<p[i])
            swap(a[i],a[p[i]]);
    for(re int i=1;i<n;i<<=1){
        int gn=fp(3,((mod-1)/(i<<1))*f);
        for(re int j=0,w;w=1,j<n;j+=(i<<1))
            for(re int k=j,x,y;k<i+j;++k,w=1ll*w*gn%mod){
                x=a[k],y=1ll*w*a[i+k]%mod;
                a[k]=(x+y)%mod,a[i+k]=(x-y+mod)%mod;
            }
    }
    if(f==-1){
        re int inv=fp(n,mod-2);
        Rep(i,0,n)
            a[i]=1ll*a[i]*inv%mod;
    }
}
inline int C(int n,int m){
    return 1ll*fac[n]*fp(1ll*fac[m]*fac[n-m]%mod,mod-2)%mod;
}
inline void solve(int *A,int l,int r){
    if(l==r){
        rep(i,1,s[l]){
            int res=C(s[l],i);
            A[i]=res;
        }
        A[0]=0;
        return ;
    }
    int mid=(l+r)>>1;
    int B[(sum[r]-sum[l-1])<<1|1];
    rep(i,0,(sum[r]-sum[l-1])*2)
        B[i]=0;
    solve(A,l,mid),solve(B,mid+1,r);
    int d,lg;
    for(d=1,lg=-1;d<=sum[r]-sum[l-1];d<<=1,++lg);
    rep(i,0,d-1)
        p[i]=(p[i>>1]>>1)^((i&1)<<lg);
    dft(A,d,1),dft(B,d,1);
    /*
    puts("A");
    rep(i,0,d-1)
        printf("%d ",A[i]);puts("");
    
    puts("B");
    rep(i,0,d-1)
        printf("%d ",B[i]);puts("");*/
    rep(i,0,d-1)
        A[i]=1ll*B[i]*A[i]%mod;
    /*puts("A");
    rep(i,0,d-1)
        printf("%d ",A[i]);puts("");*/
    dft(A,d,-1);
    /*puts("A");
    rep(i,0,d-1)
        printf("%d ",A[i]);puts("");*/
}
int ans[N];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,m)
        scanf("%d",s+i),sum[i]=sum[i-1]+s[i];
    fac[0]=1;rep(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
    solve(ans,1,m);
    printf("%d\n",ans[k]);
    return 0;
}