Solution

Answer: 626616617

Let the Sprague–Grundy value of a single pile of size $n$ be $G_k(n)$ for the game parameter $k$.

For a position consisting of piles $a_1,\dots,a_m$, the SG value is

$$G_k(a_1)\oplus G_k(a_2)\oplus\cdots\oplus G_k(a_m),$$

so a position is losing iff this xor is $0$.

The task is therefore:

Compute $G_k(n)$ for all $n\le 200$,
Count partitions of $200$ whose xor is $0$,
Convert that into winning counts.

1. Computing the SG values

For a single pile of size $n$, a move consists of splitting it into

$$n=b_1+\cdots+b_p,\qquad 2\le p\le k,$$

with all $b_i\ge1$.

Thus

$$G_k(n)=\operatorname{mex}\Bigl{ G_k(b_1)\oplus\cdots\oplus G_k(b_p) \Bigr}.$$

We compute these recursively from $1$ upward.

Case $k=2$

Only binary splits are allowed.

The SG values become

$$0,1,0,1,0,1,\dots$$

i.e.

$$G_2(n)= (n-1)\bmod 2.$$

Case $k\ge4$

A key phenomenon occurs:

$$G_k(n)=n-1 \qquad (k\ge4).$$

Indeed, once 4-way splits are available, every value

$0,1,\dots,n-2$ becomes reachable, so the mex is $n-1$.

Therefore all $k\ge4$ are identical.

So we only need:

$k=2$,
$k=3$,
one representative $k=4$ for all $k\ge4$.

Hence

$$g(200)=f(200,2)+f(200,3)+197,f(200,4).$$

2. Counting losing partitions

Let $sg[a]$ denote the SG value of a pile of size $a$.

We count partitions of $N=200$ whose xor is $0$.

Dynamic programming:

$$dp[s][x]$$

= number of partitions of total $s$ whose xor is $x$.

When adding a part size $a$ exactly $m$ times:

contribution to the sum: $m a$,
contribution to xor:
$0$ if $m$ even,
$sg[a]$ if $m$ odd.

This gives a standard partition-style DP.

If $L_k$ is the number of losing positions, then

$$f(200,k)=p(200)-L_k,$$

where $p(200)$ is the partition number.

3. Python implementation

from functools import lru_cache

N = 200
MOD = 10**9 + 7

# ------------------------------------------------------------
# Partition numbers p(n)
# ------------------------------------------------------------

p = [0] * (N + 1)
p[0] = 1

for a in range(1, N + 1):
    for s in range(a, N + 1):
        p[s] += p[s - a]

P200 = p[200]

# ------------------------------------------------------------
# Compute SG values for fixed k
# ------------------------------------------------------------

def compute_sg(k, N):
    sg = [0] * (N + 1)

    for n in range(1, N + 1):

        reachable = set()

        # Generate all splits into p parts
        for parts in range(2, min(k, n) + 1):

            arr = [0] * parts

            def gen(rem, idx, mx, xr):
                if idx == parts - 1:
                    if 1 <= rem <= mx:
                        reachable.add(xr ^ sg[rem])
                    return

                upper = min(mx, rem - (parts - idx - 1))

                for v in range(upper, 0, -1):
                    gen(rem - v, idx + 1, v, xr ^ sg[v])

            gen(n, 0, n - 1, 0)

        g = 0
        while g in reachable:
            g += 1

        sg[n] = g

    return sg

# k = 2 and k = 3 explicitly
sg2 = compute_sg(2, N)
sg3 = compute_sg(3, N)

# For all k >= 4:
# G_k(n) = n - 1
sg4 = [i - 1 for i in range(N + 1)]

# ------------------------------------------------------------
# Count losing partitions using xor DP
# ------------------------------------------------------------

def losing_count(sg):

    MAXX = 512

    dp = [[0] * MAXX for _ in range(N + 1)]
    dp[0][0] = 1

    for a in range(1, N + 1):

        ndp = [[0] * MAXX for _ in range(N + 1)]

        for s in range(N + 1):
            for x, val in enumerate(dp[s]):

                if val == 0:
                    continue

                # choose multiplicity m of part size a
                for m in range((N - s) // a + 1):

                    nx = x
                    if m % 2 == 1:
                        nx ^= sg[a]

                    ndp[s + m * a][nx] += val

        dp = ndp

    return dp[N][0]

L2 = losing_count(sg2)
L3 = losing_count(sg3)
L4 = losing_count(sg4)

f2 = P200 - L2
f3 = P200 - L3
f4 = P200 - L4

answer = (f2 + f3 + 197 * f4) % MOD

print(answer)

4. Code walkthrough

Partition numbers

p[s] += p[s-a]

This is the classic partition DP computing $p(n)$.

SG computation

For each $n$:

generate every legal split,
xor the SG values of the child piles,
take the mex.

The recursion gen(...) enumerates nonincreasing partitions so each split is counted once.

Losing-position DP

For each pile size $a$:

choose multiplicity $m$,
add $m a$ to the total sum,
xor by sg[a] iff $m$ is odd.

At the end:

dp[200][0]

is the number of losing positions.

5. Verification on the examples

The program reproduces:

$$g(7)=66$$

and

$$g(10)=291.$$

So the implementation matches the statement.

Finally, for $n=200$,

$$g(200)\bmod(10^9+7)=626616617.$$

Answer: 626616617

Project Euler Problem 629