제출 #21161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
21161		gs14004	Hexagon travel (kriii1_H)	C++11	0 / 1	0 ms	2112 KiB

H

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}


int l, r, m;
int dp[2][2005][3][2];

int main(){
	cin >> l >> r >> m;
	lint fact = 1;
	for(int i=1; i<=l+r; i++) fact = (fact * i) % mod;
	for(int i=1; i<=l; i++) fact = (fact * ipow(i, mod-2)) % mod;
	l += r;
	dp[0][0][0][0] = 1;
	for(int i=0; i<=l; i++){
		for(int j=0; j<=m; j++){
			if(i + j == 0) continue;
			for(int k=0; k<3; k++){
				for(int l=0; l<2; l++){
					dp[i%2][j][k][l] = 0;
					if(i) dp[i%2][j][k][l] += dp[(i-1)%2][j][k][l^1];
					if(j) dp[i%2][j][k][l] += dp[i%2][j-1][(k + (l ? 1 : 2)) % 3][l];
					dp[i%2][j][k][l] %= mod;
				}
			}
		}
	}
	for(int i=1; i<=3; i++){
		lint ans = dp[l%2][m][i%3][0] + dp[l%2][m][i%3][1];
		ans *= fact;
		ans %= mod;
		cout << ans << endl;
	}
}

• Subtask 1: 0 / 1