题解：AT_agc040_f [AGC040F] Two Pieces

组合意义神仙题……

看其他题解没看懂讲的是什么意思，所以自己写一篇 qwq。

前置知识：隔板法

有

n

个相同的球，放进

m

个不同的盒子里，要求每个盒子不为空，有多少种方法？

答案是

C_{n-1}^{m-1}

。我们可以看做在

n

个球中间插入

m-1

个隔板，因为有

n-1

个空隙，选出

m-1

个，所以答案是

C_{n-1}^{m-1}

。

有

n

个相同的球，放进

m

个不同的盒子里，有多少种方法？

答案是

C_{m+n-1}^{n}

。可以先往每个盒子里放个“假球”，然后用第一类隔板法得到

C_{m+n-1}^{m-1}=C_{m+n-1}^{n}

。（upd on 25.12.02）

本题做法

因为两个棋相同，所以不放设两个棋为

u,v

，且

u \leq v

。

考虑在移动

v

的操作中插入移动

u

的操作。

首先插入令

u

加上

1

的操作，假设有

i

个，我们枚举

i

（考虑始终满足

u \neq v

，把

u=v-1

的操作转为操作二）。根据插板法第一个例子可以知道是

C_{B+i-1}^{i}-C_{B+i-1}^{i-1}

。

然后考虑插入令

u=v

的操作。注意到可以相邻。空位有

n-B-i

个。要插入

A-i

个，根据插板法第二个例子可以知道是

C_{n-B-i+A-i-1}^{A-i}=C_{n+A-B-2i-1}^{A-i}

。

乘起来即可。但是有一个细节：若

i+B=n

，当且仅当

i=A

时有贡献，贡献为

C_{B+i-1}^{i}-C_{B+i-1}^{i-1}

。

最后是

i

的值域。显然是

\min\{A,\min\{B-1,n-B\}\}

。

然后做就行了。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n, a, b, fac[10000005], inv[10000005], ans;
int qpow(int x, int k){
	int ans = 1;
	while (k){
		if (k & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ans;
}
int qmod(int a, int b){
	return a * qpow(b, mod - 2) % mod;
}
int C(int n, int m){
	return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int nmod(int x){
	return (x % mod + mod) % mod;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> a >> b;
	if (!a && !b){
		cout << 1;
		return 0;
	}
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % mod;
	for (int i = 0; i <= n; i++)
		inv[i] = qmod(1, fac[i]);
	for (int i = 0; i <= min(min(a, b - 1), n - b); i++){
		if (n - b - i == 0){
			if (i == a)
				ans = (ans + nmod(C(b + i - 1, i) - C(b + i - 1, i - 1))) % mod;
		}else{
			int qwq = (nmod(C(b + i - 1, i) - C(b + i - 1, i - 1))) % mod;
			ans = (ans + (qwq * C(n + a - b - 2 * i - 1, a - i) % mod)) % mod;
		}
	}
	cout << ans;
	return 0;
}

题解：AT_agc040_f [AGC040F] Two Pieces

文章操作

前置知识：隔板法

本题做法

相关推荐

评论

题解：AT_agc040_f [AGC040F] Two Pieces