結果

問題 No.936 Are
コンテスト
ユーザー leaf_1415
提出日時 2019-11-30 21:28:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 615 ms / 3,000 ms
コード長 2,962 bytes
コンパイル時間 590 ms
コンパイル使用メモリ 67,200 KB
実行使用メモリ 207,488 KB
最終ジャッジ日時 2024-11-21 03:35:32
合計ジャッジ時間 7,520 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#define llint long long
#define mod 1000000007
#define V(k, a, b, c, d) ((k)*625+(a)*125+(b)*25+(c)*5+(d))

using namespace std;

llint n, t;
llint l1, r1, l2, r2;
vector<llint> G[1305];
bool win[1305], lose[1305], must[1305], fin[1305];
llint dp[20005][1305];

int main(void)
{
	cin >> n >> t >> l1 >> r1 >> l2 >> r2;
	
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			for(int k = 0; k < 5; k++){
				for(int l = 0; l < 5; l++){
					if(i==0&&j==0 || k==0&&l==0) continue;
					for(int m = 0; m < 2; m++){
						int u, v = V(m, i, j, k, l);
						if(m == 0){
							if(i>0&&k>0) u = V(1-m, i, j, (k+i)%5, l), G[v].push_back(u);
							if(j>0&&k>0) u = V(1-m, i, j, (k+j)%5, l), G[v].push_back(u);
							if(i>0&&l>0) u = V(1-m, i, j, k, (l+i)%5), G[v].push_back(u);
							if(j>0&&l>0) u = V(1-m, i, j, k, (l+j)%5), G[v].push_back(u);
							for(int p = 0; p < 5; p++){
								for(int q = 0; q < 5; q++){
									if(p==0&&q==0) continue;
									if(!(i+j==p+q || i+j>5&&(i+j)%5==(p+q)%5)) continue;
									if(i==p&&j==q || i==q&&j==p) continue;
									u = V(1-m, p, q, k, l), G[v].push_back(u);
								}
							}
						}
						else{
							if(i>0&&k>0) u = V(1-m, (i+k)%5, j, k, l), G[v].push_back(u);
							if(i>0&&l>0) u = V(1-m, (i+l)%5, j, k, l), G[v].push_back(u);
							if(j>0&&k>0) u = V(1-m, i, (j+k)%5, k, l), G[v].push_back(u);
							if(j>0&&l>0) u = V(1-m, i, (j+l)%5, k, l), G[v].push_back(u);
							for(int p = 0; p < 5; p++){
								for(int q = 0; q < 5; q++){
									if(p==0&&q==0) continue;
									if(!(k+l==p+q || k+l>5&&(k+l)%5==(p+q)%5)) continue;
									if(k==p&&l==q || k==q&&l==p) continue;
									u = V(1-m, i, j, p, q), G[v].push_back(u);
								}
							}
						}
					}
				}
			}
		}
	}
	
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			for(int k = 0; k < 5; k++){
				for(int l = 0; l < 5; l++){
					int v = V(0, i, j, k, l);
					int u = V(1, i, j, 0, 0);
					if(i==0&&j==0) fin[v] = true;
					for(int m = 0; m < G[v].size(); m++){
						if(G[v][m] == u) lose[v] = true;
					}
				}
			}
		}
	}
	
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			for(int k = 0; k < 5; k++){
				for(int l = 0; l < 5; l++){
					int v = V(1, i, j, k, l);
					int u = V(0, 0, 0, k, l);
					bool flag = false;
					for(int m = 0; m < G[v].size(); m++){
						if(G[v][m] == u) win[v] = true;
						if(!lose[G[v][m]]) flag = true;
					}
					if(!flag) must[v] = true;
				}
			}
		}
	}
	
	int S = V(n, l1, r1, l2, r2);
	dp[0][S] = 1;
	for(int i = 0; i < t; i++){
		for(int j = 0; j < 1305; j++){
			for(int k = 0; k < G[j].size(); k++){
				int u = G[j][k];
				if(win[j] && !fin[u]) continue;
				if(!must[j] && lose[u]) continue;
				dp[i+1][u] += dp[i][j], dp[i+1][u] %= mod;
			}
		}
	}
	llint ans = 0;
	for(int i = 0; i <= t; i++){
		for(int j = 0; j < 1305; j+=25){
			ans += dp[i][j], ans %= mod;
		}
	}
	cout << ans << endl;
	
	return 0;
}
0