交叉翻转

桌上放着N行N列共$N^2$个碟子，排成正方形，每个碟子都是一面黑色一面白色。

每轮你都可以选择一个碟子，并将所在的行和列中所有的碟子都翻转，即一共翻转$2N-1$个碟子。

所有碟子都是白色面朝上时游戏结束。以下是$N=5$时的一个例子：

可以验证，至少需要3轮才能结束游戏。

记左下角碟子的坐标为$(0,0)$，右下角碟子的坐标为$(N-1,0)$，左上角碟子的坐标为$(0,N-1)$。

设初始状态为满足$N-1\le \sqrt{x^2+y^2} < N$的碟子$(x,y)$黑色面朝上，其它碟子白色面朝上，上例即$N=5$时的初始状态。

记$T(N)$是此种初始状态下结束游戏需要的最少轮数，例如$T(5)=3$。此外还有$T(10)=29$以及$T(1000)=395253$。

无法结束游戏时定义$T(N)$为0。

求$\sum_{i=3}^{31}T(2^i-i)$。

本题难度:

解答

本题是官网第一道难度标记为100%的问题，似乎没有太好的手段，以下仅作简单说明：

首先需要注意到只有i为偶数时才能结束游戏，这可以用二元域上的矩阵和仿射变换来分别描述局面和操作加以证明。

偶数的情况就是求一系列仿射变换使之将给定的局面映射为0，不过这对于具体的局面如何求解似没有太大指导作用。

以下解法改编自官网论坛，它是经验式的，即通过考察较小的i归纳（不完全归纳）出一系列固定的步骤，再复用到较大的i上。

最终结果是$467178235146843549$。

注：以下代码为Python 3，代码中打印了进度信息。另外，由于$i=28$和30时的数字非常大，使用标准库的math.ceil(math.isqrt(n))会出现误差，因此在代码中手动实现了这一调用。

import math

r=3
for i in range(4,32,2):
    n=(1 << i)-i
    res=nfrows=nufrows=nfcols=xhigh_prev=0
    prev_flipped =False
    y=n-1
    while True:
        xlow=math.isqrt((n-1)*(n-1)-y*y)
        if xlow*xlow < (n-1)*(n-1)-y*y:
            xlow+=1
        if y < xlow:
            res*=2
            break
        xhigh=math.isqrt(n*n-y*y)
        if xhigh*xhigh < n*n-y*y:
            xhigh+=1
        xwidth=xhigh-xlow
        flip_col=(xlow==xhigh_prev-1)
        xhigh_prev=xhigh
        last_row=(y < xhigh)
        if xwidth & 1:
            res+=xwidth-int(last_row)
            if flip_col:
                res+=nufrows-nfrows-2*nfcols+y-2+(2 if prev_flipped else -2)
                nfcols+=1
            prev_flipped=False
            nufrows+=1
        else:
            if not last_row:
                res+=n-xwidth-1-2*nfcols-2*nfrows 
                if flip_col:
                    res+=nufrows-nfrows-2*nfcols+y+(2 if prev_flipped else -2)
                    nfcols+=1
            elif y==xlow:
                res+=n-xwidth-2*nfcols-2*nfrows+int(prev_flipped)
                if prev_flipped and y==xlow:
                    res+=2
            else:
                res+=n-xwidth-2*nfcols-2*nfrows
                if prev_flipped and y==xlow:
                    res+=2
                if flip_col:
                    res+=nufrows-nfrows+2*int(prev_flipped)-2*nfcols+y
                    nfcols+=1
            nfrows+=1
            prev_flipped=True
        if last_row:
            res=2*res+1
            break
        y-=1
    r+=res
    print(i,"completed")

print(r)