E - Count 123
问题核心
用 \(x_1\) 个1，\(x_2\) 个2，\(x_3\) 个3组成一个相邻数最多差1的序列，问多少种组合结果对998244353取模。
思路
经典的组合数取模加逆元问题，只需要考虑怎么组合构造答案就行，先排1和3的位置，分为四种情况
- 1开头1结尾，也就是将1分成 \(i\) 份，3分成\(i-1\)份，其中 \(k = 2i - 2\) 个位置一定需要2，\(i\) 最大是 \(min(x_1,x_3 + 1)\)
- 3开头3结尾，将1分成 \(i-1\) 份，3分成 \(i\) 份，其中 \(k = 2i - 2\) 个位置一定需要2，\(i\) 最大是 \(min(x_1 + 1,x_3)\)
- 1开头3结尾或3开头1结尾，将1和3分成 \(i\) 份，其中 \(k = 2i - 1\) 个位置一定需要2，\(i\) 最大是 \(min(x_1,x_3)\)
确定好1和3的排列情况后，假设 \(x_1 + x_3 = L\) ，接下来要在 \(L + 1\) 个空位里放 \(x_2 - k\) 个 2，因为其中 \(k\) 个位置是必须放的，这是典型的星与条问题，与隔板法的区别看这里，总共\(\binom{L + x_2 - k}{L}\) 种结果，最终答案：
\[\binom{x_1 - 1}{i - 1} \binom{x_3 - 1}{i - 2} \binom{L + x_2 - k}{L} + \binom{x_1 - 1}{i - 2} \binom{x_3 - 1}{i - 1} \binom{L + x_2 - k}{L} + 2\binom{x_1 - 1}{i - 1} \binom{x_3 - 1}{i - 1} \binom{L + x_2 - k}{L}
\]
总结和反思
- 以后遇到把两堆东西排一起的种类，要想到根据开头结尾分类，和看份数的情况。
- 把一堆东西分成几份，每份如果可以为空，就要想到星与条问题
代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 998244353;
const int N = 3e6 + 5;
i64 fact[N], infact[N];i64 ksm(i64 a, i64 b){i64 res = 1;while(b){if(b & 1) res = res * a % mod;b >>= 1;a = a * a % mod;}return res;
}i64 C(i64 a, i64 b){if(a < 0 || b < 0 || b > a) return 0; //非法组合数return fact[a] * infact[b] % mod * infact[a - b] % mod;
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);i64 x1, x2, x3;cin >> x1 >> x2 >> x3;fact[0] = 1, infact[0] = 1; //单独处理0的情况for (int i = 1; i < N; i++){fact[i] = fact[i - 1] * i % mod;}infact[N - 1] = ksm(fact[N - 1], mod - 2);for (int i = N - 2; i >= 1; i--){infact[i] = infact[i + 1] * (i + 1) % mod;}i64 n = x1 + x2 + x3, L = x1 + x3;i64 ans = 0;for (int i = 1; i <= min(x1, x3 + 1); i++){i64 k = 2 * i - 2;ans = (ans + C(x1 - 1, i - 1) * C(x3 - 1, i - 2) % mod * C(n - k, L) % mod) % mod;}for (int i = 1; i <= min(x1, x3); i++){i64 k = 2 * i - 1;ans = (ans + C(x1 - 1, i - 1) * C(x3 - 1, i - 1) % mod * C(n - k, L) % mod * 2 % mod) % mod;}for (int i = 1; i <= min(x1 + 1, x3); i++){i64 k = 2 * i - 2;ans = (ans + C(x1 - 1, i - 2) * C(x3 - 1, i - 1) % mod * C(n - k, L) % mod) % mod;}cout << ans << "\n";
}