Submission #14222

#TimeUsernameProblemLanguageResultExecution timeMemory
14222gs14004선다형 시험 (TOKI14_multiple)C++14
40 / 100
69 ms50456 KiB
#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 pmatch = p - (cnt_abmatch - i); int qmatch = q - i; if(pmatch < 0 || qmatch < 0) continue; long long t = 1ll * bino[cnt_amatch][pmatch] * bino[cnt_bmatch][qmatch] % mod; t *= bino[cnt_abmatch][i]; t %= mod; ret += t; ret %= mod; } for (int j=0; j<cnt_nomatch; j++) { ret <<= 1; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...