글 읽기 - 제 접근방법이 잘못되었나요?

hwy16016 3년 전 0

우선 블록들을 3가지로 분류했습니다.

-ㅡㅡㅡ-

ㅡㅡㅡㅡ

ㅡ- -ㅡㅡ

-ㅡ ㅡㅡ-

D1 D2

ㅡㅡㅡㅡㅡ

-ㅡㅡㅡㅡ-

-- ㅡ

ㅡ --

각각의 블럭들은 아래와 같은 점화식으로 나타낼 수 있습니다.

C(n)=(2)C(1) * C(n-1) * (2n)C(1) + sigma_(i=2 to n-1){C(i-1) * C(n-i) * (2n)C(2i-1)}

D(n)=C(n-1) + sigma_(i=2 to n-1){D(i-1) * C(n-i) * (2n-1)C(2i-2)} + D(n-1) * (2n-1)C(1)

E(n)=2 * D(n) + sigma_(i=2 to n-1){D(i-1) * D(n-i) * (2n)C(2i-2)}

위에 블럭배치는 단순한게 카운트했습니다.(sm으로, 작업의 수인 1 더해줌)

그러면 L을 위의 sm/c/d/e 4가지로 분해할 수 있습니다.

해야 하는 전체 작업의 수를 T, 단순한 작업을 sm이라 하면

sol=(T)C(sm) * (sm)! * (curT)C(현재 블럭의 작업의 수) * 현재 블럭의 작업 순서 배치의 경우의 수

입니다.

(curT는 아직 배치되지 않은 작업들의 개수)

ct, facto, cdet는 각각 combination, factorial, 위의 블럭들의 조합의 경우의 수(0 : c, 1 : d, 2 : e)를 저장합니다.

clist는 블럭들의 시작과 끝을 저장해서 cde를 만들기 위해 사용했고 cde는 L에 있는 c/d/e를 저장합니다.

문제의 예시, 이 게시판에 있는 예시,

26
16
1 2 2 1 1 2 1 1 2 2 2 1 2 2 2 2
16
2 1 1 1 2 1 2 2 2 2 2 1 2 2 2 1

20 280640559

등 예시는 다 통과하는데 왜 틀렸다고 나올까요?

제가 간과한 부분이 어디인지 모르겠습니다..

반례라도 적어주시면 감사히 쓰겠습니다.

#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#define MOD 1000000007
typedef unsigned long long int ulld;
using namespace std;

ulld ct[3001][3001], facto[1501], cdet[3][1500];

ulld ncr(int n, int r){
	if(r==0) return 1;
	if(n==0) return 1;
	if(ct[n][r]!=0) return ct[n][r];
	return ct[n][r]=(ncr(n-1, r-1)+ncr(n-1, r))%MOD;
}

ulld f(int n){
	if(n==0) return 1;
	if(n==1) return 1;
	if(facto[n]!=0) return facto[n];
	ulld t=(n*f(n-1))%MOD;
	return facto[n]=t;
}

ulld c(int n){
	if(n==1) return 2;
	if(cdet[0][n]!=0) return cdet[0][n];
	ulld sigma=0;
	for(int i=2;i<=n-1;i++){
		
		ulld t=((ulld)c(i-1)*(ulld)c(n-i))%MOD;
		sigma+=(t*ncr(2*n, 2*i-1))%MOD;
		sigma=sigma%MOD;
	}
	return cdet[0][n]=(sigma+(ulld)(4*(ulld)c(n-1)*n))%MOD;
}

ulld d(int n){
	if(n==1) return 1;
	if(cdet[1][n]!=0) return cdet[1][n];
	ulld sigma=0;
	for(int i=2;i<=n-1;i++){
		ulld t=(d(i-1)*c(n-i))%MOD;
		sigma+=(t*ncr(2*n-1, 2*i-2))%MOD;
		sigma=sigma%MOD;
	}
	return cdet[1][n]=(sigma+(ulld)(c(n-1)+d(n-1)*(2*n-1)))%MOD;
}

ulld e(int n){
	if(n==1) return 2;
	if(cdet[2][n]!=0) return cdet[2][n];
	ulld sigma=0;
	for(int i=2;i<=n-1;i++){
		ulld t=(d(i-1)*d(n-i))%MOD;
		sigma+=(t*ncr(2*n, 2*i-2))%MOD;
		sigma=sigma%MOD;
	}
	return cdet[2][n]=(sigma+(ulld)(2*d(n)))%MOD;
}

int main()
{
	int L, n, m;
	for(int i=0;i<3001;i++) for(int j=0;j<3001;j++) ct[i][j]=0;
	for(int i=0;i<3001;i++)	ct[i][i]=1, ct[i][1]=i;
	for(int i=0;i<1501;i++) facto[i]=0;
	facto[1]=1, facto[2]=2;
	
	scanf("%d %d", &L, &n);
	vector<int> a(0, 0);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d", &t);
		if(t==1)
			a.push_back(1);
		if(t==2){
			a.push_back(2);
			a.push_back(2);
		}
	}
	scanf("%d", &m);
	vector<int> b(0, 0);
	for(int i=0;i<m;i++){
		int t;
		scanf("%d", &t);
		if(t==1)
			b.push_back(1);
		if(t==2){
			b.push_back(2);
			b.push_back(2);
		}
	}
	int sm=0, alinked=0, blinked=0, cindx=-1, inc=0;
	vector<pair<int, int>> clist;
	for(int i=0;i<L;i++){
		if(a[i]==b[i]){
			if(a[i]==1)
				continue;
			if(alinked && blinked){
				alinked=blinked=0;
			}
			else if(alinked || blinked){
				if(inc==0){
					inc=1;
					cindx++;
					clist.push_back(make_pair(i-1, -1));
				}
				swap(alinked, blinked);
			}
			else
				alinked=blinked=1;
		}
		else{//a[i]!=b[i]
			if(a[i]==1){
				if(blinked){
					if(inc){
						inc=0;
						clist.back().second=i;
					}
					else
						sm++;
					blinked=0;
				}
				else
					blinked=1;
			}
			else{
				if(alinked){
					if(inc){
						inc=0;
						clist.back().second=i;
					}
					else
						sm++;
					alinked=0;
				}
				else
					alinked=1;
			}
		}
	}
	vector<vector<int>> cde(3, vector<int>(0, 0));
	for(int i=0;i<clist.size();i++){
		int diff=clist[i].second-clist[i].first;
		if(diff%2==0){
			cde[1].push_back(diff/2);
			continue;
		}
		if(a[clist[i].first]==1)
			cde[0].push_back(diff/2);
		else
			cde[2].push_back(diff/2);
	}
	int T=sm;
	for(int i=0;i<3;i++){
		for(int j=0;j<cde[i].size();j++){
			T+=cde[i][j]*2;
			if(i==1)
				continue;
			T++;
		}
	}
	
	ulld sol=(ncr(T, sm)*f(sm))%MOD;
	int curT=T-sm;
	for(int i=0;i<cde.size();i++){
		for(int j=0;j<cde[i].size();j++){
			int neededP=cde[i][j]*2+1;
			if(i==1) neededP--;
			sol*=ncr(curT, neededP);
			sol=sol%MOD;
			curT-=neededP;
			if(i==0)
				sol*=c(cde[i][j]);
			else if(i==1)
				sol*=d(cde[i][j]);
			else
				sol*=e(cde[i][j]);
			sol=sol%MOD;
		}
	}
	if(T==0)
		printf("0 1");
	else
		printf("%d %d", T, (int)sol);
	return 0;
}

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

문제

문제

출처

ICPC

제 접근방법이 잘못되었나요?

hwy16016 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말