제출 #4110

#제출 시각아이디문제언어결과실행 시간메모리
4110SkeasHexagon travel (kriii1_H)C++98
1 / 1
296 ms1900 KiB
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

#define MOD 1000000007

int cc[2][2222];
int dp[2][4444][3][2];
int L,R,M;

inline void Plus(int &a, int b) {
	a+=b; if(a>=MOD) a-=MOD;
}
inline int move(int clr, int dir) {
	if(clr==0) return !dir?1:2;
	else if(clr==1) return !dir?2:0;
	else return !dir?0:1;
}

int main() {
#ifdef LOCAL
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d%d",&L,&R,&M);
	cc[0][0] = 1;
	int cur = 0, nxt = 1;
	for(int i=1;i<=L+R;++i) {
		memset(cc[nxt],0,sizeof(cc[nxt]));
		cc[nxt][0] = 1;
		for(int j=1;j<=2000;++j) {
			cc[nxt][j] = (cc[cur][j]+cc[cur][j-1]) % MOD;
		} swap(cur,nxt);
	}

	dp[0][0][0][0] = 1;
	cur=0,nxt=1;
	for(int i=0;i<=M;++i) {
		memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int j=0;j<=L+R;++j)
		for(int k=0;k<3;++k)
		for(int h=0;h<2;++h) {
			int r = dp[cur][j][k][h];
			Plus(dp[cur][j+1][k][h^1],r);
			Plus(dp[nxt][j][move(k,h)][h],r);
		} swap(cur,nxt);
	}

	int rr=0,gg=0,bb=0;
	Plus(bb,dp[M&1][L+R][0][0]);
	Plus(bb,dp[M&1][L+R][0][1]);
	
	Plus(rr,dp[M&1][L+R][1][0]);
	Plus(rr,dp[M&1][L+R][1][1]);
	
	Plus(gg,dp[M&1][L+R][2][0]);
	Plus(gg,dp[M&1][L+R][2][1]);
	
	rr = (long long)rr * cc[(L+R)&1][L] % MOD;
	gg = (long long)gg * cc[(L+R)&1][L] % MOD;
	bb = (long long)bb * cc[(L+R)&1][L] % MOD;
	printf("%d\n",rr);
	printf("%d\n",gg);
	printf("%d\n",bb);
}
#Verdict Execution timeMemoryGrader output
Fetching results...