emm。好久没写这玩意了，来更一发。

游戏

题意：

给定一个DAG 以及起点 \(s\)。保证 \(s\) 能到达所有点。定义一条边 \(u \rightarrow v\) 的权值为 \(s\) 到 \(v\) 最少经过的边数。求 \(s\) 到每个点的必经之边的权值最小是多少。

分析：

由于是 DAG，可以用拓扑排序跑 DP。

记 \(f_i\) 表示离 \(i\) 最远的必经之边的编号，如果没有就是 \(0\)。

考虑对于一条边 \(e:x \rightarrow y\) 如何转移：

\(y\) 的入度为 \(1\)：此时如果 \(f_{x}=0\)，有 \(f_{y}=e\)；否则，\(f_{y}=f_{x}\)。
\(y\) 的入度大于 \(1\)：如果所有 \(f_{x}\) 均相同，那么 \(f_{y}=f_{x}\)；否则，\(f_{y}=0\)。

情况 \(1\) 显然。情况 \(2\) 的证明如下：

这里令 \(f_{x_1} \ne f_{x_2}\)。
显然 \(s\) 到 \(x_1\) 的所有路径与 \(s\) 到 \(x_2\) 的所有路径互不相交，否则一定存在一条到 \(x_1\) 或 \(x_2\) 的路径同时经过 \(f_{x_1},f_{x_2}\)，与 \(f\) 的定义矛盾。

于是不存在必经之边，即 \(f_{y}=0\)。

时间复杂度 \(O(n+m)\)。

棋盘

题意：

你有一个 \(n \times m\) 的棋盘，最初，棋盘上每个棋⼦都是正面朝上，每次操作你可以选择⼀个 \(X \times Y\)的矩形，选择该矩形内的任意一些棋子翻转（正面朝上的变成反面朝上、反面朝上的变成正面朝上）。问你使用不超过两次操作能形成不同棋盘的方案数。

分析：

解决该问题需要一些巧妙的 dp 技巧。

从操作入手是困难的，因此从合法棋子布局入手。

如图，我们枚举红色长方形的长和宽，得到条件1：每条边都至少有一个棋子。

这样就成功把方案分成了 \(nm\) 类。

条件2：每个棋子都必须在绿色的两个矩形内（即出现在左上角、右下角或者右上角、左下角）。

现在尝试计算出每一类的方案数。

当然可以大力容斥，不过这里提供一种优雅的解决方案：

对每个位置的棋子用一个 \(6\) 位二进制数表示（是否在矩形的上边，是否在矩形的左边，是否在矩形的右边，是否在矩形的下边，是否在左上角、右下角，是否在右上角、左下角）

对于我们选定的棋子所表示的数集合记为 \(S\)。显然，那么对 \(S\) 的前 \(4\) 位取与，后 \(2\) 位取或所得到的合法情况，只有 \(111110,111101,111111\) 这三种。

再记一个 \(cnt_i\) 表示所表示的数为 \(i\) 的位置的个数。然后就可以背包解决。

时间复杂度 \(O(nm(nm+2^{12}))\)。

\(k\) 次多项式

题意：

我们称两个⻓度相同的序列 \(a_0,a_1,...,a_{n-1}\) 和 \(b_0,b_1,...,b_{n-1}\) 相似，当且仅当存在⼀个不超过 \(k\) 次多项式，满足对所有 \(0 \le i < n\) 满足 \(P(i) \equiv (a_i-b_i)(\mod 998244353)\)。

给定两个⻓度为 \(n\) 的序列 \(a\) 和 \(b\)，找到最小的 \(x\)，使得 \(b_{x \mod n},b_{(x+1) \mod n},...,b_{x+n-1} \mod n\) 和 \(a\) 相似。

\(n \le 10 ^ 5,k \le 10^9\)。