Submission #21162

#	Time	Username	Problem	Language	Result	Execution time	Memory
21162		gs14004	Hexagon travel (kriii1_H)	C++11	1 / 1	209 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;
	for(int i=1; i<=r; 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: 1 / 1