Submission #19941

#	Time	Username	Problem	Language	Result	Execution time	Memory
19941		yukariko	동전 (kriii4_E)	C++98	0 / 100	0 ms	1720 KiB

D

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define INF 987654321

typedef long long lld;

// (연속된 짝수개의 0)%2 == (연속된 홀수개의 0)%2

char trace[10];

bool isCorrect(char *s, const int& L){
	int i, odd=0, even=0, cnt=0;
	int oneCount=0;
	for(i=0; i<L; ++i){
		if(s[i] == '0'){
			cnt = 0;
			while(s[i+cnt]=='0') cnt++;
			if(cnt&1) odd += 1;
			else even += 1;
			
			i += cnt-1;
			oneCount += cnt==1;
		}
	}
	if(odd == 1 || even == 1) return false;
	if(oneCount&1) return false;
	return odd%2 == even%2;
}

lld f(int pos, const int& L){
	if(pos == L){
		return isCorrect(trace, L);
	}
	int r = 0;
	trace[pos]='0';
	r = (r + f(pos+1, L))%MOD;
	trace[pos]='1';
	r = (r + f(pos+1, L))%MOD;
	return r;
}

int main(){
	int n;
	while(~scanf("%d", &n))
		printf("%lld\n", f(0, n));
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95