4.21杂题

由于难度差异较大，这篇题解里面只会写部分比较有意思的题。

Nullify The Matrix

题意

给出一个$n\times m$的棋盘，第$i$行第$j$列的格子的权值为$a_{i,j}$，有两个人要玩游戏。每次当前玩家可以选择一个非零的格子，让这个格子减去一个正整数，但不能减到负数，同时选择一条从这个点到$(n,m)$的最短路径，将路径上的其它位置随意赋值。不能操作的那一方输。你需要判断先手必胜还是后手必胜。

$$n,m\leq 100,T\leq 10$$

题解

注意到最短路径上每走一步都会从一条副对角线跨到与其相邻的另一条副对角线，这启发我们按照对角线来考虑。

依次考虑这张棋盘的每条副对角线。

如果我们仅考虑某条副对角线，将矩阵的其余部分完全忽略，那么它就变成了一个nim游戏，即每次当前玩家可以任选一堆棋子拿走至少一个，不能操作的玩家输。

加强一下这个游戏，考虑最靠左上的那条非全$0$的对角线，我们不妨假设它的编号为$i$，显然前$i-1$条对角线对游戏不会产生任何影响，接下来我们加入一条限制：每次当前玩家只能在第一条非全$0$的对角线上操作。

当一名玩家拿走第$i$条对角线的所有棋子，他一定可以决定$i+1$到$\min(n,m)$这些对角线的异或，即可以保证单独在这些对角线上进行nim游戏时先手必胜。这名玩家操作完毕之后，两个玩家开始轮流操作第$i+1$条对角线，由于之前这名玩家已经保证了先手必胜，因此这一条对角线最后操作的玩家仍然是他，他可以继续保持最后操作的优势。

因此，我们可以得出一个结论：对于这个简化版的游戏，先手获胜的条件是第一条非$0$的对角线异或和不为$0$。

接下来进一步加强这个游戏，考虑原问题。仍然假设第一条非$0$的对角线为$i$。

如果$i$满足异或和不为$0$，也就是在这条对角线上先手必胜，那么先手一开始可以选择这条对角线，接下来我们讨论后手的决策。

• 如果后手操作第$i$条对角线，那么先手也操作这条对角线，最后必然可以使得这条对角线最后是由先手操作的。
• 如果后手操作其它的对角线，由于先手已经操作了一次第$i$条对角线，因此先手可以使得所有对角线上都是先手必胜。此时先手与后手在同一条对角线上继续操作，由于先手后操作，因此可以保证所有对角线仍然是先手必胜。

因此，如果第$i$条对角线先手胜，则先手必胜。

如果第$i$条对角线后手必胜，那么先手一定不会操作它，我们不妨假设存在一条对角线$j$使得一开始这条对角线上先手必胜，我们讨论先后手的策略。

• 先手一开始操作第$j$条对角线，使得$j+1$到$\min(n,m)$这些对角线都是先手必胜。
• 根据之前的讨论，后手一定不会选择$j$到$\min(n,m)$这些对角线操作，否则后手必败。
• 而$(i,j-1)$这些对角线上先手必败，而此时后手由于只能选择这些对角线，因此此时先后手翻转，先手采用之前的策略即可，因此先手必胜。

如果所有对角线都是先手必败，那么只要先手操作一条对角线后手就跟着操作，可以使得最终先手必败。

因此这题的结论是：若存在一条对角线先手胜，则先手必胜。

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int G[N][N], s[2 * N];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) scanf("%d", &G[i][j]), s[i + j] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) s[i + j] ^= G[i][j];
        bool flag = false;
        for (int i = 2; i <= n + m; i++) if (s[i]) flag = true;
        if (flag) puts("Ashish");
        else puts("Jeel");
    }
}

小Y的序列

题意

来源：auoj1622

有一个序列$a$，定义一个位置$i$是好的当且仅当$i$前面有至少$k$个位置小于$a_i$。给定$n,m$，对于每个$k$求出所有每个数不超过$m$的序列中好的位置的个数之和。

$$n\leq 2\times 10^5, m\leq 10^9$$

题解

考虑二项式反演。定义$g_i$表示所有数列中满足前面有恰好$i$个数小于它的位置的个数之和，那么答案就是$g_i$的后缀和。

$g_i$不是很好求，我们定义$f_i$表示在每个数前面钦定$i$个位置，这些位置都小于这个数的个数之和。

那么我们很容易写出$f_k$的表达式。

$$\begin{aligned} f_k&=\sum_{i=1}^n\sum_{t=1}^m(t-1)^k{i-1\choose k}m^{n-1-k}\\ &=m^{n-1-k}\sum_{t=1}^m(t-1)^k\sum_{i=1}^n{i-1\choose k}\\ &=m^{n-1-k}{n\choose k+1}\sum_{t=1}^m(t-1)^k \end{aligned}$$

前两项容易求出，而后面的东西是一个自然数幂和，这个东西比较麻烦。

回顾我们熟悉的自然数幂和求法，主要有以下几种（假设求$\sum_{i=1}^n i^k$）

• 插值：这种做法适用于$k$不变的情况，但这道题中$k$是变化的。
• 斯特林数转下降幂：可以很方便地$O(k^2)$求出一个，但是很难优化。
• 伯努利数：适用于底数固定，指数变化的情况。

因此我们选择伯努利数，它的式子是这样的：

记伯努利数的$EGF$为$B(x)$，则有$B(x)=\frac{x}{e^x-1}$。这个可以通过求逆快速求出。

有

$$\sum_{i=1}^ni^k=\frac{1}{k+1}\sum_{i=0}^k{k+1\choose i}B_{i}n^{k+1-i}$$

求出$f$之后我们有

$$\begin{aligned} f_i&=\sum_{j\geq i}g_j{j\choose i}\\ g_i&=\sum_{j\geq i}f_i{j\choose i}(-1)^{j-i} \end{aligned}$$

再跑一遍差卷积即可。