P5339

发表于 更新于 分类于
[TJOI2019]唱、跳、rap和篮球

[TJOI2019]唱、跳、rap和篮球

考虑钦定法。

令 $f(k)$ 表示钦定 $k$ 组人讨论 Cxk，$g(k)$ 表示恰好有 $k$ 组人讨论 Cxk。

很容易由组合意义得到：

$$f(k)=\sum _ {i=k} \binom{i}{k} g(i)$$

由二项式反演：

$$g(k) = \sum _ {i=k} (-1) ^ {i-k} \binom{i}{k} f(i)$$

然后我们现在要求的就是 $g(0)$，于是：

$$g(0) = \sum _ {i=0} (-1) ^ {i} f(i)$$

现在考虑如何计算 $f(k)$。

令 $S(a,b,c,d,n)$ 表示有 $a$ 个人喜欢唱，$b$ 个人喜欢跳，$c$ 个人喜欢 rap，$d$ 个人喜欢篮球，队列长度为 $n$ 的排列方案数。

那么就有：

$$f(k)= \binom{n-3k}{k} S ( a-k , b-k , c-k ,d-k , n - 4k)$$

前面的组合数表示我们先从队列中扣掉 $3k$ 个人，这样我们每选中一个人就在后面加入三个人使这个位置被钦定讨论 Cxk。

然后我们就要考虑 $S(a,b,c,d,n)$ 如何求。

考虑使用 EGF，定义 $\hat{R} _ k (x)= \sum _ {i=0} ^ {k} x ^ i / i !$，那么我们的答案就是：

$$S(a,b,c,d,n) = n! [ x ^ n / n! ] \hat{R} _ a (x) \hat{R} _ b (x) \hat{R} _ c (x) \hat{R} _ d (x)$$

这个可以直接 NTT 卷积。

然后就是这里注意运算要在模 $x^n$ 下，所以系数不要赋多了。。。

时间复杂度 $O(n ^ 2 \log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define Clr(f,n) memset(f,0,sizeof(ll)*n)
#define Cpy(f,g,n) memcpy(f,g,sizeof(ll)*n)
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e5,mo=998244353,G=3;

inline ll Pow(ll b,ll p) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

const ll invG=Pow(G,mo-2);

ll n,a,b,c,d,ans;
ll f[N+5],fac[N+5],invfac[N+5],rev[N+5];
ll g[N+5];

inline void Prev(ll n) {
  for(ll i=0;i<n;i++) {rev[i]=0;rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);}
}

inline void NTT(ll *f,ll n,bool op) {
  Prev(n);for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=f[l+len]*buf%mo;
        f[l+len]=f[l]-t;if(f[l+len]<0) f[l+len]+=mo;
        f[l]=f[l]+t;if(f[l]>=mo) f[l]-=mo;
      }
    }
  }
  if(op) {
    ll invn=Pow(n,mo-2);for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;
  }
}

inline void Times(ll *f,ll *g,ll len,ll lim) {
  ll n=1;for(;n<=(len<<2);n<<=1);
  NTT(f,n,0);NTT(g,n,0);
  for(ll i=0;i<n;i++) f[i]=f[i]*g[i]%mo;
  NTT(f,n,1);Clr(f+lim,n-lim);
}

inline void Init() {
  fac[0]=1;for(ll i=1;i<=N;i++) fac[i]=fac[i-1]*i%mo;
  invfac[0]=1;invfac[N]=Pow(fac[N],mo-2);
  for(ll i=N-1;i>=1;i--) invfac[i]=invfac[i+1]*(i+1)%mo;
}

inline ll C(ll n,ll m) {return (fac[n]*invfac[m]%mo)*invfac[n-m]%mo;}

inline ll S(ll a,ll b,ll c,ll d,ll n) {
  static ll f[N+5],g[N+5];n+=5;
  for(ll i=0;i<=a&&i<n;i++) f[i]=invfac[i];
  for(ll i=0;i<=b&&i<n;i++) g[i]=invfac[i];Times(f,g,n,n);Clr(g,N);
  for(ll i=0;i<=c&&i<n;i++) g[i]=invfac[i];Times(f,g,n,n);Clr(g,N);
  for(ll i=0;i<=d&&i<n;i++) g[i]=invfac[i];Times(f,g,n,n);Clr(g,N);
  ll tmp=f[n-5]*fac[n-5]%mo;Clr(f,N);return tmp;
}

int main() {

  n=read();a=read();b=read();c=read();d=read();
  Init();

  for(ll i=0;i<=n;i++) {
    if(i>a||i>b||i>c||i>d||4*i>n) break;
    f[i]=C(n-3*i,i)*S(a-i,b-i,c-i,d-i,n-4*i)%mo;
  }

  for(ll i=0;i<=n;i++) {
    if(i&1) {ans=(ans-f[i]+mo)%mo;}
    else {ans=(ans+f[i])%mo;}
  }

  write(ans);

  return 0;
}