Problem 928: Cribbage
View on Project EulerProject Euler Problem 928 Solution
EulerSolve provides an optimized solution for Project Euler Problem 928, Cribbage, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary Compress a hand from a standard 52-card deck into a rank-count vector \(c=(c_1,\dots,c_{13})\), where \(0\le c_r\le 4\) and the ranks are \(A,2,\dots,10,J,Q,K\). The card values used by the problem are \[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \] A count vector does not distinguish suits, so it stands for \[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \] different physical hands: for each rank we choose \(c_r\) suits out of the four available. The goal is to count, with that multiplicity and excluding the empty hand, all vectors for which the face-value total \[ H(c)=\sum_{r=1}^{13} v_r c_r \] is exactly equal to the cribbage score used in the problem, namely \[ C(c)=P(c)+R(c)+2F_{15}(c). \] Here \(P(c)\) is the score from equal-rank pairs, \(R(c)\) is the score from runs, and \(F_{15}(c)\) counts card subsets whose values add up to 15. So the whole problem is an exact weighted count of the nonempty hands satisfying \(H(c)=C(c)\). Mathematical Approach Rank-count vectors are the natural state space Since suits matter only through multiplicity, the real combinatorial object is the 13-dimensional vector \(c\). Every legal hand corresponds to exactly one such vector, and every vector represents \(W(c)\) suit assignments. That compression is what makes the problem finite: there are only \(5^{13}\) possible count vectors, because each rank may appear 0, 1, 2, 3, or 4 times....
Detailed mathematical approach
Problem Summary
Compress a hand from a standard 52-card deck into a rank-count vector \(c=(c_1,\dots,c_{13})\), where \(0\le c_r\le 4\) and the ranks are \(A,2,\dots,10,J,Q,K\). The card values used by the problem are
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
A count vector does not distinguish suits, so it stands for
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
different physical hands: for each rank we choose \(c_r\) suits out of the four available. The goal is to count, with that multiplicity and excluding the empty hand, all vectors for which the face-value total
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
is exactly equal to the cribbage score used in the problem, namely
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
Here \(P(c)\) is the score from equal-rank pairs, \(R(c)\) is the score from runs, and \(F_{15}(c)\) counts card subsets whose values add up to 15. So the whole problem is an exact weighted count of the nonempty hands satisfying \(H(c)=C(c)\).
Mathematical Approach
Rank-count vectors are the natural state space
Since suits matter only through multiplicity, the real combinatorial object is the 13-dimensional vector \(c\). Every legal hand corresponds to exactly one such vector, and every vector represents \(W(c)\) suit assignments. That compression is what makes the problem finite: there are only \(5^{13}\) possible count vectors, because each rank may appear 0, 1, 2, 3, or 4 times.
Pair score and run score come directly from the counts
The pair contribution is immediate. If rank \(r\) appears \(c_r\) times, then it contains \(\binom{c_r}{2}\) equal-rank pairs, each worth 2 points, so
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
The run contribution is slightly subtler. Break the rank line into maximal consecutive blocks of positive counts. For one such block \(a,a+1,\dots,b\), let
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
Each choice of one card from every rank in that block produces a distinct run, so the block contributes \(L\cdot M\) if \(L\ge 3\), and 0 otherwise. Therefore
\[ R(c)=\sum_{\text{maximal positive blocks}} \mathbf{1}_{L\ge 3}\,L\,M. \]
This matches the usual cribbage behavior: a block such as \(A,A,2,3,4,5\) gives two runs of length 5, not a pile of shorter subruns, because the whole maximal block is scored at once.
Fifteens are a subset-sum coefficient
For each rank \(r\), we may select \(d\) of its \(c_r\) copies into a subset, where \(0\le d\le c_r\). There are \(\binom{c_r}{d}\) ways to do that, and it contributes value \(d\,v_r\). Hence the generating function
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
has the property that
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
The implementations evaluate that coefficient by a short dynamic program on sums \(0,1,\dots,15\): after processing rank \(r\), the array entry for sum \(s\) stores how many subsets of the processed ranks have total \(s\). Because we only care about 15, the polynomial is truncated immediately.
Worked example
Take the hand with two aces and one each of 2, 3, 4, and 5. In count-vector form, that means
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
and all other entries are 0. Then
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
The pair score is \(P(c)=2\), coming from the two aces. The ranks \(A,2,3,4,5\) form one maximal positive block of length 5, with multiplicity product \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\), so
\[ R(c)=5\cdot 2=10. \]
For fifteens, the subset \(A+2+3+4+5\) sums to 15, and either ace may be chosen, so \(F_{15}(c)=2\). Therefore
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
This is exactly the kind of hand the program counts.
Split the ranks into two reusable half-states
The main implementation trick is a meet-in-the-middle split after the sixth rank. A full count vector is written as
\[ c=(c^{L},c^{R}), \]
where the left half contains the first 6 ranks and the right half contains the remaining 7. For each half, the implementation precomputes a compact summary consisting of:
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
together with:
\[ f(s)=\#\{\text{subsets in this half with total } s\}\qquad (0\le s\le 15), \]
and the length, multiplicity product, and score of the prefix and suffix positive blocks. The point is that the expensive work for a half-hand is done once and then reused for every compatible half on the other side.
The only cross-boundary interaction is one merged run
The left half and the right half are independent except at the split point. If the left half ends with a positive block and the right half begins with a positive block, those two pieces actually form one longer run block in the full hand. Let the left suffix have length and multiplicity \((\ell_L,m_L)\), and the right prefix have \((\ell_R,m_R)\). Define
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
Then the correction needed at the boundary is
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
This quantity may add a new run that was too short in both halves, or it may replace two separate partial scores by one merged score. After this correction, the full run score is
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
The fifteen count becomes a short dot product
The generating function also factors over the split:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
If \(f_L(s)\) and \(f_R(s)\) are the subset-count arrays for the two halves, then
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
The implementations store a reversed copy of the right array, so this becomes a 16-term dot product rather than a fresh subset-sum computation for every full hand.
Final merge condition
For a merged hand, write
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
Since the full run score differs from \(R(c^{L})+R(c^{R})\) by exactly \(\operatorname{adjust}\), the target identity becomes
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
So a left state and a right state form a valid hand precisely when the corrected left-right base value equals twice the dot-product count of fifteens. Whenever that happens, the contribution to the answer is \(W(c^{L})W(c^{R})\). The all-zero vector satisfies the identity trivially, so it is removed at the end by subtracting 1.
How the Code Works
Half-state enumeration
The C++, Python, and Java implementations first enumerate every possible count pattern in each half: \(5^6\) states on the left and \(5^7\) on the right. For every half-state they compute the hand total, pair score, internal run score, multiplicity, the truncated subset-sum polynomial up to 15, and the prefix/suffix block data needed for a later merge.
Merging two halves
Each left half-state is paired with each right half-state. The implementation computes the boundary correction for a run that crosses the split, then forms
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
If this value is negative, odd, or larger than 340, the pair is impossible and is skipped immediately. The upper bound 340 comes from the largest possible face-value sum of a full deck count vector. Otherwise the code evaluates the 16-term dot product for \(F_{15}\), stopping early if the partial sum has already exceeded the target.
Accumulation and exactness
When the equality test succeeds, the product of the two multiplicities is added to the total. This counts all suit assignments represented by the merged rank-count vector. The empty hand is excluded at the very end. The C++ and Java implementations parallelize the outer scan over left states; the Python entry point uses the same mathematical computation path rather than a different scoring rule.
Complexity Analysis
Enumerating the half-states costs \(O(5^6)\) and \(O(5^7)\) summaries, each with only a constant-size dynamic program on sums \(0\) through \(15\). The dominant phase is the cartesian product of the two state sets, so the merge work is
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
That means the method does not reduce the exponent of the search space. Its advantage is that the expensive scoring data for a half-hand is computed once and reused many times, so each full-hand test becomes only a boundary correction plus a 16-term dot product. Memory usage is
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
coming from the stored half-state tables and their short subset-sum arrays.
Footnotes and References
- Problem page: https://projecteuler.net/problem=928
- Cribbage: Wikipedia - Cribbage
- Binomial coefficient: Wikipedia - Binomial coefficient
- Generating function: Wikipedia - Generating function
- Subset sum problem: Wikipedia - Subset sum problem
- Dynamic programming: Wikipedia - Dynamic programming
Problem 928 source code
C++
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <thread>
#include <vector>
namespace {
using i64 = std::int64_t;
using u64 = std::uint64_t;
constexpr std::array<int, 5> kCardChoose = {1, 4, 6, 4, 1};
constexpr std::array<std::array<int, 5>, 5> kSubChoose = {
std::array<int, 5>{1, 0, 0, 0, 0},
std::array<int, 5>{1, 1, 0, 0, 0},
std::array<int, 5>{1, 2, 1, 0, 0},
std::array<int, 5>{1, 3, 3, 1, 0},
std::array<int, 5>{1, 4, 6, 4, 1},
};
struct ScoreParts {
int hand_score = 0;
int pair_score = 0;
int run_score = 0;
int fifteen_count = 0;
};
ScoreParts evaluate_hand(const std::vector<int>& counts, const std::vector<int>& values) {
const int n = static_cast<int>(counts.size());
ScoreParts out;
for (int i = 0; i < n; ++i) {
const int c = counts[i];
out.hand_score += values[i] * c;
out.pair_score += c * (c - 1);
}
int len = 0;
int prod = 1;
for (int i = 0; i < n; ++i) {
const int c = counts[i];
if (c == 0) {
if (len >= 3) {
out.run_score += len * prod;
}
len = 0;
prod = 1;
} else {
++len;
prod *= c;
}
}
if (len >= 3) {
out.run_score += len * prod;
}
std::array<int, 16> ways{};
ways[0] = 1;
for (int i = 0; i < n; ++i) {
const int c = counts[i];
const int v = values[i];
std::array<int, 16> next{};
for (int s = 0; s <= 15; ++s) {
if (ways[s] == 0) {
continue;
}
for (int d = 0; d <= c; ++d) {
const int t = s + d * v;
if (t > 15) {
break;
}
next[t] += ways[s] * kSubChoose[c][d];
}
}
ways = next;
}
out.fifteen_count = ways[15];
return out;
}
u64 brute_count_equal(const std::vector<int>& values) {
const int n = static_cast<int>(values.size());
std::vector<int> counts(n, 0);
u64 total = 0;
auto rec = [&](auto&& self, int idx, int cards, u64 weight) -> void {
if (idx == n) {
if (cards == 0) {
return;
}
const ScoreParts sc = evaluate_hand(counts, values);
const int crib = sc.pair_score + sc.run_score + 2 * sc.fifteen_count;
if (sc.hand_score == crib) {
total += weight;
}
return;
}
for (int c = 0; c <= 4; ++c) {
counts[idx] = c;
self(self, idx + 1, cards + c, weight * static_cast<u64>(kCardChoose[c]));
}
};
rec(rec, 0, 0, 1);
return total;
}
struct HalfState {
int hand_score = 0;
int pair_score = 0;
int run_score = 0;
int base = 0;
int prefix_len = 0;
int prefix_prod = 1;
int prefix_score = 0;
int suffix_len = 0;
int suffix_prod = 1;
int suffix_score = 0;
std::array<std::uint32_t, 16> poly{};
std::array<std::uint32_t, 16> poly_rev{};
u64 hand_multiplicity = 0;
};
HalfState make_half_state(const std::vector<int>& counts, const std::vector<int>& values) {
const int n = static_cast<int>(counts.size());
HalfState st;
st.hand_multiplicity = 1;
for (int i = 0; i < n; ++i) {
const int c = counts[i];
st.hand_score += values[i] * c;
st.pair_score += c * (c - 1);
st.hand_multiplicity *= static_cast<u64>(kCardChoose[c]);
}
int len = 0;
int prod = 1;
for (int i = 0; i < n; ++i) {
const int c = counts[i];
if (c == 0) {
if (len >= 3) {
st.run_score += len * prod;
}
len = 0;
prod = 1;
} else {
++len;
prod *= c;
}
}
if (len >= 3) {
st.run_score += len * prod;
}
st.prefix_len = 0;
st.prefix_prod = 1;
while (st.prefix_len < n && counts[st.prefix_len] > 0) {
st.prefix_prod *= counts[st.prefix_len];
++st.prefix_len;
}
st.prefix_score = (st.prefix_len >= 3) ? (st.prefix_len * st.prefix_prod) : 0;
st.suffix_len = 0;
st.suffix_prod = 1;
int i = n - 1;
while (i >= 0 && counts[i] > 0) {
st.suffix_prod *= counts[i];
++st.suffix_len;
--i;
}
st.suffix_score = (st.suffix_len >= 3) ? (st.suffix_len * st.suffix_prod) : 0;
std::array<int, 16> ways{};
ways[0] = 1;
for (int j = 0; j < n; ++j) {
const int c = counts[j];
const int v = values[j];
std::array<int, 16> next{};
for (int s = 0; s <= 15; ++s) {
if (ways[s] == 0) {
continue;
}
for (int d = 0; d <= c; ++d) {
const int t = s + d * v;
if (t > 15) {
break;
}
next[t] += ways[s] * kSubChoose[c][d];
}
}
ways = next;
}
for (int s = 0; s <= 15; ++s) {
st.poly[s] = static_cast<std::uint32_t>(ways[s]);
st.poly_rev[s] = static_cast<std::uint32_t>(ways[15 - s]);
}
st.base = st.hand_score - st.pair_score - st.run_score;
return st;
}
std::vector<HalfState> enumerate_half_states(const std::vector<int>& values) {
const int n = static_cast<int>(values.size());
std::size_t total = 1;
for (int i = 0; i < n; ++i) {
total *= 5;
}
std::vector<HalfState> states;
states.reserve(total);
std::vector<int> counts(n, 0);
auto rec = [&](auto&& self, int idx) -> void {
if (idx == n) {
states.push_back(make_half_state(counts, values));
return;
}
for (int c = 0; c <= 4; ++c) {
counts[idx] = c;
self(self, idx + 1);
}
};
rec(rec, 0);
return states;
}
u64 count_equal_mitm(const std::vector<int>& values) {
const int n = static_cast<int>(values.size());
const int split = n / 2;
const std::vector<int> left_values(values.begin(), values.begin() + split);
const std::vector<int> right_values(values.begin() + split, values.end());
const std::vector<HalfState> left = enumerate_half_states(left_values);
const std::vector<HalfState> right = enumerate_half_states(right_values);
const unsigned threads = std::max(1u, std::thread::hardware_concurrency());
std::vector<u64> local(threads, 0);
std::vector<std::thread> workers;
workers.reserve(threads);
for (unsigned tid = 0; tid < threads; ++tid) {
const std::size_t begin = (left.size() * tid) / threads;
const std::size_t end = (left.size() * (tid + 1)) / threads;
workers.emplace_back([&, tid, begin, end]() {
u64 subtotal = 0;
for (std::size_t i = begin; i < end; ++i) {
const HalfState& L = left[i];
for (const HalfState& R : right) {
int adjust = 0;
if (L.suffix_len > 0 && R.prefix_len > 0) {
const int merged_len = L.suffix_len + R.prefix_len;
const int merged_prod = L.suffix_prod * R.prefix_prod;
const int merged_score = (merged_len >= 3) ? (merged_len * merged_prod) : 0;
adjust = merged_score - L.suffix_score - R.prefix_score;
}
const int target_twice = L.base + R.base - adjust;
if (target_twice < 0 || target_twice > 340 || (target_twice & 1) != 0) {
continue;
}
const int target_f = target_twice / 2;
i64 f = 0;
for (int k = 0; k <= 15; ++k) {
f += static_cast<i64>(L.poly[k]) * static_cast<i64>(R.poly_rev[k]);
if (f > target_f) {
break;
}
}
if (f == target_f) {
subtotal += L.hand_multiplicity * R.hand_multiplicity;
}
}
}
local[tid] = subtotal;
});
}
for (std::thread& t : workers) {
t.join();
}
u64 total = 0;
for (u64 v : local) {
total += v;
}
return total - 1;
}
void run_validations() {
{
std::vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8};
assert(count_equal_mitm(values) == brute_count_equal(values));
}
{
std::vector<int> values(13);
for (int i = 0; i < 9; ++i) {
values[i] = i + 1;
}
for (int i = 9; i < 13; ++i) {
values[i] = 10;
}
std::vector<int> sample1(13, 0);
sample1[4] = 3;
sample1[12] = 1;
const ScoreParts s1 = evaluate_hand(sample1, values);
assert(s1.pair_score + s1.run_score + 2 * s1.fifteen_count == 14);
std::vector<int> sample2(13, 0);
sample2[0] = 2;
sample2[1] = 1;
sample2[2] = 1;
sample2[3] = 1;
sample2[4] = 1;
const ScoreParts s2 = evaluate_hand(sample2, values);
assert(s2.hand_score == 16);
assert(s2.pair_score + s2.run_score + 2 * s2.fifteen_count == 16);
}
}
} // namespace
int main() {
run_validations();
std::vector<int> values(13);
for (int i = 0; i < 9; ++i) {
values[i] = i + 1;
}
for (int i = 9; i < 13; ++i) {
values[i] = 10;
}
std::cout << count_equal_mitm(values) << '\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.*;
public class Euler928 {
static final int[] kCardChoose = { 1, 4, 6, 4, 1 };
static final int[][] kSubChoose = {
{ 1, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 0 },
{ 1, 2, 1, 0, 0 },
{ 1, 3, 3, 1, 0 },
{ 1, 4, 6, 4, 1 }
};
static class HalfState {
int handScore = 0;
int pairScore = 0;
int runScore = 0;
int base = 0;
int prefixLen = 0;
int prefixProd = 1;
int prefixScore = 0;
int suffixLen = 0;
int suffixProd = 1;
int suffixScore = 0;
int[] poly = new int[16];
int[] polyRev = new int[16];
long handMultiplicity = 0;
}
static HalfState makeHalfState(int[] counts, int[] values) {
int n = counts.length;
HalfState st = new HalfState();
st.handMultiplicity = 1;
for (int i = 0; i < n; ++i) {
int c = counts[i];
st.handScore += values[i] * c;
st.pairScore += c * (c - 1);
st.handMultiplicity *= kCardChoose[c];
}
int len = 0;
int prod = 1;
for (int i = 0; i < n; ++i) {
int c = counts[i];
if (c == 0) {
if (len >= 3)
st.runScore += len * prod;
len = 0;
prod = 1;
} else {
len++;
prod *= c;
}
}
if (len >= 3)
st.runScore += len * prod;
st.prefixLen = 0;
st.prefixProd = 1;
while (st.prefixLen < n && counts[st.prefixLen] > 0) {
st.prefixProd *= counts[st.prefixLen];
st.prefixLen++;
}
st.prefixScore = st.prefixLen >= 3 ? (st.prefixLen * st.prefixProd) : 0;
st.suffixLen = 0;
st.suffixProd = 1;
int idx = n - 1;
while (idx >= 0 && counts[idx] > 0) {
st.suffixProd *= counts[idx];
st.suffixLen++;
idx--;
}
st.suffixScore = st.suffixLen >= 3 ? (st.suffixLen * st.suffixProd) : 0;
int[] ways = new int[16];
ways[0] = 1;
for (int j = 0; j < n; ++j) {
int c = counts[j];
int v = values[j];
int[] next = new int[16];
for (int s = 0; s <= 15; ++s) {
if (ways[s] == 0)
continue;
for (int d = 0; d <= c; ++d) {
int t = s + d * v;
if (t > 15)
break;
next[t] += ways[s] * kSubChoose[c][d];
}
}
ways = next;
}
for (int s = 0; s <= 15; ++s) {
st.poly[s] = ways[s];
st.polyRev[s] = ways[15 - s];
}
st.base = st.handScore - st.pairScore - st.runScore;
return st;
}
static void rec(int idx, int[] counts, int[] values, List<HalfState> states) {
if (idx == counts.length) {
states.add(makeHalfState(counts, values));
return;
}
for (int c = 0; c <= 4; ++c) {
counts[idx] = c;
rec(idx + 1, counts, values, states);
}
}
static List<HalfState> enumerateHalfStates(int[] values) {
List<HalfState> states = new ArrayList<>();
int[] counts = new int[values.length];
rec(0, counts, values, states);
return states;
}
static long countEqualMitm(int[] values) {
int n = values.length;
int split = n / 2;
int[] leftValues = Arrays.copyOfRange(values, 0, split);
int[] rightValues = Arrays.copyOfRange(values, split, n);
List<HalfState> left = enumerateHalfStates(leftValues);
List<HalfState> right = enumerateHalfStates(rightValues);
long total = 0;
for (HalfState L : left) {
for (HalfState R : right) {
int adjust = 0;
if (L.suffixLen > 0 && R.prefixLen > 0) {
int mergedLen = L.suffixLen + R.prefixLen;
int mergedProd = L.suffixProd * R.prefixProd;
int mergedScore = (mergedLen >= 3) ? (mergedLen * mergedProd) : 0;
adjust = mergedScore - L.suffixScore - R.prefixScore;
}
int targetTwice = L.base + R.base - adjust;
if (targetTwice < 0 || targetTwice > 340 || (targetTwice & 1) != 0) {
continue;
}
int targetF = targetTwice / 2;
long f = 0;
for (int k = 0; k <= 15; ++k) {
f += (long) L.poly[k] * R.polyRev[k];
if (f > targetF) {
break;
}
}
if (f == targetF) {
total += L.handMultiplicity * R.handMultiplicity;
}
}
}
return total - 1;
}
public static String solve() {
int[] values = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10 };
return Long.toString(countEqualMitm(values));
}
public static void main(String[] args) {
System.out.println(solve());
}
}