글 읽기 - 아이디어는 맞았는데 틀렸습니다가 자꾸 뜨네요 ㅠㅠ

jack2020 4년 전 0

알려진 정해로 페르마의 소정리를 이용해 풀었는데 틀렸습니다가 나옵니다 ㅠㅠ

어느 부분에서 반례가 나오나요?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> vec1, vec2;
vector<int> vec;
long long int dp[3000];

long long int factmod(long long int n, long long int p) {
	long long int res = 1;
	while (n > 1) {
		res = (res * ((n / p) % 2 ? p - 1 : 1)) % p;
		for (int i = 2; i <= n % p; ++i) {
			res = (res * i) % p;
		}
		n /= p;
	}
	return res % p;
}

long long int power(long long int x, long long int y, long long int p) {
	long long int res = 1;
	x = x % p;
	while (y > 0) {
		if (y & 1) {
			res = (res * x) % p;
		}
		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

long long int modInverse(long long int n, long long int p) {
	return power(n, p - 2, p);
}
long long int fact(int x) {
	long long int k = 1;
	for (int i = 1; i <= x; i++) {
		k = (k * i);
	}
	return k;
}
long long int comb(long long int a, long long int b) {
	if (b == 0) {
		return 1;
	}
	return fact(a) / fact(a - b) / fact(b);
}



int main() {
	//EASY
	int L, n; scanf("%d %d", &L, &n);
	for (int i = 1; i <= n; i++) {
		int a; scanf("%d", &a);
		if (i == 1) {
			if (a == 1) {

			}
			else {
				vec1.push_back(0);
			}
		}
		else {
			if (a == 1) {
				vec1.push_back(1);
			}
			else {
				vec1.push_back(1); vec1.push_back(0);
			}
		}
	}
	int m; scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int a; scanf("%d", &a);
		if (i == 1) {
			if (a == 1) {

			}
			else {
				vec2.push_back(0);
			}
		}
		else {
			if (a == 1) {
				vec2.push_back(1);
			}
			else {
				vec2.push_back(1); vec2.push_back(0);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= L - 1; i++) {
		if (vec1[i - 1] != vec2[i - 1]) {
			ans++;
		}
	}
	printf("%d ", ans);
	
	//HARD
	int siz = (int)vec1.size();
	int cnt = 0;
	for (int i = 1; i <= siz; i++) {
		cnt++;
		if (vec1[i - 1] == 1 && vec2[i - 1] == 1) {
			cnt--;
			if (cnt != 0) {
				vec.push_back(cnt);
			}
			cnt = 0;
		}
		else if (i == siz) {
			if (cnt != 0) {
				vec.push_back(cnt);
			}
		}
	}
	int maximum = 0;
	for (int i = 1; i <= (int)vec.size(); i++) {
		maximum = max(maximum, vec[i - 1]);
	}
	dp[0] = 1; dp[1] = 1;
	for (int i = 2; i <= maximum; i++) {
		int cal = 1;
		while (i - cal >= 0) {
			long long int temp = 1;
			temp = (temp * dp[cal - 1]);
			temp = (temp * dp[i - cal]);
			temp = (temp * comb(i - 1, cal - 1));
			dp[i] += temp;
			cal++; cal++;
		}
	}
	long long int ansans = 1;
	int sum = 0;
	for (int i = 1; i <= (int)vec.size(); i++) {
		ansans = (ansans * dp[vec[i - 1]]) % 1000000007;
		sum += vec[i - 1];
	}
	ansans = (ansans * factmod(sum, 1000000007)) % 1000000007;
	for (int i = 1; i <= (int)vec.size(); i++) {
		int l = vec[i - 1];
		ansans = (ansans * modInverse(fact(l), 1000000007)) % 1000000007;
	}
	
	printf("%lld", ansans);
	
	return 0;
}

sait2000 4년 전 0

3000!은 long long에 절대 안 들어가니까 fact, comb가 제대로 작동하질 않습니다. 그 외에는 잘 모르겠네요.

in:
50
26
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
25
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

out:
49 752033767

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아이디어는 맞았는데 틀렸습니다가 자꾸 뜨네요 ㅠㅠ

jack2020 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말