题解：P12658 [KOI 2023 Round 1] 格子游戏

· · 题解

膜拜题解区巨佬 \mathcal O(nmk) 做法，蒟蒻只会 \mathcal O(nmk\log k)，但是吸氧还是妥妥的过好吧（算出来最大大概为 2\times 10^8 多）。

因为只能往右边、下边和右下走，所以我们可以从 (i,j) 到可以到达的点连一条有向边，建出来的图为 DAG，这个 DP 的无后效性是一个道理。

然后学过生成函数 SG 的人，一看这就是板子。

关于 SG 函数的内容，可见这里。

对于这题，里面最关键的话：

对于状态 x 和它的所有 k 个后继状态 y_1，y_2，\ldots，y_k，定义 \operatorname{SG} 函数：

\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\}

而对于由 n 个有向图游戏组成的组合游戏，设它们的起点分别为 s_1，s_2，\ldots，s_n，则有定理：当且仅当 \operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n) \neq 0 时，这个游戏是先手必胜的。同时，这是这一个组合游戏的游戏状态 x 的 SG 值。

证明下面有。

那么我们只要对于每个 (i ,j)，找到其合法的后继，然后求出它们 SG 值的 mex 就可以了。

求 mex 可以升序排序然后求：

sort (b + 1 ,b + 1 + cnt);//排序。
int tot = unique (b + 1 ,b + 1 + cnt) - b - 1;//去重。
//这是为了去除比如后继的 SG 值为 0 1 1 1 1 2 等的情况。
int mex = tot;
up (i ,1 ,tot) if (b[i] != i - 1) {mex = i - 1 ; break;}//不符合 0，1，2，……自然数排列，这个数就是 mex。
//如果没有更改 mex 就为 tot，上面赋值过了。

但是考虑到可能的后继都在点的右下方，后继当然需要保证求过 SG 值，所以需要倒着做。

最终，如果 \operatorname{SG}(x,y) \neq 0，则先手胜；否则后手胜。

代码

# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y ; i ++)
# define dn(i ,x ,y) for (int i = x ; i >= y ; i --)
# define inf 1e14

using namespace std;

inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

const int N = 305;
int n ,m ,k ,Q ,b[N + 10] ,sg[N][N];
char a[N][N];

inline void init (){
  sg[n][m] = 0;
  dn (i ,n ,1) {
    dn (j ,m ,1) {
      if (i == n && j == m) continue;
      if (a[i][j] == '#') continue;
      int cnt = 0;
      /* 找可能的后继的 SG 值。*/
      if (i < n && a[i + 1][j] != '#') b[++ cnt] = sg[i + 1][j];
      if (j < m && a[i][j + 1] != '#') b[++ cnt] = sg[i][j + 1];
      up (d ,1 ,k){
        int ax = i + d ,ay = j + d;
        if (ax > n || ay > m) break;
        if (a[ax][ay] != '#') b[++ cnt] = sg[ax][ay];
      } /* 求 mex。*/
      sort (b + 1 ,b + 1 + cnt);
      int tot = unique (b + 1 ,b + 1 + cnt) - b - 1;
      int mex = tot;
      up (i ,1 ,tot) if (b[i] != i - 1) {mex = i - 1 ; break;}
      sg[i][j] = mex;
    }
  }
} signed main (){

  n = read () ,m = read () ,k = read ();
  up (i ,1 ,n) up (j ,1 ,m) cin >> a[i][j];

  init ();

  Q = read ();
  while (Q --) {
    int x = read () ,y = read ();
    if (sg[x][y]) puts ("First");
    else puts ("Second");
  }
  return 0 ;
}