题目描述
Applese打开了m个QQ群，向群友们发出了组队的邀请。作为网红选手，Applese得到了n位选手的反馈，每位选手只会在一个群给Applese反馈
现在，Applese要挑选其中的k名选手组队比赛，为了维持和各个群的良好关系，每个群中都应有至少一名选手成为Applese的队友（数据保证每个群都有选手给Applese反馈）
Applese想知道，他有多少种挑选队友的方案
输入描述:
输入包括两行
第一行包括三个数n, m, k，表示共有n位选手，m个群，需要有k名选手被选择
第二行包括m个数，第i个数表示第i个群有si个选手
n ≤ 100000, m ≤ k ≤ n
输出描述:
输出包括一行
第一行输出方案数
由于输出可能比较大，你只需要输出在模998244353意义下的答案
输入
5 3 4
1 2 2
输出
4
分析
如果一个群有s个人，那么这个群的生成函数就是(sum_{i=1}^{s}C_s^icdot x^i)
这样所有群的多项式乘起来之后，多项式的x的k次幂的系数就是答案了
代码
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=100050;
const int MOD=998244353;
int s[maxn];
ll fact[maxn],inv[maxn];
ll getInv(ll x) {
return x==1?1:getInv(MOD%x)*(MOD-MOD/x)%MOD;
}
void init() {
fact[0]=1;
for(int i = 1; i < maxn; ++i) fact[i]=fact[i-1]*i%MOD;
inv[maxn-1]=getInv(fact[maxn-1]);
for(int i = maxn-2; i >= 0; --i) inv[i]=inv[i+1]*(i+1)%MOD;
}
ll C(int n,int k) {
if(k>n) return 0;
return fact[n]*inv[k]%MOD*inv[n-k]%MOD;
}
vector<int> a[maxn];
struct Cmp {
bool operator ()(const int&u,const int &v)const {
return a[u].size()>a[v].size();
}
};
ll Pow(ll x,ll n) {
ll ans=1,base=x%MOD;
while(n) {
if(n&1) ans=ans*base%MOD;
base=base*base%MOD;
n>>=1;
}
return ans;
}
int t[maxn*2];
void ntt(vector<int>&a,int n,int op) {
for(int i = 0; i < n; ++i) {
int idx=0,base=(n>>1);
for(int j = 0; base; ++j) {
if(i&(1<<j)) idx+=base;
base>>=1;
}
t[idx]=a[i];
}
for(int i = 0; i < n; ++i) a[i]=t[i];
for(int i = 1; i < n; i<<=1) {
ll gn,g=1;
if(op==1) gn=Pow(3,(MOD-1)/i/2);
else gn=Pow(3,(MOD-1)/i/2*(i*2-1));
for(int j = 0; j < n; j+=(i<<1)) {
g=1;
for(int k = j; k < j+i; ++k) {
ll u=a[k],v=a[k+i];
a[k]=(u+g*v)%MOD;
a[k+i]=(u-g*v)%MOD;
g=g*gn%MOD;
}
}
}
if(op==-1) {
ll t=getInv(n);
for(int i = 0; i < n; ++i) {
a[i]=(ll)a[i]*t%MOD;
}
}
}
void mul(vector<int>&a,vector<int>&b) {
int n=1;
while(n<a.size()+b.size()-1) n<<=1;
a.resize(n),b.resize(n);
ntt(a,n,1);
ntt(b,n,1);
for(int i = 0; i < n; ++i) a[i]=(ll)a[i]*b[i]%MOD;
ntt(a,n,-1);
while(a.size()>1&&a.back()==0) a.pop_back();
}
int main() {
init();
ll e1=Pow(3,(MOD-1)/4);
ll e2=Pow(3,(MOD-1)/4*3);
int n,m,k;
scanf("%d%d%d", &n,&m,&k);
priority_queue<int,vector<int>,Cmp> q;
for(int i = 1; i <= m; ++i) {
scanf("%d", s+i);
a[i].resize(s[i]+1);
for(int j = 1; j <= s[i]; ++j) {
a[i][j]=C(s[i],j);
}
q.push(i);
}
while(q.size()>=2) {
int u=q.top();q.pop();
int v=q.top();q.pop();
mul(a[u],a[v]);
q.push(u);
//for(auto e:a[u]) cout<<(e+MOD)%MOD<<" ";
//cout<<endl;
}
int u=q.top();q.pop();
if(k>=a[u].size()) {
printf("0
");
}
else printf("%lld
", ((ll)a[u][k]%MOD+MOD)%MOD);
return 0;
}