Project Euler 310

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

Project Euler 310

题目

Nim Square

Alice and Bob play the game Nim Square.

Nim Square is just like ordinary three-heap normal play Nim, but the players may only remove a square number of stones from a heap.

The number of stones in the three heaps is represented by the ordered triple $(a,b,c)$.

If $0\le a\le b\le c\le29$ then the number of losing positions for the next player is $1160$.

Find the number of losing positions for the next player if $0\le a\le b\le c\le100 000$.

Sprague–Grundy定理

$sg$函数是一个用来解决公平组合游戏(ICG)问题的一种工具。

定义一个非负整数集合上的运算$\text{mex}(s)$：表示集合$s$中未出现的最小的非负整数。

我们定义一个游戏状态$n$，令$sg(n)=\text{mex}({sg(m)|n\rightarrow m})$.$m$是从$n$能够抵达的所有游戏状态。如果$sg(n)>0$，那么状态$n$为必胜态；如果$sg(n)=0$，那么为必败态。

Sprague–Grundy，SG定理说明了，如果这个游戏当前的状态$n$，它可以看做是多个状态$(n_1,n_2,\dots,n_k)$的组合，那么就可以写成：

以NIM游戏为例，如果当前有$n$堆石头，其中第$i$堆为$a_i$。那么状态$sg(a_1,a_2,\dots,a_n)$可以看成是$sg(a_1),sg(a_2),\dots,sg(a_n)$的组合，当前的状态是必胜态还是必败态由$sg(a_1)\oplus sg(a_2)\oplus\dots\oplus sg(a_n)$决定。

因此一般使用SG定理解决问题，主要依靠的是分治的思想。

解决方案

在每一次操作中，一方可以拿起三堆石头$(a,b,c)$的其中一堆的石头的平方数个。并且这$3$堆石头是相互独立的。因此，三堆石头的$sg$函数$sg(a,b,c)=sg(a)\oplus sg(b)\oplus sg(c)$.那么此时只需要单独考虑一堆石头的情况$sg(n)$。

只拿一堆石头时，那么剩下的石头只可能为$n-1^2,n-2^2,n-3^2,\dots$。那么不难写出$sg(n)$为：

由此可以快速地求出每个独立状态的$sg$值。

令$N=10^5$，那么问题就转化成有多少个三元组$(a,b,c),0\le a\le b\le c\le N$，满足$sg(a)\oplus sg(b)\oplus sg(c)=0$。

可以想到先统计在$0\sim N$中有多少个值$n$，其中有$c(i)$个$n$满足$sg(n)=i$。令$O=\max_{i=0}^N {sg(i)}$。并且其实$O$值很小。那么可以考虑通过枚举$i,j$使得$0\le i\le j\le i\oplus j \le O$，进行组合计数即可。计数的过程中要注意当$i=j$时，$c[i]$和$c[j]$使用的是同一个部分下的所有数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000;
const int M=log(N+10)*10+10;
int sg[N+4];
bool mex[M+4];
int cnt[M+4];
int main(){
    for(int i=1;i<=N;i++){
        memset(mex,0,sizeof(mex));
        for(int j=1;j*j<=i;j++)
            mex[sg[i-j*j]]=1;
        int j=0;
        for(;mex[j];++j);
        sg[i]=j;
        ++cnt[sg[i]];
    }
    ++cnt[0];
    int mx=*max_element(sg+1,sg+N+1);
    ll ans=0;
    for(int i=0;i<=mx;i++)
        for(int j=i+1;j<=mx;j++){
            int k=i^j;
            if(mx>=k&&k>j)
                ans+=1ll*cnt[i]*cnt[j]*cnt[k];
        }
    for(int i=1;i<=mx;i++)
        ans+=1ll*cnt[i]*(cnt[i]+1)/2*cnt[0];
    ans+=1ll*cnt[0]*(cnt[0]+1)*(cnt[0]+2)/6;
    printf("%lld\n",ans);
}