Problem 923: Young's Game B
View on Project EulerProject Euler Problem 923 Solution
EulerSolve provides an optimized solution for Project Euler Problem 923, Young's Game B, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary For every positive triple \((a,b,k)\) with \(a+b+k\le W\), the problem defines one staircase component of Young's Game B. Each component is a short partizan game, and \(S(m,W)\) counts ordered \(m\)-tuples of such components whose disjunctive sum is winning for Left, with the final answer taken modulo \(10^9+7\). The target value is \(S(8,64)\). The compiled implementations first verify the smaller checkpoints \(S(2,4)=7\) and \(S(3,9)=315319\), then reuse the same machinery for the main case. Mathematical Approach The solution has two distinct layers. First, every staircase component is canonically reduced to a very restricted family of game values. Second, once that catalogue is known, the ordered \(m\)-tuples are counted by frequency distributions and a sparse dynamic program instead of explicit enumeration. Staircase Components and Boundary Recursion Fix positive integers \(a\), \(b\), and \(k\). For \(0\le i\lt a\) and \(0\le j\lt b\), let \(G_{a,b,k}(i,j)\) be the game state in row \(i\), column \(j\), and layer \(k\). Left moves in the \(j\)-direction, while Right moves in the \(i\)-direction. If a move would step past the boundary, play drops to the next smaller layer....
Detailed mathematical approach
Problem Summary
For every positive triple \((a,b,k)\) with \(a+b+k\le W\), the problem defines one staircase component of Young's Game B. Each component is a short partizan game, and \(S(m,W)\) counts ordered \(m\)-tuples of such components whose disjunctive sum is winning for Left, with the final answer taken modulo \(10^9+7\).
The target value is \(S(8,64)\). The compiled implementations first verify the smaller checkpoints \(S(2,4)=7\) and \(S(3,9)=315319\), then reuse the same machinery for the main case.
Mathematical Approach
The solution has two distinct layers. First, every staircase component is canonically reduced to a very restricted family of game values. Second, once that catalogue is known, the ordered \(m\)-tuples are counted by frequency distributions and a sparse dynamic program instead of explicit enumeration.
Staircase Components and Boundary Recursion
Fix positive integers \(a\), \(b\), and \(k\). For \(0\le i\lt a\) and \(0\le j\lt b\), let \(G_{a,b,k}(i,j)\) be the game state in row \(i\), column \(j\), and layer \(k\). Left moves in the \(j\)-direction, while Right moves in the \(i\)-direction. If a move would step past the boundary, play drops to the next smaller layer.
That gives the recursive options
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
with
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
and
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
The staircase component associated with the triple \((a,b,k)\) is the top-left state \(G_{a,b,k}=G_{a,b,k}(0,0)\). Enumerating all triples with \(a,b,k\ge 1\) and \(a+b+k\le W\) produces the full catalogue of components.
Canonical Reduction and the Stop-Pair Invariant
Every raw game is reduced by the standard short-game rules: dominated options are removed, reversible moves are bypassed, and if all surviving left and right options are numbers with a gap between them, the game is replaced by the simplest dyadic rational in that interval. So the reduction engine is general enough to create arbitrary dyadic numbers if needed.
After reduction, the solver computes the left and right stops recursively:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
The decisive empirical invariant for this problem is that every staircase component ends up in one of only two forms:
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
In other words, the reduced non-numeric components are always single switches with integer stops. This is not treated as a vague heuristic; the compiled implementations explicitly check for it and stop if a staircase component falls outside that family.
Separating Integer Shifts from Switch Weights
Write
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Now two frequency tables are enough to describe the whole catalogue:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
and, for each weight \(w\),
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
The problem is therefore no longer about individual triples \((a,b,k)\); it becomes a counting problem over integers and switches classified by their weight and right endpoint.
Why Sorted Switches Collapse to Alternating Weights
The non-numeric part of any tuple sum is a sum of basic switches \(U_w\). When \(w_1\ge w_2\), canonical addition gives
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
So if the selected switch weights are sorted in nonincreasing order,
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
the top two switches collapse to the integer \(w_1\), the next two collapse to \(w_3\), and so on. If we also sum the right endpoints \(R_1,\dots,R_s\), then
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
The whole switch contribution becomes
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
That is the key simplification behind the counting stage: after sorting by weight, the switch part remembers only \(s\), the sum of right endpoints, and the sum of the weights sitting in odd positions.
Counting Ordered Tuples by Frequency Distributions
For the purely numeric components, the implementations build ordered convolution tables
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
which count ordered \(n\)-tuples of integers with total \(\sigma\).
For a fixed switch weight \(w\), they also build
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
the number of ordered \(c\)-tuples of weight-\(w\) switches whose right endpoints add to \(\rho\).
The sparse dynamic program processes weights from large to small. A state records
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
where \(s\) is the number of chosen switches, \(\Sigma_R\) the accumulated sum of right endpoints, and \(\Sigma_{\mathrm{odd}}\) the accumulated odd-position contribution. If \(c\) new switches of weight \(w\) are added after the already processed heavier weights, the number of newly occupied odd positions is
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
So the transition is
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
with multiplicity \(\binom{s+c}{c}D_{w,c}(\rho)\). The binomial factor is required because the original tuples are ordered: the newly chosen weight-\(w\) switches can be interleaved with the already chosen heavier switches in \(\binom{s+c}{c}\) ways while preserving the internal order of each group.
After all switch weights have been processed, the remaining \(m-s\) entries must be integers. Interleaving those integers with the \(s\) switches contributes an additional factor \(\binom{m}{s}\). If the numeric part contributes \(\sigma\), define
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
If \(s\) is even, the total game is the integer \(T\), so Left wins exactly when \(T>0\). If \(s\) is odd, the total game is the switch \(\{T\mid T-w_s\}\), so Left has a move to \(T\) and wins when \(T\ge 0\). Combining both cases gives the final criterion
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
Worked Example: The Checkpoint \(S(2,4)=7\)
For \(W=4\), the admissible triples produce exactly four staircase values:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
So the catalogue is \(\{0,\{0\mid 0\},1,-1\}\). The ordered pairs that are winning for Left are
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
Hence
$$ S(2,4)=7, $$
exactly the checkpoint used by the solver before it tackles the larger inputs.
How the Code Works
Generating and Reducing Every Staircase Family
The C++ and Java implementations iterate over all \(a\) and \(b\). For fixed \(a\) and \(b\), they fill a three-dimensional table over \((k,i,j)\), working backward so that every left and right option has already been constructed when the current state is reduced. This directly implements the staircase recursion above.
Compressing the Catalogue into Integers and Switches
After each component \(G_{a,b,k}(0,0)\) is canonically reduced, the implementations compute its stop pair. Numeric components are counted by their integer value. Non-numeric components are required to have exactly one left option and one right option, both numbers, so they can be recorded as a switch \(X(R,w)\) using its right endpoint \(R\) and weight \(w\).
Convolutions, Sparse DP, and the Final Win Test
Once the catalogue has been compressed into frequency tables, the implementations precompute ordered convolutions for integers and for each switch weight, run the sparse DP over descending weights, and finally combine each reachable switch state with the appropriate numeric distribution. The Python implementation does not rebuild the game engine itself; it delegates to the compiled solver and returns the parsed result.
Complexity Analysis
The structural bottleneck is catalogue generation. For fixed \(a\) and \(b\), the temporary table has \((K+1)ab\) states, where \(K=W-a-b\). Summing that over all admissible pairs gives
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
This stage uses \(O(W^3)\) temporary space for one staircase family at a time, plus memoized storage for canonical game values. The counting stage is polynomial in \(m\) and in the support sizes of the integer distributions, switch distributions, and reachable sparse-DP states. In practice, that is what makes \(S(8,64)\) feasible: the code counts frequency patterns instead of enumerating astronomical numbers of ordered tuples.
Footnotes and References
- Project Euler problem page: https://projecteuler.net/problem=923
- Combinatorial game theory: Wikipedia - Combinatorial game theory
- Disjunctive sum: Wikipedia - Disjunctive sum
- Surreal number: Wikipedia - Surreal number
- Dyadic rational: Wikipedia - Dyadic rational
Problem 923 source code
C++
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <unordered_map>
#include <utility>
#include <vector>
namespace {
constexpr int kMod = 1000000007;
struct Dyadic {
long long num;
int exp;
Dyadic(long long n = 0, int e = 0) : num(n), exp(e) { normalize(); }
void normalize() {
if (num == 0) {
exp = 0;
return;
}
while (exp > 0 && (num & 1LL) == 0) {
num >>= 1;
--exp;
}
}
};
static int cmp_dyadic(const Dyadic& a, const Dyadic& b) {
if (a.num == b.num && a.exp == b.exp) {
return 0;
}
int e = std::max(a.exp, b.exp);
__int128 na = static_cast<__int128>(a.num) << (e - a.exp);
__int128 nb = static_cast<__int128>(b.num) << (e - b.exp);
if (na < nb) {
return -1;
}
if (na > nb) {
return 1;
}
return 0;
}
static Dyadic add_dyadic(const Dyadic& a, const Dyadic& b) {
int e = std::max(a.exp, b.exp);
__int128 na = static_cast<__int128>(a.num) << (e - a.exp);
__int128 nb = static_cast<__int128>(b.num) << (e - b.exp);
__int128 s = na + nb;
Dyadic r(static_cast<long long>(s), e);
r.normalize();
return r;
}
static Dyadic neg_dyadic(const Dyadic& a) {
return Dyadic(-a.num, a.exp);
}
static long long floor_dyadic(const Dyadic& a) {
if (a.exp == 0) {
return a.num;
}
long long den = 1LL << a.exp;
if (a.num >= 0) {
return a.num / den;
}
return -(((-a.num) + den - 1) / den);
}
static long long ceil_dyadic(const Dyadic& a) {
Dyadic na = neg_dyadic(a);
long long f = floor_dyadic(na);
return -f;
}
static Dyadic simplest_between(const Dyadic& l, const Dyadic& r) {
for (int n = 0; n <= 60; ++n) {
auto floor_scaled = [&](const Dyadic& x) -> long long {
if (n >= x.exp) {
__int128 val = static_cast<__int128>(x.num) << (n - x.exp);
return static_cast<long long>(val);
}
int sh = x.exp - n;
if (x.num >= 0) {
return static_cast<long long>(static_cast<__int128>(x.num) >> sh);
}
__int128 pos = -static_cast<__int128>(x.num);
__int128 q = (pos + (static_cast<__int128>(1) << sh) - 1) >> sh;
return static_cast<long long>(-q);
};
auto ceil_scaled = [&](const Dyadic& x) -> long long {
Dyadic nx = neg_dyadic(x);
return -floor_scaled(nx);
};
long long low = floor_scaled(l) + 1;
long long high = ceil_scaled(r) - 1;
if (low > high) {
continue;
}
long long t;
if (low <= 0 && 0 <= high) {
t = 0;
} else if (high < 0) {
t = high;
} else {
t = low;
}
Dyadic ans(t, n);
ans.normalize();
return ans;
}
return Dyadic(0, 0);
}
template <typename V>
class FlatHash64 {
public:
FlatHash64() = default;
V* find(uint64_t key) {
if (keys_.empty()) {
return nullptr;
}
std::size_t idx = mix(key) & mask_;
while (true) {
uint64_t cur = keys_[idx];
if (cur == kEmpty) {
return nullptr;
}
if (cur == key) {
return &values_[idx];
}
idx = (idx + 1) & mask_;
}
}
void insert(uint64_t key, V value) {
if (keys_.empty() || (size_ + 1) * 10 >= keys_.size() * 7) {
rehash(keys_.empty() ? 1024 : keys_.size() * 2);
}
insertNoResize(key, value);
}
private:
static constexpr uint64_t kEmpty = std::numeric_limits<uint64_t>::max();
std::vector<uint64_t> keys_;
std::vector<V> values_;
std::size_t mask_ = 0;
std::size_t size_ = 0;
static uint64_t mix(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
void insertNoResize(uint64_t key, V value) {
std::size_t idx = mix(key) & mask_;
while (true) {
uint64_t cur = keys_[idx];
if (cur == kEmpty) {
keys_[idx] = key;
values_[idx] = value;
++size_;
return;
}
if (cur == key) {
values_[idx] = value;
return;
}
idx = (idx + 1) & mask_;
}
}
void rehash(std::size_t cap) {
std::size_t n = 1;
while (n < cap) {
n <<= 1;
}
std::vector<uint64_t> oldKeys = std::move(keys_);
std::vector<V> oldVals = std::move(values_);
keys_.assign(n, kEmpty);
values_.resize(n);
mask_ = n - 1;
size_ = 0;
for (std::size_t i = 0; i < oldKeys.size(); ++i) {
if (oldKeys[i] != kEmpty) {
insertNoResize(oldKeys[i], oldVals[i]);
}
}
}
};
struct GameNode {
bool isNumber = false;
bool reduced = false;
Dyadic val;
std::vector<int> L;
std::vector<int> R;
};
struct VecKey {
std::vector<int> L;
std::vector<int> R;
bool operator==(const VecKey& other) const { return L == other.L && R == other.R; }
};
struct VecKeyHash {
std::size_t operator()(const VecKey& key) const noexcept {
uint64_t h = 1469598103934665603ULL;
auto mix = [&](uint64_t x) {
h ^= x;
h *= 1099511628211ULL;
};
for (int x : key.L) {
mix(static_cast<uint64_t>(x) + 0x9e3779b97f4a7c15ULL);
}
mix(0xA5A5A5A5A5A5A5A5ULL);
for (int x : key.R) {
mix(static_cast<uint64_t>(x) + 0xD1B54A32D192ED03ULL);
}
return static_cast<std::size_t>(h);
}
};
struct StopPair {
Dyadic L;
Dyadic R;
};
struct NumKey {
long long num;
int exp;
bool operator==(const NumKey& other) const { return num == other.num && exp == other.exp; }
};
struct NumKeyHash {
std::size_t operator()(const NumKey& key) const noexcept {
uint64_t h = 1469598103934665603ULL;
h ^= static_cast<uint64_t>(key.num) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
h ^= static_cast<uint64_t>(key.exp) + 0xD1B54A32D192ED03ULL + (h << 6) + (h >> 2);
return static_cast<std::size_t>(h);
}
};
class GameEngine {
public:
GameEngine() { zeroId_ = makeNumber(Dyadic(0, 0)); }
int zero() const { return zeroId_; }
int canonical(int id) { return rep(id); }
int number(const Dyadic& value) { return makeNumber(value); }
std::size_t nodeCount() const { return nodes_.size(); }
const GameNode& node(int id) const { return nodes_[id]; }
int makeBinary(int l, int r) {
if (l != -1) {
l = rep(l);
}
if (r != -1) {
r = rep(r);
}
uint64_t key = (static_cast<uint64_t>(static_cast<uint32_t>(l + 1)) << 32) |
static_cast<uint32_t>(r + 1);
if (int* it = binMap_.find(key)) {
return rep(*it);
}
int id = static_cast<int>(nodes_.size());
nodes_.push_back(GameNode());
parent_.push_back(id);
if (l != -1) {
nodes_[id].L.push_back(l);
}
if (r != -1) {
nodes_[id].R.push_back(r);
}
int rid = reduceInPlace(id);
binMap_.insert(key, rid);
return rid;
}
int add(int a, int b) { return addImpl(a, b, true); }
int addNoMemo(int a, int b) { return addImpl(a, b, false); }
StopPair stops(int id) {
id = rep(id);
ensureStopSize(id);
if (stopSeen_[static_cast<std::size_t>(id)]) {
return stopMemo_[static_cast<std::size_t>(id)];
}
StopPair res;
if (nodes_[id].isNumber) {
res = StopPair{nodes_[id].val, nodes_[id].val};
} else {
bool hasL = false;
bool hasR = false;
Dyadic Lval(0, 0);
Dyadic Rval(0, 0);
for (int l : nodes_[id].L) {
StopPair sp = stops(l);
if (!hasL || cmp_dyadic(sp.R, Lval) > 0) {
Lval = sp.R;
hasL = true;
}
}
for (int r : nodes_[id].R) {
StopPair sp = stops(r);
if (!hasR || cmp_dyadic(sp.L, Rval) < 0) {
Rval = sp.L;
hasR = true;
}
}
res = StopPair{Lval, Rval};
}
stopMemo_[static_cast<std::size_t>(id)] = res;
stopSeen_[static_cast<std::size_t>(id)] = 1;
return res;
}
bool leftFirstWin(int g) {
g = rep(g);
ensureOutcomeSize(g);
if (leftMemo_[g] != -1) {
return leftMemo_[g] == 1;
}
if (nodes_[g].isNumber) {
leftMemo_[g] = (nodes_[g].val.num > 0) ? 1 : 0;
rightMemo_[g] = (nodes_[g].val.num < 0) ? 1 : 0;
return leftMemo_[g] == 1;
}
for (int l : nodes_[g].L) {
if (!rightFirstWin(l)) {
leftMemo_[g] = 1;
return true;
}
}
leftMemo_[g] = 0;
return false;
}
bool rightFirstWin(int g) {
g = rep(g);
ensureOutcomeSize(g);
if (rightMemo_[g] != -1) {
return rightMemo_[g] == 1;
}
if (nodes_[g].isNumber) {
leftMemo_[g] = (nodes_[g].val.num > 0) ? 1 : 0;
rightMemo_[g] = (nodes_[g].val.num < 0) ? 1 : 0;
return rightMemo_[g] == 1;
}
for (int r : nodes_[g].R) {
if (!leftFirstWin(r)) {
rightMemo_[g] = 1;
return true;
}
}
rightMemo_[g] = 0;
return false;
}
private:
std::vector<GameNode> nodes_;
std::vector<int> parent_;
std::unordered_map<NumKey, int, NumKeyHash> numMap_;
FlatHash64<int> binMap_;
std::unordered_map<VecKey, int, VecKeyHash> canonMap_;
FlatHash64<int> addMap_;
FlatHash64<uint8_t> leqMemo_;
std::vector<int8_t> leftMemo_;
std::vector<int8_t> rightMemo_;
std::vector<StopPair> stopMemo_;
std::vector<char> stopSeen_;
int zeroId_ = -1;
int rep(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]];
x = parent_[x];
}
return x;
}
void aliasTo(int from, int to) {
from = rep(from);
to = rep(to);
if (from != to) {
parent_[from] = to;
}
}
void ensureStopSize(int id) {
if (stopMemo_.size() <= static_cast<std::size_t>(id)) {
stopMemo_.resize(static_cast<std::size_t>(id) + 1);
stopSeen_.resize(static_cast<std::size_t>(id) + 1, 0);
}
}
int makeNumber(const Dyadic& in) {
Dyadic d = in;
d.normalize();
NumKey key{d.num, d.exp};
auto it = numMap_.find(key);
if (it != numMap_.end()) {
return it->second;
}
int id = static_cast<int>(nodes_.size());
nodes_.push_back(GameNode());
parent_.push_back(id);
nodes_[id].isNumber = true;
nodes_[id].reduced = true;
nodes_[id].val = d;
numMap_[key] = id;
if (d.num == 0) {
return id;
}
if (d.exp == 0) {
if (d.num > 0) {
nodes_[id].L.push_back(makeNumber(Dyadic(d.num - 1, 0)));
} else {
nodes_[id].R.push_back(makeNumber(Dyadic(d.num + 1, 0)));
}
} else {
nodes_[id].L.push_back(makeNumber(Dyadic(d.num - 1, d.exp)));
nodes_[id].R.push_back(makeNumber(Dyadic(d.num + 1, d.exp)));
}
return id;
}
void ensureOutcomeSize(int g) {
if (static_cast<int>(leftMemo_.size()) <= g) {
leftMemo_.resize(g + 1, -1);
rightMemo_.resize(g + 1, -1);
}
}
bool leq(int a, int b) {
a = rep(a);
b = rep(b);
if (a == b) {
return true;
}
if (nodes_[a].isNumber && nodes_[b].isNumber) {
return cmp_dyadic(nodes_[a].val, nodes_[b].val) <= 0;
}
uint64_t key = (static_cast<uint64_t>(a) << 32) | static_cast<uint32_t>(b);
if (uint8_t* it = leqMemo_.find(key)) {
return *it == 1;
}
for (int al : nodes_[a].L) {
if (leq(b, al)) {
leqMemo_.insert(key, 2);
return false;
}
}
for (int br : nodes_[b].R) {
if (leq(br, a)) {
leqMemo_.insert(key, 2);
return false;
}
}
leqMemo_.insert(key, 1);
return true;
}
void removeDominatedLeft(std::vector<int>& L) {
std::vector<char> kill(L.size(), 0);
for (std::size_t i = 0; i < L.size(); ++i) {
if (kill[i]) {
continue;
}
for (std::size_t j = 0; j < L.size(); ++j) {
if (i == j || kill[j]) {
continue;
}
if (leq(L[i], L[j]) && !leq(L[j], L[i])) {
kill[i] = 1;
break;
}
}
}
std::vector<int> out;
out.reserve(L.size());
for (std::size_t i = 0; i < L.size(); ++i) {
if (!kill[i]) {
out.push_back(L[i]);
}
}
L.swap(out);
}
void removeDominatedRight(std::vector<int>& R) {
std::vector<char> kill(R.size(), 0);
for (std::size_t i = 0; i < R.size(); ++i) {
if (kill[i]) {
continue;
}
for (std::size_t j = 0; j < R.size(); ++j) {
if (i == j || kill[j]) {
continue;
}
if (leq(R[j], R[i]) && !leq(R[i], R[j])) {
kill[i] = 1;
break;
}
}
}
std::vector<int> out;
out.reserve(R.size());
for (std::size_t i = 0; i < R.size(); ++i) {
if (!kill[i]) {
out.push_back(R[i]);
}
}
R.swap(out);
}
int reduceInPlace(int id) {
id = rep(id);
if (nodes_[id].isNumber || nodes_[id].reduced) {
return id;
}
auto& L = nodes_[id].L;
auto& R = nodes_[id].R;
for (int& x : L) {
x = rep(x);
}
for (int& x : R) {
x = rep(x);
}
std::sort(L.begin(), L.end());
L.erase(std::unique(L.begin(), L.end()), L.end());
std::sort(R.begin(), R.end());
R.erase(std::unique(R.begin(), R.end()), R.end());
removeDominatedLeft(L);
removeDominatedRight(R);
bool changed = true;
while (changed) {
changed = false;
for (std::size_t i = 0; i < L.size() && !changed; ++i) {
int l = rep(L[i]);
for (int lr : nodes_[l].R) {
if (leq(lr, id)) {
L.erase(L.begin() + static_cast<long long>(i));
int lr_rep = rep(lr);
for (int x : nodes_[lr_rep].L) {
L.push_back(rep(x));
}
changed = true;
break;
}
}
}
if (changed) {
std::sort(L.begin(), L.end());
L.erase(std::unique(L.begin(), L.end()), L.end());
removeDominatedLeft(L);
continue;
}
for (std::size_t i = 0; i < R.size() && !changed; ++i) {
int r = rep(R[i]);
for (int rl : nodes_[r].L) {
if (leq(id, rl)) {
R.erase(R.begin() + static_cast<long long>(i));
int rl_rep = rep(rl);
for (int x : nodes_[rl_rep].R) {
R.push_back(rep(x));
}
changed = true;
break;
}
}
}
if (changed) {
std::sort(R.begin(), R.end());
R.erase(std::unique(R.begin(), R.end()), R.end());
removeDominatedRight(R);
}
}
if (L.empty() && R.empty()) {
aliasTo(id, zeroId_);
return zeroId_;
}
auto allNumbers = [&](const std::vector<int>& v) -> bool {
for (int x : v) {
if (!nodes_[rep(x)].isNumber) {
return false;
}
}
return true;
};
bool lNum = allNumbers(L);
bool rNum = allNumbers(R);
if (!L.empty() && !R.empty() && lNum && rNum) {
Dyadic maxL = nodes_[rep(L[0])].val;
for (int x : L) {
Dyadic v = nodes_[rep(x)].val;
if (cmp_dyadic(v, maxL) > 0) {
maxL = v;
}
}
Dyadic minR = nodes_[rep(R[0])].val;
for (int x : R) {
Dyadic v = nodes_[rep(x)].val;
if (cmp_dyadic(v, minR) < 0) {
minR = v;
}
}
if (cmp_dyadic(maxL, minR) < 0) {
Dyadic mid = simplest_between(maxL, minR);
int nid = makeNumber(mid);
aliasTo(id, nid);
return nid;
}
} else if (lNum && R.empty()) {
Dyadic maxL = nodes_[rep(L[0])].val;
for (int x : L) {
Dyadic v = nodes_[rep(x)].val;
if (cmp_dyadic(v, maxL) > 0) {
maxL = v;
}
}
long long fl = floor_dyadic(maxL);
int nid = makeNumber(Dyadic(fl + 1, 0));
aliasTo(id, nid);
return nid;
} else if (rNum && L.empty()) {
Dyadic minR = nodes_[rep(R[0])].val;
for (int x : R) {
Dyadic v = nodes_[rep(x)].val;
if (cmp_dyadic(v, minR) < 0) {
minR = v;
}
}
long long ce = ceil_dyadic(minR);
int nid = makeNumber(Dyadic(ce - 1, 0));
aliasTo(id, nid);
return nid;
}
VecKey key{L, R};
auto it = canonMap_.find(key);
if (it != canonMap_.end()) {
aliasTo(id, it->second);
return rep(it->second);
}
canonMap_.emplace(std::move(key), id);
nodes_[id].reduced = true;
return id;
}
int makeGame(std::vector<int> L, std::vector<int> R) {
for (int& x : L) {
x = rep(x);
}
for (int& x : R) {
x = rep(x);
}
std::sort(L.begin(), L.end());
L.erase(std::unique(L.begin(), L.end()), L.end());
std::sort(R.begin(), R.end());
R.erase(std::unique(R.begin(), R.end()), R.end());
if (L.size() <= 1 && R.size() <= 1) {
int l = L.empty() ? -1 : L[0];
int r = R.empty() ? -1 : R[0];
return makeBinary(l, r);
}
int id = static_cast<int>(nodes_.size());
nodes_.push_back(GameNode());
parent_.push_back(id);
nodes_[id].L = std::move(L);
nodes_[id].R = std::move(R);
return reduceInPlace(id);
}
int addImpl(int a, int b, bool cacheThis) {
a = rep(a);
b = rep(b);
if (a == zeroId_) {
return b;
}
if (b == zeroId_) {
return a;
}
if (nodes_[a].isNumber && nodes_[b].isNumber) {
return makeNumber(add_dyadic(nodes_[a].val, nodes_[b].val));
}
int x = a;
int y = b;
if (x > y) {
std::swap(x, y);
}
uint64_t key = (static_cast<uint64_t>(x) << 32) | static_cast<uint32_t>(y);
if (int* it = addMap_.find(key)) {
return rep(*it);
}
const std::vector<int> aL = nodes_[a].L;
const std::vector<int> aR = nodes_[a].R;
const std::vector<int> bL = nodes_[b].L;
const std::vector<int> bR = nodes_[b].R;
std::vector<int> L;
std::vector<int> R;
L.reserve(aL.size() + bL.size());
R.reserve(aR.size() + bR.size());
if (!nodes_[a].isNumber) {
for (int al : aL) {
L.push_back(addImpl(al, b, true));
}
for (int ar : aR) {
R.push_back(addImpl(ar, b, true));
}
}
if (!nodes_[b].isNumber) {
for (int bl : bL) {
L.push_back(addImpl(a, bl, true));
}
for (int br : bR) {
R.push_back(addImpl(a, br, true));
}
}
int res = makeGame(std::move(L), std::move(R));
if (cacheThis) {
addMap_.insert(key, res);
}
return res;
}
};
struct StaircaseFreq {
std::unordered_map<int, int> numFreq; // value -> count
std::vector<std::unordered_map<int, int>> switchFreq; // weight -> (R -> count)
int maxWeight = 0;
};
static StaircaseFreq collect_staircase_freq(int max_w, GameEngine& eng) {
StaircaseFreq freq;
freq.switchFreq.resize(static_cast<std::size_t>(max_w + 1));
for (int a = 1; a <= max_w - 2; ++a) {
for (int b = 1; b <= max_w - a - 1; ++b) {
int K = max_w - a - b;
if (K < 1) {
continue;
}
int A = a;
int B = b;
std::vector<int> dp(static_cast<std::size_t>((K + 1) * A * B), eng.zero());
auto idx = [&](int k, int i, int j) { return (k * A + i) * B + j; };
for (int k = 1; k <= K; ++k) {
for (int i = A - 1; i >= 0; --i) {
for (int j = B - 1; j >= 0; --j) {
int left = -1;
int right = -1;
if (k == 1 && j == B - 1) {
left = -1;
} else if (j < B - 1) {
left = dp[static_cast<std::size_t>(idx(k, i, j + 1))];
} else {
left = dp[static_cast<std::size_t>(idx(k - 1, i, 0))];
}
if (k == 1 && i == A - 1) {
right = -1;
} else if (i < A - 1) {
right = dp[static_cast<std::size_t>(idx(k, i + 1, j))];
} else {
right = dp[static_cast<std::size_t>(idx(k - 1, 0, j))];
}
dp[static_cast<std::size_t>(idx(k, i, j))] = eng.makeBinary(left, right);
}
}
}
for (int k = 1; k <= K; ++k) {
int id = eng.canonical(dp[static_cast<std::size_t>(idx(k, 0, 0))]);
StopPair sp = eng.stops(id);
if (sp.L.exp != 0 || sp.R.exp != 0) {
std::cerr << "Non-integer stops encountered.\n";
std::exit(1);
}
int L = static_cast<int>(sp.L.num);
int R = static_cast<int>(sp.R.num);
const auto& node = eng.node(id);
if (node.isNumber) {
int& slot = freq.numFreq[L];
++slot;
if (slot >= kMod) {
slot -= kMod;
}
} else {
if (node.L.size() != 1 || node.R.size() != 1) {
std::cerr << "Non-switch game encountered.\n";
std::exit(1);
}
int l = eng.canonical(node.L[0]);
int r = eng.canonical(node.R[0]);
if (!eng.node(l).isNumber || !eng.node(r).isNumber) {
std::cerr << "Switch options are non-numbers.\n";
std::exit(1);
}
int weight = L - R;
if (weight < 0) {
std::cerr << "Negative switch weight encountered.\n";
std::exit(1);
}
if (weight >= static_cast<int>(freq.switchFreq.size())) {
freq.switchFreq.resize(static_cast<std::size_t>(weight + 1));
}
int& slot = freq.switchFreq[static_cast<std::size_t>(weight)][R];
++slot;
if (slot >= kMod) {
slot -= kMod;
}
freq.maxWeight = std::max(freq.maxWeight, weight);
}
}
}
}
return freq;
}
static std::vector<std::unordered_map<int, int>> compute_dist(
const std::unordered_map<int, int>& base_freq,
int max_len) {
std::vector<std::unordered_map<int, int>> dist(static_cast<std::size_t>(max_len + 1));
dist[0][0] = 1;
if (base_freq.empty()) {
return dist;
}
for (int len = 1; len <= max_len; ++len) {
auto& cur = dist[len];
auto& prev = dist[len - 1];
for (const auto& kv : prev) {
int sum = kv.first;
int cnt = kv.second;
for (const auto& bv : base_freq) {
int val = bv.first;
int freq = bv.second;
int& slot = cur[sum + val];
long long add = static_cast<long long>(cnt) * freq % kMod;
int nv = slot + static_cast<int>(add);
if (nv >= kMod) {
nv -= kMod;
}
slot = nv;
}
}
}
return dist;
}
static uint64_t pack_key(int sumR, int sumOdd) {
return (static_cast<uint64_t>(static_cast<uint32_t>(sumR)) << 32) |
static_cast<uint32_t>(sumOdd);
}
static int unpack_sumR(uint64_t key) { return static_cast<int32_t>(key >> 32); }
static int unpack_sumOdd(uint64_t key) { return static_cast<int>(key & 0xFFFFFFFFu); }
static int compute_S(int m, int max_w, GameEngine& eng) {
StaircaseFreq freq = collect_staircase_freq(max_w, eng);
std::vector<std::vector<int>> binom(m + 1, std::vector<int>(m + 1, 0));
for (int n = 0; n <= m; ++n) {
binom[n][0] = binom[n][n] = 1;
for (int k = 1; k < n; ++k) {
int nv = binom[n - 1][k - 1] + binom[n - 1][k];
if (nv >= kMod) {
nv -= kMod;
}
binom[n][k] = nv;
}
}
auto num_dist = compute_dist(freq.numFreq, m);
std::vector<std::vector<std::unordered_map<int, int>>> dist_by_weight;
dist_by_weight.resize(static_cast<std::size_t>(freq.maxWeight + 1));
for (int w = 0; w <= freq.maxWeight; ++w) {
if (freq.switchFreq[static_cast<std::size_t>(w)].empty()) {
continue;
}
dist_by_weight[static_cast<std::size_t>(w)] =
compute_dist(freq.switchFreq[static_cast<std::size_t>(w)], m);
}
using StateMap = std::unordered_map<uint64_t, int>;
std::vector<std::array<StateMap, 2>> dp(static_cast<std::size_t>(m + 1));
dp[0][0][pack_key(0, 0)] = 1;
for (int w = freq.maxWeight; w >= 0; --w) {
const auto& dist_w = dist_by_weight[static_cast<std::size_t>(w)];
if (dist_w.empty()) {
continue;
}
std::vector<std::array<StateMap, 2>> next(static_cast<std::size_t>(m + 1));
for (int s = 0; s <= m; ++s) {
for (int parity = 0; parity <= 1; ++parity) {
const auto& cur = dp[s][parity];
if (cur.empty()) {
continue;
}
for (const auto& kv : cur) {
int sumR = unpack_sumR(kv.first);
int sumOdd = unpack_sumOdd(kv.first);
int cnt = kv.second;
for (int c = 0; c <= m - s; ++c) {
const auto& dist_c = dist_w[static_cast<std::size_t>(c)];
if (dist_c.empty()) {
continue;
}
int leftCount = (c + (parity == 0 ? 1 : 0)) / 2;
int newParity = parity ^ (c & 1);
int comb = binom[s + c][c];
for (const auto& rv : dist_c) {
int newS = s + c;
int newSumR = sumR + rv.first;
int newSumOdd = sumOdd + leftCount * w;
long long ways = static_cast<long long>(cnt) * rv.second % kMod;
ways = ways * comb % kMod;
auto& slot = next[newS][newParity][pack_key(newSumR, newSumOdd)];
int nv = slot + static_cast<int>(ways);
if (nv >= kMod) {
nv -= kMod;
}
slot = nv;
}
}
}
}
}
dp.swap(next);
}
long long ans = 0;
for (int s = 0; s <= m; ++s) {
int n = m - s;
int interleave = binom[m][s];
for (int parity = 0; parity <= 1; ++parity) {
const auto& cur = dp[s][parity];
if (cur.empty()) {
continue;
}
for (const auto& kv : cur) {
int sumR = unpack_sumR(kv.first);
int sumOdd = unpack_sumOdd(kv.first);
int cnt = kv.second;
const auto& num_map = num_dist[static_cast<std::size_t>(n)];
for (const auto& nv : num_map) {
long long total = static_cast<long long>(sumR) + sumOdd + nv.first;
bool win;
if (total > 0) {
win = true;
} else if (total < 0) {
win = false;
} else {
win = (s % 2 == 1);
}
if (!win) {
continue;
}
long long ways = static_cast<long long>(cnt) * nv.second % kMod;
ways = ways * interleave % kMod;
ans += ways;
if (ans >= kMod) {
ans %= kMod;
}
}
}
}
}
return static_cast<int>(ans % kMod);
}
} // namespace
int main() {
GameEngine eng;
int s24 = compute_S(2, 4, eng);
if (s24 != 7) {
std::cerr << "Validation failed: S(2,4) != 7, got " << s24 << "\n";
return 1;
}
int s39 = compute_S(3, 9, eng);
if (s39 != 315319) {
std::cerr << "Validation failed: S(3,9) != 315319, got " << s39 << "\n";
return 1;
}
std::cerr << "Validation checkpoints passed.\n";
int s864 = compute_S(8, 64, eng);
std::cout << s864 << "\n";
return 0;
}Python
from __future__ import annotations
import re
import shutil
import subprocess
from pathlib import Path
ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")
def parse_output(stdout: str) -> str:
lines = [line.strip() for line in stdout.splitlines() if line.strip()]
if not lines:
return ""
answers = []
equals = []
for line in lines:
m1 = ANSWER_RE.search(line)
if m1:
answers.append(m1.group(1).strip())
m2 = EQUAL_RE.search(line)
if m2:
equals.append(m2.group(1).strip())
if answers:
return answers[-1]
if equals:
return equals[-1]
return lines[-1]
def should_skip_cpp_checkpoints(src: Path) -> bool:
try:
text = src.read_text(encoding="utf-8", errors="ignore")
except OSError:
return False
return "--skip-checkpoints" in text
def run_cpp(binary: Path, src: Path, root: Path) -> str:
cmd = [str(binary)]
if should_skip_cpp_checkpoints(src):
cmd.append("--skip-checkpoints")
try:
return subprocess.check_output(cmd, text=True, cwd=root)
except subprocess.CalledProcessError:
return subprocess.check_output(cmd, text=True, cwd=src.parent)
def solve() -> str:
problem_id = __file__.split("Euler")[-1].split(".")[0]
root = Path(__file__).resolve().parent.parent
src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"
if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
compiler = shutil.which("clang++") or shutil.which("g++")
if not compiler:
raise RuntimeError("No C++ compiler found (clang++/g++).")
subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])
output = run_cpp(binary=binary, src=src, root=root)
parsed = parse_output(output)
if not parsed:
raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
return parsed
if __name__ == "__main__":
print(solve())
Java
import java.util.*;
import java.math.BigInteger;
public class Euler923 {
static final int MOD = 1000000007;
static class Dyadic {
long num;
int exp;
Dyadic(long num, int exp) {
this.num = num;
this.exp = exp;
normalize();
}
void normalize() {
if (num == 0) {
exp = 0;
return;
}
while (exp > 0 && (num & 1) == 0) {
num >>= 1;
exp--;
}
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (!(o instanceof Dyadic))
return false;
Dyadic dyadic = (Dyadic) o;
return num == dyadic.num && exp == dyadic.exp;
}
@Override
public int hashCode() {
return Objects.hash(num, exp);
}
}
static int cmpDyadic(Dyadic a, Dyadic b) {
if (a.num == b.num && a.exp == b.exp)
return 0;
int e = Math.max(a.exp, b.exp);
BigInteger na = BigInteger.valueOf(a.num).shiftLeft(e - a.exp);
BigInteger nb = BigInteger.valueOf(b.num).shiftLeft(e - b.exp);
return na.compareTo(nb);
}
static Dyadic addDyadic(Dyadic a, Dyadic b) {
int e = Math.max(a.exp, b.exp);
BigInteger na = BigInteger.valueOf(a.num).shiftLeft(e - a.exp);
BigInteger nb = BigInteger.valueOf(b.num).shiftLeft(e - b.exp);
BigInteger sum = na.add(nb);
return new Dyadic(sum.longValue(), e);
}
static Dyadic negDyadic(Dyadic a) {
return new Dyadic(-a.num, a.exp);
}
static long floorDyadic(Dyadic a) {
if (a.exp == 0)
return a.num;
long den = 1L << a.exp;
if (a.num >= 0)
return a.num / den;
return -(((-a.num) + den - 1) / den);
}
static long ceilDyadic(Dyadic a) {
return -floorDyadic(negDyadic(a));
}
static Dyadic simplestBetween(Dyadic l, Dyadic r) {
for (int n = 0; n <= 60; ++n) {
int finalN = n;
java.util.function.Function<Dyadic, Long> floorScaled = (x) -> {
if (finalN >= x.exp) {
return x.num << (finalN - x.exp);
}
int sh = x.exp - finalN;
if (x.num >= 0)
return x.num >> sh;
long pos = -x.num;
long q = (pos + (1L << sh) - 1) >> sh;
return -q;
};
java.util.function.Function<Dyadic, Long> ceilScaled = (x) -> {
return -floorScaled.apply(negDyadic(x));
};
long low = floorScaled.apply(l) + 1;
long high = ceilScaled.apply(r) - 1;
if (low > high)
continue;
long t;
if (low <= 0 && 0 <= high)
t = 0;
else if (high < 0)
t = high;
else
t = low;
return new Dyadic(t, finalN);
}
return new Dyadic(0, 0);
}
static class GameNode {
boolean isNumber = false;
boolean reduced = false;
Dyadic val = null;
List<Integer> L = new ArrayList<>();
List<Integer> R = new ArrayList<>();
}
static class StopPair {
Dyadic L, R;
StopPair(Dyadic l, Dyadic r) {
L = l;
R = r;
}
}
static class GameEngine {
List<GameNode> nodes = new ArrayList<>();
List<Integer> parent = new ArrayList<>();
Map<Dyadic, Integer> numMap = new HashMap<>();
Map<String, Integer> binMap = new HashMap<>();
Map<String, Integer> canonMap = new HashMap<>();
Map<String, Boolean> leqMemo = new HashMap<>();
List<StopPair> stopMemo = new ArrayList<>();
List<Boolean> stopSeen = new ArrayList<>();
int zeroId;
GameEngine() {
zeroId = makeNumber(new Dyadic(0, 0));
}
int zero() {
return zeroId;
}
int rep(int x) {
while (parent.get(x) != x) {
int px = parent.get(x);
parent.set(x, parent.get(px));
x = parent.get(x);
}
return x;
}
int canonical(int id) {
return rep(id);
}
int makeNumber(Dyadic inStr) {
Dyadic val = new Dyadic(inStr.num, inStr.exp);
if (numMap.containsKey(val))
return numMap.get(val);
int id = nodes.size();
GameNode node = new GameNode();
node.isNumber = true;
node.reduced = true;
node.val = val;
nodes.add(node);
parent.add(id);
numMap.put(val, id);
if (val.num == 0)
return id;
if (val.exp == 0) {
if (val.num > 0) {
node.L.add(makeNumber(new Dyadic(val.num - 1, 0)));
} else {
node.R.add(makeNumber(new Dyadic(val.num + 1, 0)));
}
} else {
node.L.add(makeNumber(new Dyadic(val.num - 1, val.exp)));
node.R.add(makeNumber(new Dyadic(val.num + 1, val.exp)));
}
return id;
}
int makeBinary(int l, int r) {
if (l != -1)
l = rep(l);
if (r != -1)
r = rep(r);
String key = l + "," + r;
if (binMap.containsKey(key))
return rep(binMap.get(key));
int id = nodes.size();
GameNode node = new GameNode();
nodes.add(node);
parent.add(id);
if (l != -1)
node.L.add(l);
if (r != -1)
node.R.add(r);
int rid = reduceInPlace(id);
binMap.put(key, rid);
return rid;
}
void aliasTo(int fromId, int toId) {
fromId = rep(fromId);
toId = rep(toId);
if (fromId != toId) {
parent.set(fromId, toId);
}
}
boolean leq(int a, int b) {
a = rep(a);
b = rep(b);
if (a == b)
return true;
GameNode na = nodes.get(a);
GameNode nb = nodes.get(b);
if (na.isNumber && nb.isNumber) {
return cmpDyadic(na.val, nb.val) <= 0;
}
String key = a + "," + b;
if (leqMemo.containsKey(key))
return leqMemo.get(key);
for (int al : na.L) {
if (leq(b, al)) {
leqMemo.put(key, false);
return false;
}
}
for (int br : nb.R) {
if (leq(br, a)) {
leqMemo.put(key, false);
return false;
}
}
leqMemo.put(key, true);
return true;
}
List<Integer> removeDominatedLeft(List<Integer> L) {
boolean[] kill = new boolean[L.size()];
for (int i = 0; i < L.size(); ++i) {
if (kill[i])
continue;
for (int j = 0; j < L.size(); ++j) {
if (i == j || kill[j])
continue;
if (leq(L.get(i), L.get(j)) && !leq(L.get(j), L.get(i))) {
kill[i] = true;
break;
}
}
}
List<Integer> out = new ArrayList<>();
for (int i = 0; i < L.size(); ++i) {
if (!kill[i])
out.add(L.get(i));
}
return out;
}
List<Integer> removeDominatedRight(List<Integer> R) {
boolean[] kill = new boolean[R.size()];
for (int i = 0; i < R.size(); ++i) {
if (kill[i])
continue;
for (int j = 0; j < R.size(); ++j) {
if (i == j || kill[j])
continue;
if (leq(R.get(j), R.get(i)) && !leq(R.get(i), R.get(j))) {
kill[i] = true;
break;
}
}
}
List<Integer> out = new ArrayList<>();
for (int i = 0; i < R.size(); ++i) {
if (!kill[i])
out.add(R.get(i));
}
return out;
}
List<Integer> distinctAndSorted(List<Integer> lst) {
Set<Integer> set = new HashSet<>(lst);
List<Integer> out = new ArrayList<>(set);
Collections.sort(out);
return out;
}
int reduceInPlace(int id) {
id = rep(id);
GameNode node = nodes.get(id);
if (node.isNumber || node.reduced)
return id;
List<Integer> L = new ArrayList<>();
for (int x : node.L)
L.add(rep(x));
List<Integer> R = new ArrayList<>();
for (int x : node.R)
R.add(rep(x));
L = distinctAndSorted(L);
R = distinctAndSorted(R);
L = removeDominatedLeft(L);
R = removeDominatedRight(R);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < L.size(); ++i) {
int l = rep(L.get(i));
boolean found = false;
for (int lr : nodes.get(l).R) {
if (leq(lr, id)) {
L.remove(i);
int lrRep = rep(lr);
for (int x : nodes.get(lrRep).L) {
L.add(rep(x));
}
changed = true;
found = true;
break;
}
}
if (found)
break;
}
if (changed) {
L = distinctAndSorted(L);
L = removeDominatedLeft(L);
continue;
}
for (int i = 0; i < R.size(); ++i) {
int r = rep(R.get(i));
boolean found = false;
for (int rl : nodes.get(r).L) {
if (leq(id, rl)) {
R.remove(i);
int rlRep = rep(rl);
for (int x : nodes.get(rlRep).R) {
R.add(rep(x));
}
changed = true;
found = true;
break;
}
}
if (found)
break;
}
if (changed) {
R = distinctAndSorted(R);
R = removeDominatedRight(R);
}
}
if (L.isEmpty() && R.isEmpty()) {
aliasTo(id, zeroId);
return zeroId;
}
boolean lNum = true;
for (int x : L)
if (!nodes.get(rep(x)).isNumber) {
lNum = false;
break;
}
boolean rNum = true;
for (int x : R)
if (!nodes.get(rep(x)).isNumber) {
rNum = false;
break;
}
if (!L.isEmpty() && !R.isEmpty() && lNum && rNum) {
Dyadic maxL = nodes.get(rep(L.get(0))).val;
for (int x : L) {
Dyadic v = nodes.get(rep(x)).val;
if (cmpDyadic(v, maxL) > 0)
maxL = v;
}
Dyadic minR = nodes.get(rep(R.get(0))).val;
for (int x : R) {
Dyadic v = nodes.get(rep(x)).val;
if (cmpDyadic(v, minR) < 0)
minR = v;
}
if (cmpDyadic(maxL, minR) < 0) {
Dyadic mid = simplestBetween(maxL, minR);
int nid = makeNumber(mid);
aliasTo(id, nid);
return nid;
}
} else if (lNum && R.isEmpty()) {
Dyadic maxL = nodes.get(rep(L.get(0))).val;
for (int x : L) {
Dyadic v = nodes.get(rep(x)).val;
if (cmpDyadic(v, maxL) > 0)
maxL = v;
}
long fl = floorDyadic(maxL);
int nid = makeNumber(new Dyadic(fl + 1, 0));
aliasTo(id, nid);
return nid;
} else if (rNum && L.isEmpty()) {
Dyadic minR = nodes.get(rep(R.get(0))).val;
for (int x : R) {
Dyadic v = nodes.get(rep(x)).val;
if (cmpDyadic(v, minR) < 0)
minR = v;
}
long ce = ceilDyadic(minR);
int nid = makeNumber(new Dyadic(ce - 1, 0));
aliasTo(id, nid);
return nid;
}
String key = L.toString() + "|" + R.toString();
if (canonMap.containsKey(key)) {
int cId = canonMap.get(key);
aliasTo(id, cId);
return rep(cId);
}
canonMap.put(key, id);
node.L = L;
node.R = R;
node.reduced = true;
return id;
}
void ensureStopSize(int id) {
while (stopMemo.size() <= id) {
stopMemo.add(null);
stopSeen.add(false);
}
}
StopPair stops(int id) {
id = rep(id);
ensureStopSize(id);
if (stopSeen.get(id))
return stopMemo.get(id);
GameNode node = nodes.get(id);
StopPair res;
if (node.isNumber) {
res = new StopPair(node.val, node.val);
} else {
boolean hasL = false;
boolean hasR = false;
Dyadic Lval = null;
Dyadic Rval = null;
for (int l : node.L) {
StopPair sp = stops(l);
if (!hasL || cmpDyadic(sp.R, Lval) > 0) {
Lval = sp.R;
hasL = true;
}
}
for (int r : node.R) {
StopPair sp = stops(r);
if (!hasR || cmpDyadic(sp.L, Rval) < 0) {
Rval = sp.L;
hasR = true;
}
}
res = new StopPair(Lval, Rval);
}
stopMemo.set(id, res);
stopSeen.set(id, true);
return res;
}
}
static class StaircaseFreq {
Map<Integer, Integer> numFreq = new HashMap<>();
List<Map<Integer, Integer>> switchFreq = new ArrayList<>();
int maxWeight = 0;
}
static StaircaseFreq collectStaircaseFreq(int maxW, GameEngine eng) {
StaircaseFreq freq = new StaircaseFreq();
for (int i = 0; i <= maxW; ++i) {
freq.switchFreq.add(new HashMap<>());
}
for (int a = 1; a <= maxW - 1; ++a) {
for (int b = 1; b <= maxW - a; ++b) {
int K = maxW - a - b;
if (K < 1)
continue;
int A = a;
int B = b;
int[] dp = new int[(K + 1) * A * B];
Arrays.fill(dp, eng.zero());
for (int k = 1; k <= K; ++k) {
for (int i = A - 1; i >= 0; --i) {
for (int j = B - 1; j >= 0; --j) {
int left = -1;
int right = -1;
if (k == 1 && j == B - 1)
left = -1;
else if (j < B - 1)
left = dp[(k * A + i) * B + (j + 1)];
else
left = dp[((k - 1) * A + i) * B + 0];
if (k == 1 && i == A - 1)
right = -1;
else if (i < A - 1)
right = dp[(k * A + (i + 1)) * B + j];
else
right = dp[((k - 1) * A + 0) * B + j];
dp[(k * A + i) * B + j] = eng.makeBinary(left, right);
}
}
}
for (int k = 1; k <= K; ++k) {
int id = eng.canonical(dp[(k * A + 0) * B + 0]);
StopPair sp = eng.stops(id);
int L = (int) sp.L.num;
int R = (int) sp.R.num;
GameNode node = eng.nodes.get(id);
if (node.isNumber) {
freq.numFreq.put(L, (freq.numFreq.getOrDefault(L, 0) + 1) % MOD);
} else {
int weight = L - R;
while (weight >= freq.switchFreq.size()) {
freq.switchFreq.add(new HashMap<>());
}
Map<Integer, Integer> map = freq.switchFreq.get(weight);
map.put(R, (map.getOrDefault(R, 0) + 1) % MOD);
freq.maxWeight = Math.max(freq.maxWeight, weight);
}
}
}
}
return freq;
}
static List<Map<Integer, Integer>> computeDist(Map<Integer, Integer> baseFreq, int maxLen) {
List<Map<Integer, Integer>> dist = new ArrayList<>();
for (int i = 0; i <= maxLen; ++i)
dist.add(new HashMap<>());
dist.get(0).put(0, 1);
if (baseFreq.isEmpty())
return dist;
for (int length = 1; length <= maxLen; ++length) {
Map<Integer, Integer> cur = dist.get(length);
Map<Integer, Integer> prev = dist.get(length - 1);
for (Map.Entry<Integer, Integer> pv : prev.entrySet()) {
int vsum = pv.getKey();
int cnt = pv.getValue();
for (Map.Entry<Integer, Integer> bv : baseFreq.entrySet()) {
int val = bv.getKey();
int freq = bv.getValue();
long ways = (long) cnt * freq % MOD;
cur.put(vsum + val, (int) ((cur.getOrDefault(vsum + val, 0) + ways) % MOD));
}
}
}
return dist;
}
static class StateKey {
int sumR, sumOdd;
StateKey(int r, int o) {
sumR = r;
sumOdd = o;
}
public boolean equals(Object o) {
if (this == o)
return true;
if (!(o instanceof StateKey))
return false;
StateKey stateKey = (StateKey) o;
return sumR == stateKey.sumR && sumOdd == stateKey.sumOdd;
}
public int hashCode() {
return Objects.hash(sumR, sumOdd);
}
}
static int computeS(int m, int maxW, GameEngine eng) {
StaircaseFreq freq = collectStaircaseFreq(maxW, eng);
int[][] binom = new int[m + 1][m + 1];
for (int n = 0; n <= m; ++n) {
binom[n][0] = binom[n][n] = 1;
for (int k = 1; k < n; ++k) {
binom[n][k] = (binom[n - 1][k - 1] + binom[n - 1][k]) % MOD;
}
}
List<Map<Integer, Integer>> numDist = computeDist(freq.numFreq, m);
List<List<Map<Integer, Integer>>> distByWeight = new ArrayList<>();
for (int w = 0; w <= freq.maxWeight; ++w) {
if (freq.switchFreq.get(w).isEmpty()) {
distByWeight.add(new ArrayList<>());
} else {
distByWeight.add(computeDist(freq.switchFreq.get(w), m));
}
}
Map<StateKey, Integer>[][] dp = new Map[m + 1][2];
for (int s = 0; s <= m; ++s) {
for (int p = 0; p < 2; ++p)
dp[s][p] = new HashMap<>();
}
dp[0][0].put(new StateKey(0, 0), 1);
for (int w = freq.maxWeight; w >= 0; --w) {
List<Map<Integer, Integer>> distW = distByWeight.get(w);
if (distW.isEmpty())
continue;
Map<StateKey, Integer>[][] nextDp = new Map[m + 1][2];
for (int s = 0; s <= m; ++s) {
for (int p = 0; p < 2; ++p)
nextDp[s][p] = new HashMap<>();
}
for (int s = 0; s <= m; ++s) {
for (int parity = 0; parity < 2; ++parity) {
Map<StateKey, Integer> cur = dp[s][parity];
if (cur.isEmpty())
continue;
for (Map.Entry<StateKey, Integer> kv : cur.entrySet()) {
int sumR = kv.getKey().sumR;
int sumOdd = kv.getKey().sumOdd;
int cnt = kv.getValue();
for (int c = 0; c <= m - s; ++c) {
Map<Integer, Integer> distC = distW.get(c);
if (distC == null || distC.isEmpty())
continue;
int leftCount = (c + (parity == 0 ? 1 : 0)) / 2;
int newParity = parity ^ (c & 1);
int comb = binom[s + c][c];
for (Map.Entry<Integer, Integer> rv : distC.entrySet()) {
int newS = s + c;
int newSumR = sumR + rv.getKey();
int newSumOdd = sumOdd + leftCount * w;
long ways = (long) cnt * rv.getValue() % MOD;
ways = ways * comb % MOD;
StateKey key = new StateKey(newSumR, newSumOdd);
nextDp[newS][newParity].put(key,
(int) ((nextDp[newS][newParity].getOrDefault(key, 0) + ways) % MOD));
}
}
}
}
}
dp = nextDp;
}
long ans = 0;
for (int s = 0; s <= m; ++s) {
int n = m - s;
int interleave = binom[m][s];
for (int parity = 0; parity < 2; ++parity) {
Map<StateKey, Integer> cur = dp[s][parity];
if (cur.isEmpty())
continue;
for (Map.Entry<StateKey, Integer> kv : cur.entrySet()) {
int sumR = kv.getKey().sumR;
int sumOdd = kv.getKey().sumOdd;
int cnt = kv.getValue();
Map<Integer, Integer> numMap = numDist.get(n);
for (Map.Entry<Integer, Integer> nv : numMap.entrySet()) {
long totalVal = (long) sumR + sumOdd + nv.getKey();
boolean win;
if (totalVal > 0)
win = true;
else if (totalVal < 0)
win = false;
else
win = (s % 2 == 1);
if (!win)
continue;
long ways = (long) cnt * nv.getValue() % MOD;
ways = ways * interleave % MOD;
ans = (ans + ways) % MOD;
}
}
}
}
return (int) (ans % MOD);
}
public static String solve() {
GameEngine eng = new GameEngine();
int ans = computeS(8, 64, eng);
return Integer.toString(ans);
}
public static void main(String[] args) {
System.out.println(solve());
}
}