| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 14199 |
2015-05-04T12:21:19 Z |
ainta |
선다형 시험 (TOKI14_multiple) |
C++ |
|
103 ms |
1184 KB |
#include<stdio.h>
int n, P1, P2, w[2][5], C[2], D[5][2010], DD[2][2010];
int a1[2010], a2[2010];
long long Mod = 1000000007, F[2010], invF[2010];
long long Pow(long long a, long long b){
long long r = 1;
while (b){
if (b % 2)r = r*a%Mod;
a = a*a%Mod;
b /= 2;
}
return r;
}
long long Comb(int a, int b){
return F[a] * invF[b] % Mod*invF[a - b] % Mod;
}
void DP(int pv){
int i, j, k;
D[0][0] = 1;
long long t;
for (i = 1; i <= 4; i++){
for (j = 0; j <= n; j++){
if (!D[i - 1][j])continue;
t = 1;
for (k = 0; k <= w[pv][i]; k++){
D[i][j + k] = (D[i][j+k] + Comb(w[pv][i], k)*t % Mod * D[i - 1][j]) % Mod;
t = t*i%Mod;
}
D[i - 1][j] = 0;
}
}
for (i = 0; i <= n; i++){
DD[pv][i] = D[4][i];
D[4][i] = 0;
}
}
int main(){
char pp[20];
scanf("%d%d%d", &n, &P1, &P2);
int i, c, j;
long long Res = 0;
for (i = 1; i <= n; i++){
scanf("%s", pp);
a1[i] = pp[0] - 'a';
}
for (i = 1; i <= n; i++){
scanf("%s", pp);
a2[i] = pp[0] - 'a';
}
for (i = 1; i <= n; i++){
scanf("%s", pp);
c = 0;
for (j = 0; j < 5; j++){
if (pp[j] != '.')c++;
}
if (a1[i] == a2[i]){
C[0]++;
w[0][c - 1]++;
}
else{
C[1]++;
w[1][c - 2]++;
}
}
F[0] = invF[0] = 1;
for (i = 1; i <= n; i++){
F[i] = F[i - 1] * i%Mod;
invF[i] = Pow(F[i], Mod - 2);
}
DP(0);
DP(1);
for (i = 0; i <= P1&&i <= P2 && i <= C[0]; i++){
if (C[1] < P1 + P2 - i * 2)continue;
Res = (Res + DD[0][C[0] - i] * Comb(P1 + P2 - i * 2, P1 - i) % Mod * DD[1][C[1] - (P1 + P2 - i * 2)]) % Mod;
}
printf("%lld\n", Res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1184 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1184 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
23 ms |
1184 KB |
Output is correct |
| 7 |
Correct |
35 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
57 ms |
1184 KB |
Output is correct |
| 9 |
Correct |
46 ms |
1184 KB |
Output is correct |
| 10 |
Correct |
103 ms |
1184 KB |
Output is correct |
