Project Euler 409

题目

Nim Extreme

Let \(n\) be a positive integer. Consider nim positions where:

• There are \(n\) non-empty piles.

• Each pile has size less than \(2^n\).

• No two piles have the same size.

Let \(W(n)\) be the number of winning nim positions satisfying the above conditions (a position is winning if the first player has a winning strategy). For example, \(W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360\) and \(W(100) \bmod 1 000 000 007 = 384777056\).

Find \(W(10 000 000) \bmod 1 000 000 007\).

解决方案

关于这个NIM博弈的页面，给出了一个更一般的方法用来判断当前游戏状态是必胜态还是必败态：

假设一共有\(n\)堆石头，每一堆的个数为\(a_i\)。那么游戏是必败态时，当且仅当

\[\bigoplus_{i=1}^n a_i=a_1\oplus a_2\oplus a_3 \oplus\dots\oplus a_n=0\]

其中\(\oplus\)是异或运算。

那么根据这个前置知识，考虑如下问题：

有多少个长度为\(m\)的序列\(\{x\}\)，满足：

1. \(x_i\)的数值两两不同。

2. \(\forall i\in[1,n],0< x_i<2^n\)

3. \(x_1\oplus x_2\oplus x_3 \oplus\dots\oplus x_m=0\)

用\(f_n(m)\)来表示这个序列对个数。

如果我们直接任意取前\(m-1\)个数，再令\(x_{m}=\bigoplus_{i=1}^{m-1} x_i\)，那么答案很明显为\(\displaystyle{A_{2^n-1}^{m-1}=\dfrac{(2^n-1)!}{(2^n-m)!}}\)，令\(g_n(m)=A_{2^n-1}^{m-1}\)。

那么我们考虑从\(g_n(k)\)排除掉一些情况从而得到\(f_n(k)\)。本题求解\(f_n(k)\)的使用了动态规划的思想：

• 如果前\(k-1\)个数满足\(\bigoplus_{i=1}^{k-1} x_i=0\)，那么说明\(x_{k}=0\)，不符合第\(2\)个条件。这种情况一共有\(f_n(k-1)\)种。
• 如果前\(k-1\)个数满足\(\bigoplus_{i=1}^{k-1} x_i=x_j\)，其中\(j\in [1,k-1]\)，那么说明\(x_{k}=x_j\)，不符合第\(1\)个条件。这也意味着：\(x_1\oplus x_2\oplus \dots \oplus x_{j-1}\oplus x_{j+1}\oplus \dots \oplus x_{k-1}=0\)。这一类情况一共有\(f_n(k-2)\cdot (k-1) \cdot (2^n-1-(k-2))\)情况，其中这个式子的第二项是指\(j\)有\(k-1\)种取法，第三项是指\(x_j\)可以取遍除了\(x\)序列中的\(k-2\)个数，剩下的\(2^n-1-(k-2)\)个数。

根据上面的内容，不难写出\(f_n(k)\)的递推式为：

\[f_n(k)= \left \{\begin{aligned} &1 & & \text{if}\quad k=0 \\ &g_n(k)-f_n(k-1) & & \text{else if}\quad k=1 \\ &g_n(k)-f_n(k-1)-f_n(k-2)\cdot (k-1)\cdot (2^n-k+1)& & \text{else} \end{aligned}\right.\]

那么整道题的最终答案为

\[g_n(n)-f_n(n)\]

代码

# include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=10000000;
ll mod=1000000007;
ll f[N+4];
int main(){
    f[0]=1;
    ll g=1,pw2=qpow(2,N,mod);
    for(int i=1;i<=N;i++){
        f[i]=(g-f[i-1]+mod)%mod;
        if(i>=2) f[i]=(f[i]-f[i-2]*(i-1)%mod*(pw2-i+1+mod)%mod+mod)%mod;
        g=g*(pw2-i+mod)%mod;
    }
    ll ans=(g-f[N]+mod)%mod;
    printf("%lld\n",ans);
}