This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
const int mod = 1e9 + 7;
int n, p, q;
char sa[2005], sb[2005];
char tab[2005][6];
int dp[205][205][205];
int bino[2005][2005];
int f(int pos, int p, int q){
if(p < 0 || q < 0) return 0;
if(pos == n) return p == 0 && q == 0;
if(~dp[pos][p][q]) return dp[pos][p][q];
int ret = 0;
for (int i=0; i<5; i++) {
if(tab[pos][i] != '.'){
ret += f(pos+1,p - (sa[pos] == tab[pos][i]),q - (sb[pos] == tab[pos][i]));
ret %= mod;
}
}
return dp[pos][p][q] = ret;
}
void solve_sub2(){
int cnt_nomatch = 0;
int cnt_amatch = 0;
int cnt_bmatch = 0;
int cnt_abmatch = 0;
for (int i=0; i<n; i++) {
if(tab[i][sa[i] - 'a'] != '.' && tab[i][sb[i] - 'a'] != '.'){
cnt_abmatch++;
}
else if(tab[i][sa[i] - 'a'] != '.'){
cnt_amatch++;
}
else if(tab[i][sb[i] - 'a'] != '.'){
cnt_bmatch++;
}
else{
cnt_nomatch++;
}
}
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;
}
}
int ret = 0;
for (int i=0; i<=cnt_abmatch; i++) {
int p_req = p - i;
int q_req = q - i;
if(p_req < 0 || q_req < 0 || p_req > cnt_amatch || q_req > cnt_bmatch) continue;
long long t = bino[cnt_amatch][p_req];
t *= bino[cnt_bmatch][q_req];
t %= mod;
for (int j=0; j<cnt_nomatch; j++) {
t *= 2;
t %= mod;
}
ret += t;
ret %= mod;
}
printf("%d",ret);
}
void what_the_fuck(){
char str[10];
memset(dp,-1,sizeof(dp));
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]);
}
if(n > 200){
solve_sub2();
return;
}
printf("%d",f(0,p,q));
}
int main(){
what_the_fuck();
puts("");
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |