QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73671#1245. Three ballsWUZRWWA 2ms5420kbC++142.2kb2023-01-27 15:37:592023-01-27 15:38:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-27 15:38:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5420kb
  • [2023-01-27 15:37:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int mod = 1e9 + 7, N = 10005;
int n, fac[N], inv[N], sum[N][N];
char a[N], b[N], c[N];
int add(int x, int y) {
	return (x += y) < mod ? x : x - mod;
}
void upd(int &x, const int &y) {
	if ((x += y) >= mod) x -= mod;
}
void upd(int &x, const ll &y) {
	x = (x + y) % mod;
}
int C(int n, int m) {
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int ksm(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}
int calc(int r1, char *a, int r2, char *b) {
	int c0 = 0, c1 = 0, ans = 0;
	static int sum[N];
	rep(i, 1, n) (a[i] == b[i] ? c0 : c1)++;
	rep(i, 0, c1) sum[i] = C(c1, i);
	rep(i, 1, c1) upd(sum[i], sum[i - 1]);
	for (int i = 0; i <= c0 && i <= r1 && i <= r2; i++) {
		int l = max(c1 + i - r2, 0), r = min(r1 - i, c1);
		if (l > r) break;
		upd(ans, 1ll * C(c0, i) * (sum[r] + (l ? mod - sum[l - 1] : 0)));
	}
	return ans;
}
signed main() {
	int r1, r2, r3, c1 = 0, c2 = 0, c3 = 0, c4 = 0, ans = 0;
	cin >> n >> r1 >> a + 1 >> r2 >> b + 1 >> r3 >> c + 1;
	fac[0] = fac[1] = 1;
	rep(i, 2, n) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = ksm(fac[n], mod - 2);
	per(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	rep(i, 0, r1) upd(ans, C(n, i));
	rep(i, 0, r2) upd(ans, C(n, i));
	rep(i, 0, r3) upd(ans, C(n, i));
	upd(ans, mod - calc(r1, a, r2, b));
	upd(ans, mod - calc(r2, b, r3, c));
	upd(ans, mod - calc(r3, c, r1, a));
	rep(i, 1, n)
	if (a[i] == b[i] && b[i] == c[i]) c4++;
	else if (b[i] == c[i]) c1++;
	else if (a[i] == c[i]) c2++;
	else if (a[i] == b[i]) c3++;
	rep(i, 0, c3)
	rep(j, 0, c4) sum[i + j][j - i + c3] = 1ll * C(c3, i) * C(c4, j) % mod;
	rep(i, 0, c3 + c4)
	rep(j, 1, c3 + c4) upd(sum[i][j], sum[i][j - 1]);
	rep(i, 1, c3 + c4)
	rep(j, 0, c3 + c4) upd(sum[i][j], sum[i - 1][j]);
	rep(i, 0, c1)
	rep(j, 0, c2) {
		int l1 = min(r3 - c1 - c2 + i + j, c3 + c4), l2 = min(r2 - c1 - c3 + i - j, c4) + c3;
		if (l1 >= 0 && l2 >= 0) upd(ans, 1ll * C(c1, i)*C(c2, j) % mod * sum[l1][l2]);
	}
	cout << ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3352kb

input:

3
1 000
1 100
0 111

output:

7

result:

ok answer is '7'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5420kb

input:

5
2 10110
0 11010
1 00000

output:

19

result:

ok answer is '19'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3364kb

input:

3
2 011
0 100
3 010

output:

9

result:

wrong answer expected '8', found '9'