Submission #14198

#	Time	Username	Problem	Language	Result	Execution time	Memory
14198		ainta	선다형 시험 (TOKI14_multiple)	C++98	100 / 100	325 ms	1184 KiB

multiple

#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 / 24
• Subtask 2: 16 / 16
• Subtask 3: 60 / 60