QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73664 | #1245. Three balls | WUZRW | WA | 2ms | 3504kb | C++14 | 2.3kb | 2023-01-27 14:59:44 | 2023-01-27 14:59:47 |
Judging History
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) {
if ((x += y) >= mod) x -= 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++;
// c1 11
// c2 10
// c3 01
// c4 00
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: 3504kb
input:
3 1 000 1 100 0 111
output:
7
result:
ok answer is '7'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
5 2 10110 0 11010 1 00000
output:
19
result:
ok answer is '19'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3348kb
input:
3 2 011 0 100 3 010
output:
9
result:
wrong answer expected '8', found '9'