#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 10,
M = 1'000'000'007;
int n;
int a[4][N];
inline void add(auto& x, const auto& y) {
x += y;
if (x >= M) x -= M;
}
inline int powder(int a, int b) {
int ret = 1;
for (; b; b /= 2, a = 1ll * a * a % M) {
if (b & 1) ret = 1ll * ret * a % M;
}
return ret;
}
inline int distribute(int n, int m) {
int ret = 1;
for (int i = 1; i <= n; ++i, ++m) ret = 1ll * ret * m % M;
return ret;
}
int f[N][N * 3][2], prefDP[N * 3][2];
int pref[N], cnt[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= n; ++j) {
char ch; cin >> ch;
a[i][j] = (ch == 'x');
}
}
for (int i = 1; i <= n; ++i) {
cnt[i] = a[1][i] + a[3][i];
pref[i] = pref[i - 1] + a[1][i] + a[2][i] + a[3][i];
}
for (int j = 0; j <= pref[1]; ++j) {
if (a[2][1]) {
if (j > cnt[1]) f[1][j][0] = (cnt[1] <= 1 ? 1 : 2);
} else {
if (!j) f[1][j][0] = (cnt[1] <= 1 ? 1 : 2);
}
}
const int m = pref[n];
for (int i = 2; i <= n; ++i) {
prefDP[0][0] = f[i - 1][0][0];
prefDP[0][1] = f[i - 1][0][1];
for (int j = 1; j <= m; ++j) {
prefDP[j][0] = (prefDP[j - 1][0] + f[i - 1][j][0]) % M;
prefDP[j][1] = (prefDP[j - 1][1] + f[i - 1][j][1]) % M;
}
auto getDP = [&](int l, int r, int type) {
return !l ? prefDP[r][type] : (prefDP[r][type] - prefDP[l - 1][type] + M) % M;
};
if (a[2][i]) {
for (int j = 1; j <= pref[i]; ++j) {
if (j >= cnt[i]) { // up & down and previous is 0
auto& ret = f[i][j][0];
int value = 1ll * getDP(0, m, 0) *
distribute(cnt[i], j - cnt[i]) % M;
add(ret, value);
}
if (j >= cnt[i]) { // up & down and previous is 1
auto& ret = f[i][j][0];
int value = 1ll * getDP(j - cnt[i], m, 1) *
distribute(cnt[i], j - cnt[i]) % M;
add(ret, value);
}
{ // left & right
auto& ret = f[i][j][1];
for (int k = 0; k < cnt[i] && k < j; ++k) {
int value = 1ll * getDP(0, j - 1 - k, 0) *
distribute(k, j - k) % M *
distribute(cnt[i] - k, pref[i - 1] + 2 - (j - k)) % M;
if (k) value = 1ll * value * max(1, cnt[i]) % M;
add(ret, value);
}
}
}
} else {
auto& ret = f[i][0][0];
int value = 1ll * (getDP(0, m, 0) + getDP(0, m, 1)) % M *
distribute(cnt[i], pref[i - 1] + 1) % M;
add(ret, value);
}
}
int answer = 0;
for (int i = 0; i <= m; ++i) add(answer, f[n][i][0]);
cout << answer << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |