文章目錄

• 題目
• 題解
• code1（NTT）
• code2（EGF+卷積）

題目

大中鋒的學院要組織學生參觀博物館，要求學生們在博物館中排成一隊進行參觀。他的同學可以分為四類：一部分最喜歡唱、一部分最喜歡跳、一部分最喜歡rap，還有一部分最喜歡籃球。如果隊列中$k,k+1,k+2,k+3$位置上的同學依次，最喜歡唱、最喜歡跳、最喜歡rap、最喜歡籃球，那么他們就會聚在一起討論蔡徐坤。大中鋒不希望這種事情發生，因為這會使得隊伍顯得很亂。大中鋒想知道有多少種排隊的方法，不會有學生聚在一起討論蔡徐坤。兩個學生隊伍被認為是不同的，當且僅當兩個隊伍中至少有一個位置上的學生的喜好不同。由于合法的隊伍可能會有很多種，種類數對998244353取模。

輸入格式
輸入數據只有一行。每行5個整數，第一個整數n，代表大中鋒的學院要組織多少人去參觀博物館。接下來四個整數a、b、c、d，分別代表學生中最喜歡唱的人數、最喜歡跳的人數、最喜歡rap的人數和最喜歡籃球的人數。保證$a+b+c+d\ge n$。

輸出格式
每組數據輸出一個整數，代表你可以安排出多少種不同的學生隊伍，使得隊伍中沒有學生聚在一起討論蔡徐坤。結果對$998244353$取模。

輸入輸出樣例
輸入
4 4 3 2 1
輸出
174

輸入
996 208 221 132 442
輸出
442572391

說明/提示
對于20%的數據，有$n=a=b=c=d\le 500$
對于100%的數據，有$n\le 1000$ ， $a,b,c,d\le 500$

題解

考慮枚舉有$i$堆人在討論cxk小姐姐，那么被cxk迷倒的人就有$4i$個，且每一堆人是挨在一起的，
所以我們可以把這$4i$個人縮成$i$個群體，每一個群體可以展開成為$4$人
那么現在就只用考慮剩下的$n?3i$人，放置的方案數就是$$C_{n?3i}^i$$
簡單用整體法證明一下：
在$n?3i$人中，要選$i$個拿來討論，$n?4i$個不討論，方案數是對應的$$C_{n?3i}^i=C_{n?3i}^{n?4i}$$
也可以理解為在$n?3i$個空格里面找$i$個起點開始討論小姐姐

---

接著枚舉好了$i$及它們可能出現的地方$C_{n?3i}^i$，我們就要去考慮剩下$n?4i$人的排列，可以亂來
$$(n?4i)!$$
但是$attention$，如果看了我的上一篇指數型生成函數專練，就會與這里有一點相通
題目說的方案數不同的要求是至少有一個位置上的學生的喜好不同，而不是學生本人不同
所以我們要除掉喜好籃球，跳舞，唱歌，rap本身內部的亂拍，因為從愛好上來看是看不出來排列不同的
設$a,b,c,d$分別代表學生中最喜歡唱的人數、最喜歡跳的人數、最喜歡rap的人數和最喜歡籃球的總人數，我們考慮的是剩下的不討論cxk姐姐的學生亂排，所以要剪掉外層所枚舉的去參與討論的人數
$$\frac{(n?4i)!}{(a?i)!(n?i)!(c?i)!(d?i)!}$$

---

最后寫出每種喜好的生成函數，以喜歡籃球的人為例：
$$\sum _{i=0}^c\frac{x^i}{i!}$$
把四種愛好卷起來，卷出最后乘積的第$n?4i$項就是我們需要除掉的東西，乘上$(n?4i)!$就是真正的亂排數

---

因為帶取模，所以是用$NTT$跑，除的話就要變成乘逆元，所以我們可以在卷的時候就直接卷逆元

但是我們又發現雖然假設的是$i$堆人在討論，但是統計答案的時候卻把$\ge i$堆人討論的情況都統計了
而且當統計$i=1$時，會算兩遍至少兩堆人討論的方案，三遍至少三堆人討論的方案…在統計$i=2$時，會算三遍至少三堆人討論的方案…
當統計$i$的方案時，會多算$C_j^i$次至少$j$堆人討論的方案，所以我們可以用容斥來解決

---

總結一下答案應該是
$$\sum _{i=0}^{min}(?1{)}^i?C_{n?3i}^i?\frac{(n?4i)!}{(a?i)!(n?i)!(c?i)!(d?i)!}$$

code1（NTT）

#include <cstdio> #include <iostream> using namespace std; #define mod 998244353 #define LL long long #define MAXN 10005 int n, anum, bnum, cnum, dnum; LL pi, ni, result; LL a[MAXN], b[MAXN], c[MAXN], d[MAXN], rev[MAXN], fac[MAXN], Invfac[MAXN];LL qkpow ( LL x, LL y ) {LL ans = 1;while ( y ) {if ( y & 1 )ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }LL C ( int n, int m ) {return fac[n] * Invfac[m] % mod * Invfac[n - m] % mod; }void NTT ( LL *c, LL limit, LL f ) {for ( LL i = 0;i < limit;i ++ )if ( i < rev[i] )swap ( c[i], c[rev[i]] );for ( LL i = 1;i < limit;i <<= 1 ) {LL omega = qkpow ( f == 1 ? pi : ni, ( mod - 1 ) / ( i << 1 ) );for ( LL j = 0;j < limit;j += ( i << 1 ) ) {LL w = 1;for ( LL k = 0;k < i;k ++, w = w * omega % mod ) {LL x = c[k + j], y = w * c[i + j + k] % mod;c[k + j] = ( x + y ) % mod;c[k + j + i] = ( x - y + mod ) % mod;}}}LL inv = qkpow ( limit, mod - 2 );if ( f == -1 )for ( LL i = 0;i < limit;i ++ )c[i] = c[i] * inv % mod; }void init () {Invfac[0] = fac[0] = 1;for ( int i = 1;i <= n;i ++ )fac[i] = fac[i - 1] * i % mod;Invfac[n] = qkpow ( fac[n], mod - 2 );for ( int i = n - 1;i;i -- )Invfac[i] = Invfac[i + 1] * ( i + 1 ) % mod; }LL solve ( int n, int A, int B, int C, int D ) {LL len = 1, l = 0;while ( len < ( ( A + B + C + D ) << 1 ) ) {len <<= 1;l ++;}for ( LL i = 0;i < len;i ++ )rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << ( l - 1 ) );for ( int i = 0;i < len;i ++ )a[i] = ( i <= A ? Invfac[i] : 0 );for ( int i = 0;i < len;i ++ )b[i] = ( i <= B ? Invfac[i] : 0 );for ( int i = 0;i < len;i ++ )c[i] = ( i <= C ? Invfac[i] : 0 );for ( int i = 0;i < len;i ++ )d[i] = ( i <= D ? Invfac[i] : 0 );NTT ( a, len, 1 );NTT ( b, len, 1 );NTT ( c, len, 1 );NTT ( d, len, 1 );for ( int i = 0;i < len;i ++ )a[i] = a[i] * b[i] % mod * c[i] % mod * d[i] % mod;NTT ( a, len, -1 );return a[n] * fac[n] % mod; }int main() {pi = 3;ni = mod / pi + 1;scanf ( "%d %d %d %d %d", &n, &anum, &bnum, &cnum, &dnum );init();int k = min ( min ( min ( min ( anum, bnum ), cnum ), dnum ), n / 4 );anum -= k;bnum -= k;cnum -= k;dnum -= k;result = 0;for ( k;k >= 0;k -- ) {LL tmp = C ( n - 3 * k, k ) % mod * solve ( n - 4 * k, anum, bnum, cnum, dnum ) % mod;anum ++;bnum ++;cnum ++;dnum ++;result = ( result + ( ( k & 1 ) ? mod - tmp : tmp ) ) % mod;}printf ( "%lld\n", result );return 0; }

code2（EGF+卷積）

#include <cstdio> #include <iostream> using namespace std; #define mod 998244353 #define LL long long #define MAXN 1005 int n, a, b, c, d; LL result; LL foldAB[MAXN], foldCD[MAXN], fac[MAXN], Invfac[MAXN];LL qkpow ( LL x, LL y ) {LL ans = 1;while ( y ) {if ( y & 1 )ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }LL C ( int n, int m ) {return fac[n] * Invfac[m] % mod * Invfac[n - m] % mod; }void Fac () {Invfac[0] = fac[0] = 1;for ( int i = 1;i <= n;i ++ )fac[i] = fac[i - 1] * i % mod;Invfac[n] = qkpow ( fac[n], mod - 2 );for ( int i = n - 1;i;i -- )Invfac[i] = Invfac[i + 1] * ( i + 1 ) % mod; }int main() {scanf ( "%d %d %d %d %d", &n, &a, &b, &c, &d );Fac();int k = min ( min ( min ( min ( a, b ), c ), d), n / 4 );a -= k;b -= k;c -= k;d -= k;for ( int i = 0;i <= a;i ++ )for ( int j = 0;j <= b;j ++ )foldAB[i + j] = ( foldAB[i + j] + Invfac[i] * Invfac[j] % mod ) % mod;for ( int i = 0;i <= c;i ++ )for ( int j = 0;j <= d;j ++ )foldCD[i + j] = ( foldCD[i + j] + Invfac[i] * Invfac[j] % mod ) % mod;result = 0;for ( k;k >= 0;k -- ) {LL ans = 0;int tp = n - 4 * k;for ( int i = 0;i <= tp;i ++ )ans = ( ans + foldAB[i] * foldCD[tp - i] % mod ) % mod;ans = ans * fac[tp] % mod * C ( n - k * 3, k ) % mod;result = ( result + ( ( k & 1 ) ? mod - ans : ans ) ) % mod;a ++;b ++;c ++;d ++;for ( int i = 0;i <= a;i ++ )foldAB[i + b] = ( foldAB[i + b] + Invfac[i] * Invfac[b] % mod ) % mod;for ( int i = 0;i <= b;i ++ )foldAB[i + a] = ( foldAB[i + a] + Invfac[i] * Invfac[a] % mod ) % mod;foldAB[a + b] = ( foldAB[a + b] - Invfac[a] * Invfac[b] % mod + mod ) % mod;for ( int i = 0;i <= c;i ++ )foldCD[i + d] = ( foldCD[i + d] + Invfac[i] * Invfac[d] % mod ) % mod;for ( int i = 0;i <= d;i ++ )foldCD[i + c] = ( foldCD[i + c] + Invfac[i] * Invfac[c] % mod ) % mod;foldCD[c + d] = ( foldCD[c + d] - Invfac[c] * Invfac[d] % mod ) % mod;}printf ( "%lld\n", result );return 0; }

代碼或者思路有任何問題歡迎評論

總結

以上是生活随笔為你收集整理的[TJOI2019]唱、跳、rap和篮球（指数型生成函数+NTT+卷积）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。