题解 P5820 【【L&K R-03】射击场决战】

KesdiaelKen · 2019-12-19 15:48:15 · 题解

本题为博弈论+数论题目，只需转化一下模型即可。

生成函数只是个随机函数，按题意生成数据。其实是因为直接给数据文件太大无法上传

下面分数据编号进行讲评。

1

用k减去每个初始示数，题意就可以理解为在任意一个位置上减1，不够减则借位。每个数从0到k。这不就是k+1进制的减法吗？于是，题意转化为：给出n个数，每次减去(k+1)^i，i为任意自然数，不能减到小于0，轮流操作，问谁会面对全0的局面。则考虑每个数的胜负情况（记为f[i]）。

对于此点n=1，只需考虑一个数的f[i]。由于2点m,k范围较大，不能像1那样枚举下接状态。考虑f[i]是否具有规律。发现对于k的奇偶不同，规律不同：下面分情况证明：

对于k为偶数，当2|i时f[i]=false（败），否则为true（胜）。证明：数学归纳法。当i=0,1时成立。当i>1，由于2|k，2\not|(k+1)^i，i-(k+1)^i与i不同奇偶，则若i为偶，所有i-(k+1)^i为奇，f[i-(k+1)^i]=true，则f[i]=false。i为奇同理。

对于k为奇数，当i>k+1，f[i]\equiv f[i\mod (k+2)]；当i\le k+1，f[i]=true时(2\not|i )or(i=k+1)，f[i]=false时(2|i)and(i\not=k+1)。证明：数学归纳法。当i=0\space to\space k+1时易知成立。当i>k+1时，(k+1)^i=1\space or\space -1(\mod k+2)，则类似k为偶数时进行归纳。

存不下转换后的数。但考虑到最后的数要对k+2取模，可以在读入的时候同时取模。因为是k+1进制，对于奇数位，模k+2的值为-1乘此位上的数；对于偶数位，模k+2的值为1乘上此位上的数。

6-8

有多个数，k为偶数。先求出每个初始数的f。由以上证明可看到k为偶数时，赢状态的所有下接状态都为输状态，而输状态的所有下接状态都为赢状态。末状态所有数都为0，有偶数个赢状态。对于所有数，一次射击只能将一个数的f变为相反的一个状态。因此对于一个人，他面对的所有数中赢状态总数一定。所以，若先手面对奇数个赢状态则必赢，偶数个则必输。

5

每个数都小于等于k，即不可能取到k为奇数的特殊状态i\equiv k+1(\mod k+2)，等同于k为偶数的状态，即赢状态只接输状态，输状态只接赢状态。做法同上。

4

只有两个数，可以进行特殊讨论解决。

9-17