結果

問題 No.936 Are
ユーザー leaf_1415leaf_1415
提出日時 2019-11-30 21:28:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 675 ms / 3,000 ms
コード長 2,962 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 65,420 KB
実行使用メモリ 207,440 KB
最終ジャッジ日時 2023-08-13 09:44:32
合計ジャッジ時間 7,957 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 675 ms
207,380 KB
testcase_02 AC 617 ms
207,392 KB
testcase_03 AC 5 ms
4,376 KB
testcase_04 AC 5 ms
4,508 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 5 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 4 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 172 ms
58,836 KB
testcase_14 AC 498 ms
168,692 KB
testcase_15 AC 200 ms
67,988 KB
testcase_16 AC 360 ms
121,488 KB
testcase_17 AC 325 ms
109,068 KB
testcase_18 AC 134 ms
46,252 KB
testcase_19 AC 587 ms
196,760 KB
testcase_20 AC 587 ms
197,868 KB
testcase_21 AC 542 ms
180,144 KB
testcase_22 AC 323 ms
108,036 KB
testcase_23 AC 616 ms
207,440 KB
testcase_24 AC 618 ms
207,432 KB
権限があれば一括ダウンロードができます

ソースコード

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