oj.uz

Submission #14198

# Submission time Handle Problem Language Result Execution time Memory
14198 2015-05-04T12:19:37 Z ainta 선다형 시험 (TOKI14_multiple) C++
100 / 100
 325 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;
	for (i = 1; i <= 4; i++){
		for (j = 0; j <= n; j++){
			if (!D[i - 1][j])continue;
			for (k = 0; k <= w[pv][i]; k++){
				D[i][j + k] = (D[i][j+k] + Comb(w[pv][i], k)*Pow(i, k) % Mod * D[i - 1][j]) % 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);
}

Subtask #1
24.0 / 24.0

# 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 2 ms 1184 KB Output is correct
10 Correct 0 ms 1184 KB Output is correct

Subtask #2
16.0 / 16.0

# 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 3 ms 1184 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1184 KB Output is correct
2 Correct 13 ms 1184 KB Output is correct
3 Correct 24 ms 1184 KB Output is correct
4 Correct 38 ms 1184 KB Output is correct
5 Correct 77 ms 1184 KB Output is correct
6 Correct 57 ms 1184 KB Output is correct
7 Correct 94 ms 1184 KB Output is correct
8 Correct 161 ms 1184 KB Output is correct
9 Correct 131 ms 1184 KB Output is correct
10 Correct 325 ms 1184 KB Output is correct