2.1 KiB
2.1 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4da1000cf542c50ffed | 問題 366: 石取りゲーム (3) | 5 | 302027 | problem-366-stone-game-iii |
--description--
アントンとベルンハルトという名前の 2 人のプレイヤーが、次のようなゲームをしています。
n 個の石を積み上げた山が 1 つあります。
先手は、任意の正の整数分の石を取れますが、山全体を取ることはできません。
その後、各プレイヤーは、対戦相手が直前に取った数の 2 倍までの数の石を取ります。
最後の石を取ったプレイヤーが勝者です。
例: n = 5 とします。
先手が 2 個以上の石を取った場合、後手は残りのすべての石を取ることができます。
先手が石を 1 個取り 4 個残した場合、後手も石を 1 個取ると 3 個残ります。
先手は多くとも 2 \times 1 = 2 個の石しか取れないので、3 個すべてを取ることはできません。 したがって、また石を 1 個取ると仮定します。残りは 2 個になります。
後手は、残っている 2 個の石を取れば勝つことができます。
したがって、石が 5 個ある山は先手にとって敗北ポジション (必ず負ける状況) です。
いくつかの勝利ポジションでは、先手が取り得る手は複数あります。
例: n = 17 の場合、先手は 1 個または 4 個の石を取ることができます。
先手が最初のターンで勝利ポジションから取れる石の最大数を M(n) とし、他のすべてのポジションでは M(n) = 0 とします。
n ≤ 100 のとき、\sum M(n) = 728 です。
n ≤ {10}^{18} のとき、\sum M(n) を求めなさい。 mod {10}^8 で答えること。
--hints--
stoneGameThree() は 88351299 を返す必要があります。
assert.strictEqual(stoneGameThree(), 88351299);
--seed--
--seed-contents--
function stoneGameThree() {
return true;
}
stoneGameThree();
--solutions--
// solution required