HDU6869：Slime and Stones

【难度】

5 / 10 5/10 5/10
杭电就喜欢出拓展题……

【题意】

有两堆石子，第一堆有 a a a 个石头，第二堆有 b b b 个石头。
你有两种操作：
操作一：从某堆拿任意个石子。
操作二：从第一堆拿 x x x 个，从第二堆拿 y y y 个，要求 ∣ x − y ∣ ≤ k |x-y|\le k ∣x−y∣≤k,其中 k k k是给定常数。

每个人都是最优策略，让你求是否先手必胜（1）或先手必败（2）。

【数据范围】

样 例 组 数 1 ≤ T ≤ 1 0 5 样例组数 1\le T\le 10^5 样例组数1≤T≤105
1 ≤ a , b , k ≤ 1 0 8 1\le a,b,k\le 10^8 1≤a,b,k≤108

【样例输入】

4
1 2 0
2 4 0
1 2 1
2 6 1

【样例输出】

0
1
1
0

【思路】

（一）首先是一眼就能看出的规律

若 ∣ a − b ∣ ≤ k |a-b|\le k ∣a−b∣≤k，则直接先手必胜。
若 ( i , j ) (i,j) (i,j)为必输状态，且 ( a , b ) (a,b) (a,b)能转移到 ( i , j ) (i,j) (i,j) ，则 ( a , b ) (a,b) (a,b) 必胜，否则必输。

更正式的表达为：

S G [ a , b ] = m e x ( a , b ) 能 转 移 到 ( i , j ) { S G [ i , j ] } \color{red}SG[a,b]=\underset{(a,b)能转移到(i,j)}{mex}\Big\{ SG[i,j]\Big \} SG[a,b]=(a,b)能转移到(i,j)mex​{SG[i,j]}

我们打一下表查看一下规律。

【打表代码】

int dp[MAX][MAX][MAX];
int main()
{
    for(int k=0;k<=5;++k){
        show(k);
        for(int i=1;i<=60;++i){
            for(int j=1;j<=60;++j){
                if(abs((i-j))<=k)cout << "+" << " ",dp[i][j][k] = 1;
                else{
                    bool fd = false;
                    for(int p=1;!fd && p<=i;++p)
                    for(int q=1;!fd && q<=j;++q){
                        if(p==i && q==j)continue;
                        if(abs((i-p)-(j-q))<=k && dp[p][q][k]==0)fd=true;
                    }
                    for(int p=1;!fd && p<i;++p)if(dp[p][j][k]==0)fd=true;
                    for(int p=1;!fd && p<j;++p)if(dp[i][p][k]==0)fd=true;
                    if(fd)dp[i][j][k] = 1;
                    else dp[i][j][k] = 0;
                    if(fd)cout << "." << " ";
                    else cout << "X" << " ";
                }
            }
            puts("");
        }
        puts("");
    }
    return 0;
}

以下为k=0与k=1时的表格，其中 m a t [ i ] [ j ] = ‘ X ’ mat[i][j]=‘X’ mat[i][j]=‘X’表示该点为必输态，否则为必胜态。
其中对角线状态额外用 ‘ + ’ ‘+’ ‘+’号做了对照标记。


发现，对于不同的 k k k,必输态都很少，大致呈直线分布。但是之间的间隔很奇怪。

我们枚举上三角矩阵不同的 X X X之间的间隔(纵坐标间隔)并丢到OEIS中去，可以发现规律

k = 0 , d i s [ ] = { 2 , 5 , 7 , 10 , 13 , 15 , 18 ⋯   } k = 1 , d i s [ ] = { 3 , 6 , 10 , 13 , 17 , 20 , 23 ⋯   } k = 2 , d i s [ ] = { 4 , 8 , 12 , 17 , 21 , 25 , 30 , 34 ⋯   } k = 3 , d i s [ ] = { 5 , 10 , 15 , 20 , 26 , 31 , 36 , 41 , 47 ⋯   } k=0,dis[]=\{2,5,7,10,13,15,18\cdots\}\\ k=1,dis[]=\{3,6,10,13,17,20,23\cdots\}\\ k=2,dis[]=\{4,8,12,17,21,25,30,34\cdots\}\\ k=3,dis[]=\{5,10,15,20,26,31,36,41,47\cdots\}\\ k=0,dis[]={2,5,7,10,13,15,18⋯}k=1,dis[]={3,6,10,13,17,20,23⋯}k=2,dis[]={4,8,12,17,21,25,30,34⋯}k=3,dis[]={5,10,15,20,26,31,36,41,47⋯}

然后OEIS里面的查找结果为：
【注意：需要通分成分母为2，注意根号内数值需要递增】
k = 0 , B [ n ] = f l o o r ( n × 3 + 5 2 ) k = 1 , B [ n ] = f l o o r ( n × 4 + 8 2 ) k = 2 , B [ n ] = f l o o r ( n × 5 + 13 2 ) k = 3 , B [ n ] = f l o o r ( n × 6 + 20 2 ) ⋮ \color{green}k=0,B[n]=floor(n\times \frac{3+\sqrt5}{2})\\ k=1,B[n]=floor(n\times \frac{4+\sqrt8}{2})\\ k=2,B[n]=floor(n\times \frac{5+\sqrt{13}}{2})\\ k=3,B[n]=floor(n\times \frac{6+\sqrt{20}}{2})\\ \vdots k=0,B[n]=floor(n×23+5 ​​)k=1,B[n]=floor(n×24+8 ​​)k=2,B[n]=floor(n×25+13 ​​)k=3,B[n]=floor(n×26+20 ​​)⋮
可以看到，左侧的数字 3 , 4 , 5 , 6 ⋯ 3,4,5,6\cdots 3,4,5,6⋯依次递增。右侧数字的规律？再套到OEIS中！
（若找不到可以多找几个k）

我们是从第二项开始的，那么稍微替换一下 n n n：
b ( n ) = ( n + 1 ) 2 + 1 = n 2 + 2 n + 5 b(n) =\sqrt{(n+1)^2+1}=\sqrt{n^2+2n+5} b(n)=(n+1)2+1 ​=n2+2n+5 ​

那么第 n n n 个必败态的纵坐标我们就知道了，为：
B [ n ] = ⌊ n k + 3 + k 2 + 2 k + 5 2 ⌋ B[n]=\Big\lfloor n\frac{k+3+\sqrt{k^2+2k+5}}{2}\Big\rfloor B[n]=⌊n2k+3+k2+2k+5 ​​⌋

然后再结合威佐夫博弈的一些性质（找来的）：

【贝亚蒂定理：Beatty’s theorem】
贝亚蒂定理：百度百科
奇 异 局 势 满 足 （ p , p p − 1 ） 的 模 式 ， 即 可 反 推 横 坐 标   （ 奇 异 局 势 指 的 是 必 败 态 的 点 对 ） \color{red}奇异局势满足（p,\frac{p}{p-1}）的模式，即可反推横坐标\\ \ \\ \color{green}（奇异局势指的是必败态的点对） 奇异局势满足（p,p−1p​）的模式，即可反推横坐标 （奇异局势指的是必败态的点对）
【威佐夫博弈：Wythoff’s game】
威佐夫博弈：百度百科

(百度百科这里是 k = 0 k=0 k=0的特殊情况、、)
当 k = 0 时 ， 奇 异 局 势 满 足 ( p , p + n ) 我 们 马 后 炮 一 下 得 知 ： 奇 异 局 势 满 足 ( p , p + n + n k ) \color{red}当k=0时，奇异局势满足(p,p+n)\\ 我们马后炮一下得知：奇异局势满足(p,p+n+nk) 当k=0时，奇异局势满足(p,p+n)我们马后炮一下得知：奇异局势满足(p,p+n+nk)
然后得出奇异局势标为：
A [ n ] = ⌊ n − k + 1 + k 2 + 2 k + 5 2 ⌋   B [ n ] = ⌊ n k + 3 + k 2 + 2 k + 5 2 ⌋ \color{red}A[n]=\Big\lfloor n\frac{-k+1+\sqrt{k^2+2k+5}}{2}\Big\rfloor\\ \ \\ B[n]=\Big\lfloor n\frac{k+3+\sqrt{k^2+2k+5}}{2}\Big\rfloor A[n]=⌊n2−k+1+k2+2k+5 ​​⌋ B[n]=⌊n2k+3+k2+2k+5 ​​⌋

然后我们二分查找对应的 n n n，再查看是否满足这两个点对公式即可。

【注：】
当 k = 0 k=0 k=0时，即为普通的威佐夫博弈，在HDU有原题。

【核心代码】

时间复杂度： O ( T × log ⁡ 2 L i m i t ) O(T\times \log_2 Limit) O(T×log2​Limit)
其中上界 L i m i t Limit Limit为 1 0 8 10^8 108
Time(Ms)：62

int main()
{
    int T;
    T = read();
    while(T--){
        int a,b,t;
        a = read();
        b = read();
        t = read();
        double k = (double)t;
        if(a > b)swap(a,b);
        double XA = (1.0-k+sqrt(5.0+2*k+k*k))/2;
        double XB = (3.0+k+sqrt(5.0+2*k+k*k))/2;
        int l = 0;
        int r = 100000000;
        while(l < r){
            int mid = l + r >> 1;
            if(floor((double)mid * XA) > a)r = mid - 1;
            else if(floor((double)mid * XA) < a)l = mid + 1;
            else {
                l = mid;
                break;
            }
        }
        if(floor((double)l * XA) == a && floor((double)l * XB) == b)printf("0\n");
        else printf("1\n");
    }
    return 0;
}