LightOJ-1296 题解 SG函数找规律

题目链接一道找规律的好题。

首先SG函数打表，完全模板：

int mem[1024];
int sg(int n) {
    if (n == 1) return 0;
    if (mem[n]>-1) return mem[n];

    short vis[1024] = {0};
    rep(i,1,n/2) vis[sg(n-i)] = 1;
    for(int i=0; ; ++i) if (!vis[i]) return mem[n]=i;
}

观察结果，发现n为偶数时SG函数值是n/2，但n是奇数是规律不明显。

n=1, sg=0
n=2, sg=1
n=3, sg=0
n=4, sg=2
n=5, sg=1
n=6, sg=3
n=7, sg=0
n=8, sg=4
n=9, sg=2
n=10, sg=5
n=11, sg=1
n=12, sg=6
n=13, sg=3
n=14, sg=7
n=15, sg=0
n=16, sg=8
n=17, sg=4
n=18, sg=9
n=19, sg=2
n=20, sg=10
n=21, sg=5
n=22, sg=11
n=23, sg=1
n=24, sg=12
n=25, sg=6
n=26, sg=13
n=27, sg=3
n=28, sg=14
n=29, sg=7
n=30, sg=15
n=31, sg=0
n=32, sg=16
n=33, sg=8
n=34, sg=17
n=35, sg=4
n=36, sg=18
n=37, sg=9
n=38, sg=19
n=39, sg=2
n=40, sg=20
n=41, sg=10
n=42, sg=21
n=43, sg=5
n=44, sg=22
n=45, sg=11
n=46, sg=23
n=47, sg=1
n=48, sg=24
n=49, sg=12
n=50, sg=25

但可以观察到sg(n)=0时，n+1为2的次幂。进而猜想sg(n)和n+1的二进制表示有关，继续打表如下：

n=1     sg=0    0000000010
n=3     sg=0    0000000100
n=7     sg=0    0000001000
n=15    sg=0    0000010000
n=31    sg=0    0000100000
n=2     sg=1    0000000011
n=5     sg=1    0000000110
n=11    sg=1    0000001100
n=23    sg=1    0000011000
n=47    sg=1    0000110000
n=4     sg=2    0000000101
n=9     sg=2    0000001010
n=19    sg=2    0000010100
n=39    sg=2    0000101000
n=6     sg=3    0000000111
n=13    sg=3    0000001110
n=27    sg=3    0000011100
n=8     sg=4    0000001001
n=17    sg=4    0000010010
n=35    sg=4    0000100100
n=10    sg=5    0000001011
n=21    sg=5    0000010110
n=43    sg=5    0000101100
n=12    sg=6    0000001101
n=25    sg=6    0000011010
n=14    sg=7    0000001111
n=29    sg=7    0000011110
n=16    sg=8    0000010001
n=33    sg=8    0000100010
n=18    sg=9    0000010011
n=37    sg=9    0000100110
n=20    sg=10   0000010101
n=41    sg=10   0000101010
n=22    sg=11   0000010111
n=45    sg=11   0000101110
n=24    sg=12   0000011001
n=49    sg=12   0000110010
n=26    sg=13   0000011011
n=28    sg=14   0000011101
n=30    sg=15   0000011111
n=32    sg=16   0000100001
n=34    sg=17   0000100011
n=36    sg=18   0000100101
n=38    sg=19   0000100111
n=40    sg=20   0000101001
n=42    sg=21   0000101011
n=44    sg=22   0000101101
n=46    sg=23   0000101111
n=48    sg=24   0000110001
n=50    sg=25   0000110011

上表先按sg(n)排序，再按n排序，并列出n+1的二进制表示。不难发现，n+1末尾的0均可以去掉，不影响sg(n)的结果。注意到，如果n+1末尾有0，则n是奇数；去掉末尾所有0之后n+1必然为奇数而n为偶数，则答案就得到了。代码就可以略去了。