CF1931G
思路
观察可得,要拼出合法序列只有12交替同时34插入12和21之间;
当1和2的相差超过1时,多出来拼图的无法拼接成合法序列,所以答案是0;
当1和2都为0时,只有3或者只有4的情况答案是1,其他情况答案是0;
当1比2多一个时:
只能是前后都是1,比如1 2 1 2 1,
观察得,3只能插在1的后面,4只能插在1的前面,3和4的插法是独立的
所以3的插法就是用c个物品放入a个盒中且允许空盒的方案数,把问题转化一下,我们先在a个盒子里分别放入1个物品,然后再按前面的方法入盒子,这样就把问题转化成用a + c个物品放入a个盒子中且不允许空盒的方案数,用隔板法得\(C_{a + c - 1}^{a - 1} = C_{a + c - 1}^{a}\)
同理4的插法就是\(C_{a + d - 1}^{a - 1} = C_{a + d - 1}^{d}\)
所以当1比2多一个时总方案数就是\(C_{a + c - 1}^{a}*C_{a + d - 1}^{d}\)
同理,当2比1多1时:
总方案数是\(C_{b + c - 1}^{c}*C_{b + d - 1}^{d}\)
当1和2一样多时:
如果是1在前,那么3的插法有\(C_{a + c - 1}^{c}\),4的插法有\(C_{a+d}^{d}\)
如果是2在前,那么3的插法用\(C_{a + c}^{c}\),4的插法有\(C_{a + d - 1}^{d}\)
总方案数就是\(C_{a + c - 1}^{c}*C_{a+d}^{d}+C_{a + c}^{c}*C_{a + d - 1}^{d}\)
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int P = 998244353;
const int N = 4e6 + 10;
i64 f[N], g[N];
i64 qpow(i64 a, i64 b) {
i64 res = 1;
while(b){
if(b & 1) res = res * a % P;
a = a * a % P;
b >>= 1;
}
return res;
}
void init(){
f[0] = g[0] = 1;
for(int i = 1; i <= N; i++) {
f[i] = f[i-1] * i % P;
g[i] = g[i-1] * qpow(i, P-2) % P;
}
}
i64 getC(i64 n, i64 m){
if (n < m || n < 0 || m < 0) return 0;
return f[n] * g[m] % P * g[n-m] % P;
}
void solve() {
i64 a, b, c, d;
cin >> a >> b >> c >> d;
if (a == 0 && b == 0) {
if (c && d) cout << 0 << endl;
else cout << 1 << endl;
} else if (a == b) {
i64 ans = getC(a + c - 1, c) * getC(a + d, d) + getC(a + c, c) * getC(a + d - 1, d);
cout << ans % P << endl;
} else if (a - b == 1) {
i64 ans = getC(a + c - 1, c) * getC(a + d - 1, d);
cout << ans % P << endl;
} else if (b - a == 1) {
i64 ans = getC(b + c - 1, c) * getC(b + d - 1, d);
cout << ans % P << endl;
} else cout << 0 << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
标签:i64,const,插法,int,res,Puzzle,CF1931G,Dimensional
From: https://www.cnblogs.com/kichuan/p/18017129