Submission #4110

#	Time	Username	Problem	Language	Result	Execution time	Memory
4110		Skeas	Hexagon travel (kriii1_H)	C++98	1 / 1	296 ms	1900 KiB

H

#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);
}

• Subtask 1: 1 / 1