#include <cstdio>
#include <cstring>
const int mod = 1e9 + 7;
typedef long long lint;
int n, p, q;
char sa[2005], sb[2005];
char tab[2005][6];
lint bino[2005][2005];
lint dp1[2][2005];
lint dp2[2][2005];
lint dp3[2][2005];
lint dp4[2][2005];
int p1, p2, p3, p4;
void solve(){
int cnt_amatch = 0;
int cnt_bmatch = 0;
int cnt_abmatch = 0;
int cnt_samematch = 0;
lint nomatch = 1;
dp1[0][0] = dp2[0][0] = dp3[0][0] = dp4[0][0] = 1;
for (int i=0; i<n; i++) {
int p = 0;
for (int j=0; j<5; j++) {
if(tab[i][j] != '.') p++;
}
if(tab[i][sa[i] - 'a'] != '.' && sa[i] == sb[i]){
cnt_samematch++;
p1 ^= 1;
dp1[p1][0] = 1;
for (int j=1; j<=i+1; j++) {
dp1[p1][j] = dp1[p1^1][j-1] * (p-1) + dp1[p1^1][j];
dp1[p1][j] %= mod;
}
}
else if(tab[i][sa[i] - 'a'] != '.' && tab[i][sb[i] - 'a'] != '.'){
cnt_abmatch++;
p2 ^= 1;
dp2[p2][0] = 1;
for (int j=1; j<=i+1; j++) {
dp2[p2][j] = dp2[p2^1][j-1] * (p-2) + dp2[p2^1][j];
dp2[p2][j] %= mod;
}
}
else if(tab[i][sa[i] - 'a'] != '.'){
cnt_amatch++;
p3 ^= 1;
dp3[p3][0] = 1;
for (int j=1; j<=i+1; j++) {
dp3[p3][j] = dp3[p3^1][j-1] * (p-1) + dp3[p3^1][j];
dp3[p3][j] %= mod;
}
}
else if(tab[i][sb[i] - 'a'] != '.'){
cnt_bmatch++;
p4 ^= 1;
dp4[p4][0] = 1;
for (int j=1; j<=i; j++) {
dp4[p4][j] = dp4[p4^1][j-1] * (p-1) + dp4[p4^1][j];
dp4[p4][j] %= mod;
}
}
else{
nomatch *= p;
nomatch %= mod;
}
}
for (int i=0; i<=n; i++) {
bino[i][0] = 1;
for (int j=1; j<=i; j++) {
bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
bino[i][j] %= mod;
}
}
lint ret = 0;
for (int i=0; i<=cnt_samematch; i++) {
for (int j=i; j<=cnt_abmatch; j++) {
for (int k=i; j + k <= cnt_abmatch + 2 * i; k++) {
if(p < j || q < k || p - cnt_amatch > j || q - cnt_bmatch > k) continue; lint t = 1;
t *= dp1[p1][cnt_samematch - i];
t %= mod;
t *= dp2[p2][cnt_abmatch - j - k + 2 * i];
t %= mod;
t *= dp3[p3][cnt_amatch - p + j];
t %= mod;
t *= dp4[p4][cnt_bmatch - q + k];
t %= mod;
t *= bino[j + k - 2 * i][j - i];
t %= mod;
ret += t;
ret %= mod;
}
}
}
ret *= nomatch;
ret %= mod;
printf("%lld",ret);
}
void what_the_fuck(){
char str[10];
scanf("%d %d %d",&n,&p,&q);
for (int i=0; i<n; i++) {
scanf("%s",str);
sa[i] = str[0];
}
for (int i=0; i<n; i++) {
scanf("%s",str);
sb[i] = str[0];
}
for (int i=0; i<n; i++) {
scanf("%s",tab[i]);
}
solve();
}
int main(){
what_the_fuck();
puts("");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
32632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
32632 KB |
Output is correct |
| 2 |
Correct |
0 ms |
32632 KB |
Output is correct |
| 3 |
Correct |
0 ms |
32632 KB |
Output is correct |
| 4 |
Correct |
19 ms |
32632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
32632 KB |
Output is correct |
| 2 |
Correct |
8 ms |
32632 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
32632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
