自动搬运

查看原文

来自洛谷，原作者为

	lcfollower 不 AK Div.2 & 3 不改签 | AT 不上蓝不改签（目前只有绿）。 | 不拿蓝钩不改签。 | 大号在 N 个月前已清关，误清的用这个号回关

搬运于2025-08-24 23:17:10，当前版本为作者最后更新于2025-06-07 21:49:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

膜拜题解区巨佬 $\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 ;
}