P2252

2021CHD · 2024-02-26 21:10:31 · 题解

提供一种不产生精度误差的做法。

本题解中所有数字以及未知数均为整数。

本题解中假定输入的 a\le b，如果输入的 a>b 则将输入的 a 和 b 交换。

我们对先手必败态进行打表，表如下：

0 0
1 2
3 5
4 7
6 10
8 13
9 15
11 18
12 20
14 23
......

考虑相邻两个必败态之间较小的数的差距，打表得：

12122121221221212212122122121221221212212122122121221212212212122122121221212212212122122121221212212212122......

不难发现，相邻两项之间较小的数的差距只能是 1 或 2。

证明如下：

基本规则1：(0,0)是必败态。

基本规则2：若 (a,b) 是必败态，则 (a+x,b)、(a,b+x)、(a+x,b+x) 均为必胜态。（x 为正整数）

基本规则3：若一个状态 (a,b) ，任何 (a-x,b) 满足 x\le a、(a,b-x) 满足 x\le b、(a-x,b-x) 满足 x\le \min(a,b)均已定义且均为必胜态，则该状态为必败态。（x 为正整数）

不难发现若 (a,b) 为必败态，则 (b,a) 为必败态。（通过基本规则的对称性）

引理1：对于每个 a，至多存在一个 b 使得 (a,b) 是必败态

证明：若存在 b<c 满足 (a,b) 和 (a,c) 均为必败态，则根据基本规则2得出 (a,c) 为必胜态，矛盾。

引理2：对于每个 a，存在一个 b 使得 (a,b) 是必败态

证明：若不存在 b 满足 (a,b) 为必败态，则根据基本规则3得出对于任意的b ，(a,b) 可以表示为 (c+x,d) 或 (c+x,d+x) 的形式，其中 (c,d) 为必败态且 c<a。

根据引理1，至多有 a 个满足条件的 (c,d)，那么至多只有 2a 个满足条件的 (a,b)，和假设中“对于任意的b ，a,b 均满足条件”矛盾。

引理3：对于任意必败态 (a,b) 满足 a\le b，对于任意 0\le x<b-a，存在唯一必败态 (m,n) 满足 m<a,n-m=x，且对于任意必败态 (m,n) 满足 m<a,m\le n，(m,n) 满足 n-m\le b-a，且对于任意必败态 (a,b),(m,n) 满足 a\le b,m\le n,a\le m，满足 b\le n。

证明：引理3对于 (0,0) 显然成立。

若引理3对于任意 a\le k-1(k>0) 成立，若不存在必败态 (k,b) 满足 k\le b，则引理3对于 a=k 成立。

否则，根据引理2，存在唯一必败态 (k,b) 满足 k\le b。

必然存在必败态 (x,y) 满足 x\le y，使得不存在必败态 (q,p) 满足 x\le q\le k,q\le p。

则 b-k>y-x，那么 b>y，对于 (k,b=k+y-x+1) 满足基本规则3，其为必败态，则引理3对于 a=k 成立。

引理3的推论：对于 2 个必败态 (a,b),(c,d) 满足 a\le b,c\le d,a<c 且不存在必败态 (p,q) 满足 p\le q,a<p<c，满足 d-b=c-a+1。

总证明：

根据引理3的推论，不存在必败态 (a,b),(c,d) 满足 a\le b,c\le d,d=b+1，则不存在必败态 (a,b),(c,d) 满足 a\ge b,c\ge d,a=c+1。

则对于任意集合 S=\{x,x+1\}，满足至多存在一个 w\in S 使得存在必败态 (w,b) 满足 (w\ge b)。

对于 2 个必败态 (a,b),(c,d) 使得 a\le b,c\le d,a<c 且不存在必败态 (p,q) 满足 p\le q,a\le p\le c，满足对于任意 a<q<c，存在必败态 (q,p) 满足 q\ge p。

则对于 2 个必败态 (a,b),(c,d) 使得 a\le b,c\le d,a<c 且不存在必败态 (p,q) 满足 p\le q,a<p<c，满足 1\le c-a\le 2。

证明完毕。

经过这一番骚操作之后，我们证明了上文中的数列只存在 1 和 2 两种数字。

接下来就是找规律并证明的时间了。

不难发现，数列中第一项是 1，且数列中的 1 从不连续出现。

不难发现，数列中的 2 的连续段长度构成序列 12122121221221212212122122...，也就是说构成它本身！

接下来我们证明这两点。

证明数列中的 1 从不连续出现。

根据数列中只存在 1 和 2 以及引理3的推论，得出对于 2 个必败态 (a,b),(c,d) 满足 a\ge b,c\ge d,a<c 且不存在必败态 (p,q) 使得 p\ge q,a<p<c，满足 2\le c-a\le 3。

经检验，第一个 1 处不存在连续的 2 个 1。

如果数列中有连续的 2 个 1，那么说明存在必败态 (a,b)、(a+1,c)、(a+2,d) 满足 a<b，a+1<c,a+2<d，就是说不存在必败态 (a,p)、(a+1,q)、(a+2,r) 满足 a>p，a+1>q,a+2>r。

那么就必然存在 2 个必败态 (m,n),(x,y) 满足 m\ge n,x\ge y,m<x 且不存在必败态 (u,v) 使得 u\ge v,m<u<x，满足 x-m\ge 4，与上文矛盾。

证明数列是以如上所述方式自定义的。

以下文字将会采用不那么严谨的表述方式。

考虑原数列中的每个 1，发现其对应了相邻两个满足前一个数大于等于后一个数的必败态中间间隔 2，而原数列中的每个 2，发现其对应了相邻两个前一个数大于等于后一个数的必败态中间间隔 3。

也就是说每一个 1 可以在原数列上导出一个 2，而每一个 2 可以原数列上导出一个 12。

再进行一次类似的操作，每一个 2 可以原数列上导出一个 12，每一个 12 可以原数列上导出一个 212。

也就是说，每一个 1 可以在原数列上导出两次得到 12，而每一个 2 可以原数列上导出两次得到 212。

考察导出前后的数列：

导出前：12122121221221212212122122...。

导出后：122121221221212212122122...。

不难发现导出后比导出前少了开头的 12。

那么第一个 1 对应了缺少的 12，其余的每个 1 和它前面的 2 必定会导出 21212，这个 1 就对应了中间的 12，而每个 2 和前面的数字要么导出了 12212（前面是 1），要么导出了 212212（前面是 2），也就是说，每一个 2 又恰好可以对应一个 122。

那么有了这些结论，我们已经可以 O(n) 导出上文中的数列了，但是这还不够，因为这个数列表示了相邻两个数的差值，如何快速判断一个 a 是否存在必败态 (a,b) 满足 a\le b 呢？

不难发现，如果数列以 0 开始编号，必败态 (a,b) 满足 a\le b 存在当且仅当 a=0 或数列的第 a 项为 2。

证明上述结论。

每一个 1 可以在原数列上导出一个 2，而每一个 2 可以原数列上导出一个 12，也就是说相邻两个 2 的间隔对应了原数列去除第一个数的结果，刚好符合我们最初对该数列的定义。

所以如果 (a,b) 满足 0<a\le b 是必败态，当且仅当数列的第 a 项是第 m 个 2，并且数列的第 b 项是第 m+1 个 1。

特判 a=0 的情况。

现在问题简化成了计算数列的第 x 个数和计算数列的第 x 个数前有几个 1。

如果不能快速求得这个答案的话我们就前功尽弃了。

很幸运，这个数列是自定义的，也就是说，它的各个部分会有一定程度的相似性。

如下图所示。

因为这个数列是自定义的，可以用如上方式思考。

“组成部分的长度”实际上是斐波那契数列，可以方便地用数学归纳法证明。

比如我们要求数列的第 20 项，查阅第三行发现，它等于紫色区间的第三个位置，于是转化为求解数列的第 7 项，然后问题规模就减小了。

最后一定会转化为求数列第 0 项或第 1 项。

求排名呢？

可以预处理每层的两个段中各有几个 1，几个 2，那就可以像上面一样递归处理了。

时间复杂度：O(\log(\max(a,b)))。

参考代码：

#include<cstdio>
using namespace std;
long long x,y,t,f[100]={0,1,1},s[100]={0,0,1},g[100]={0,1},i,num1,num2;
main()
{
    scanf("%lld%lld",&x,&y);
    if(x>y)
    {
        t=x;
        x=y;
        y=t;
    }
    for(i=3;i<=50;i++)
    {
        f[i]=f[i-1]+f[i-2];
        s[i]=s[i-1]+s[i-2];
        g[i]=g[i-1]+g[i-2];
    }
    if(y==0)
    printf("0");
    else if(x==0)
    printf("1");
    else
    {
        for(i=1;i<=50;i=i+2)
        if(f[i]+f[i+1]>x)
        break;
        for(;i>=3;i=i-2)
        {
            if(x>=f[i]&&x<f[i]*2)
            {
                num1=num1+s[i];
                x=x-f[i];
            }
            else if(x>=f[i]*2)
            {
                num1=num1+s[i]+s[i-1];
                x=x-f[i]-f[i-1];
            }
        }
        if(x==0)
        {
            printf("1");
            return 0;
        }
        for(i=1;i<=50;i=i+2)
        if(f[i]+f[i+1]>y)
        break;
        for(;i>=3;i=i-2)
        {
            if(y>=f[i]&&y<f[i]*2)
            {
                num2=num2+g[i];
                y=y-f[i];
            }
            else if(y>=f[i]*2)
            {
                num2=num2+g[i]+g[i-1];
                y=y-f[i]-f[i-1];
            }
        }
        if(y==1||num1!=num2-1)
        printf("1");
        else
        printf("0");
    }
}