注册登录

[CF306C]White, Black and White Again_排列组合

White, Black and White Again

题目链接：https://www.luogu.org/problem/CF306C

数据范围：略。

题解：

记得不要看错题，容易看成来回交替下去，其实只有一次。

数据范围实在是特别小，我们就枚举一下中间的黑色是哪些天就好了，复杂度是$O(n^2)$的。

代码：

#include <bits/stdc++.h>

#define setIO(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

const int mod = 1000000009 ;

int fac[4010], inv[4010];

int qpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) {
			ans = (ll)ans * x % mod;
		}
		y >>= 1;
		x = (ll)x * x % mod;
	}
	return ans;
}

inline int C(int x, int y) {
	if (x < y) {
		return 0;
	}
	return (ll)fac[x] * inv[x - y] % mod * inv[y] % mod;
}

int main() {
	// setIO("count");
	int n, w, b;
	cin >> n >> w >> b ;
	fac[0] = 1, inv[0] = 1;
	for (int i = 1; i <= 4000; i ++ ) {
		fac[i] = (ll)fac[i - 1] * i % mod;
		inv[i] = qpow(fac[i], mod - 2);
	}
	int ans = 0;
	for (int i = 2; i <= n; i ++ ) {
		for (int j = i; j < n; j ++ ) {
			// i, j
			ans = (ans + (ll)fac[w] * fac[b] % mod * C(w - 1, n - j + i - 2) % mod * C(b - 1, j - i) % mod) % mod;
		}
	}
	cout << ans << endl ;
	// fclose(stdin);
	// fclose(stdout);
	return 0;
}
知识兔

小结：读题要仔细啊。

计算机