首页 > 其他 > 详细

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

时间:2019-10-17 00:45:32      阅读:73      评论:0      收藏:0      [点我收藏+]

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;
}

小结:读题要仔细啊。

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

原文:https://www.cnblogs.com/ShuraK/p/11688274.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!