結果
| 問題 |
No.726 Tree Game
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:55:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 7,800 bytes |
| コンパイル時間 | 4,936 ms |
| コンパイル使用メモリ | 86,084 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 12:57:21 |
| 合計ジャッジ時間 | 1,872 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility> // For std::pair
// Use __uint128_t for intermediate calculations in modular exponentiation to avoid overflow.
// This type is available in GCC and Clang.
#ifdef __GNUC__
using u128 = __uint128_t;
#else
// Provide a fallback for compilers that don't support __uint128_t.
// Note: This fallback might lead to overflow for very large intermediate values in the power function.
// Competitive programming environments usually support __uint128_t.
using u128 = unsigned long long;
#warning "__uint128_t not supported, potential overflow in modular exponentiation."
#endif
// Use unsigned long long for large integers potentially involved in primality testing.
using u64 = unsigned long long;
// Modular exponentiation function: computes (base^exp) % mod
// Uses __uint128_t for intermediate products to prevent overflow.
u64 power(u64 base, u64 exp, u64 mod) {
u64 res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (u128)res * base % mod;
base = (u128)base * base % mod;
exp /= 2;
}
return res;
}
// Helper function for Miller-Rabin primality test.
// Checks if 'n' is composite using 'a' as a base witness.
// 'd' and 's' satisfy n-1 = d * 2^s where d is odd.
bool check_composite(u64 n, u64 a, u64 d, int s) {
// Calculate a^d % n
u64 x = power(a, d, n);
// If x is 1 or n-1, n might be prime (pass test for base a)
if (x == 1 || x == n - 1)
return false;
// Repeat s-1 times: square x and check if it becomes n-1
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false; // n might be prime
}
// If x never became n-1 after squaring, n is definitely composite
return true;
}
// Miller-Rabin primality test function.
// Uses deterministic set of bases {2, 7, 61} which is sufficient for n < 4,759,123,141.
// This covers the problem constraints (Y, X <= 10^9) and likely coordinate ranges.
bool is_prime(u64 n) {
// Handle base cases: 0, 1 are not prime. 2, 3, 5 are prime.
if (n < 2) return false;
if (n == 2 || n == 3 || n == 5) return true;
// Quick check for divisibility by small primes 2, 3, 5
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
// Pre-check small numbers < 49 using properties. Any number < 49 not divisible by 2,3,5 must be prime or 7*7=49.
// The remaining primes < 49 are: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
if (n < 49) {
// Note: 7*7 = 49. We only check up to n < 49.
// Any remaining number must be one of these primes.
return true;
}
// If n >= 49, proceed with Miller-Rabin test
int s = 0;
u64 d = n - 1;
// Find d and s such that n-1 = d * 2^s where d is odd
while ((d & 1) == 0) {
d >>= 1;
s++;
}
// Test with bases {2, 7, 61}
for (u64 a : {2, 7, 61}) {
// We need a < n. Since n >= 49, this holds for a=2, 7, 61.
// Check if n is one of the bases itself (though redundant because we checked small primes already)
if (n == a) return true;
// Perform Miller-Rabin test with base 'a'
if (check_composite(n, a, d, s))
return false; // Found a witness 'a' that proves n is composite
}
// If n passed Miller-Rabin test for all selected bases, it is very likely prime.
// For the chosen bases and range, this is deterministic.
return true;
}
// Memoization table to store computed Grundy values.
// Key: pair of coordinates (y, x). Value: Grundy number G(y, x).
// Use std::map for simplicity. For higher performance, std::unordered_map could be considered.
std::map<std::pair<long long, long long>, int> memo;
// Recursive function to compute the Grundy value (Nim-sum) G(y, x) for a state (y, x).
// Assumes this function is called only for non-prime cells (y, x).
int compute_grundy(long long y, long long x) {
// State represented as a pair of coordinates
std::pair<long long, long long> current_state = {y, x};
// Check if the Grundy value for this state is already computed and stored in the map
auto it = memo.find(current_state);
if (it != memo.end()) {
return it->second; // Return memoized value
}
// Set to store the Grundy values of reachable next states (neighbors in the game graph)
std::set<int> neighbor_grundy_values;
// Explore the move upwards to (y+1, x)
long long next_y1 = y + 1;
long long next_x1 = x;
// A move is valid only if the destination cell is non-prime.
// A cell (i, j) is non-prime if both i and j are NOT prime.
if (!is_prime(next_y1) && !is_prime(next_x1)) {
// Recursively compute the Grundy value of the next state and add it to the set
neighbor_grundy_values.insert(compute_grundy(next_y1, next_x1));
}
// Explore the move rightwards to (y, x+1)
long long next_y2 = y;
long long next_x2 = x + 1;
// Check if the destination cell is non-prime
if (!is_prime(next_y2) && !is_prime(next_x2)) {
// Recursively compute the Grundy value and add it to the set
neighbor_grundy_values.insert(compute_grundy(next_y2, next_x2));
}
// Compute the Minimum Excluded value (mex) of the set of neighbor Grundy values.
// mex(S) is the smallest non-negative integer not present in the set S.
int mex = 0;
while (neighbor_grundy_values.count(mex)) {
mex++;
}
// Store the computed mex value (Grundy value for current state) in the memoization table
// and return it.
return memo[current_state] = mex;
}
int main() {
// Optimize C++ standard input/output streams for speed
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long Y, X; // Input coordinates for the starting position
std::cin >> Y >> X;
// Flag to determine if the first player has a winning strategy
bool first_can_win = false;
// --- Determine the winner based on the game rules ---
// The first player wins if they can make a move to a state (cell) which is a P-position (losing position for the next player).
// A P-position has a Grundy value of 0.
// Evaluate the move upwards to (Y+1, X)
long long next_y1 = Y + 1;
long long next_x1 = X;
// Check if the destination cell (Y+1, X) is a non-prime cell
if (!is_prime(next_y1) && !is_prime(next_x1)) {
// If it's non-prime, compute its Grundy value. If G(Y+1, X) == 0, this is a winning move.
if (compute_grundy(next_y1, next_x1) == 0) {
first_can_win = true; // Found a winning move
}
}
// If (Y+1, X) is a prime cell, moving there is an immediate loss, so it's not a winning move.
// Evaluate the move rightwards to (Y, X+1), only if a winning move hasn't been found yet.
if (!first_can_win) {
long long next_y2 = Y;
long long next_x2 = X + 1;
// Check if the destination cell (Y, X+1) is non-prime
if (!is_prime(next_y2) && !is_prime(next_x2)) {
// If it's non-prime, compute its Grundy value. If G(Y, X+1) == 0, this is a winning move.
if (compute_grundy(next_y2, next_x2) == 0) {
first_can_win = true; // Found a winning move
}
}
// If (Y, X+1) is a prime cell, moving there is an immediate loss.
}
// Output the result based on whether the first player has a winning move
if (first_can_win) {
std::cout << "First" << std::endl;
} else {
// If no move leads to a Grundy 0 state, the first player loses (assuming optimal play).
std::cout << "Second" << std::endl;
}
return 0;
}