#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[2005][2005];
lint dp2[2005][2005];
lint dp3[2005][2005];
lint dp4[2005][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]){
// printf("%d 1\n",i);
cnt_samematch++;
p1++;
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'] != '.'){
//printf("%d 2\n",i);
cnt_abmatch++;
p2++;
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'] != '.'){
// printf("%d 3\n",i);
cnt_amatch++;
p3++;
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'] != '.'){
// printf("%d 4\n",i);
cnt_bmatch++;
p4++;
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{
printf("%d 5\n",i);
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=0; j<=cnt_abmatch; j++) {
int pmatch = p - i - j;
int qmatch = q - i - (cnt_abmatch - j);
if(pmatch < 0 || qmatch < 0 || pmatch > cnt_amatch || qmatch > cnt_bmatch) continue;
lint t = 1;
t *= bino[cnt_amatch][pmatch];
t %= mod;
t *= dp3[p3][cnt_amatch - pmatch];
t %= mod;
t *= bino[cnt_bmatch][qmatch];
t %= mod;
t *= dp4[p4][cnt_bmatch - qmatch];
t %= mod;
t *= bino[cnt_samematch][i];
t %= mod;
t *= dp1[p1][cnt_samematch - i];
t %= mod;
t *= bino[cnt_abmatch][j];
t %= mod;
t *= dp2[p2][cnt_abmatch - j];
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 |
Memory limit exceeded |
0 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
0 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
0 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
