Contest Info

date: 2018.08.09 12:00-17:00

practice link

Solutions

A. Circulant Matrix

题目大意：给出一个线性方程组 \(\sum_{j=0}^{n-1}a[i\oplus j]\cdot x[j]=b[i]\)，求解 \(X\)。

题解：考虑递归求解。

\(n=1\) 时直接计算即可。

\(n>1\) 时，我们将相邻的两个方程两两合并，可以得到一个 \(n/2\) 阶线性方程组： \[ b[2i]+b[2i+1]=\sum_{j=0}^{n/2-1}(a[2(i\oplus j)]+a[2(i\oplus j)+1])(x[2j]+x[2j+1]) \] 于是我们可以解出所有的 \(x[2j]+x[2j+1]\)。

再将所有的 \(x[2j+1]\) 代换成 \((x[2j]+x[2j+1])-x[2j]\)，可以发现，常数项可以用 FWT 计算，系数则变成了 \(a[2j]-a[2j+1]\)，具体式子就不写了。这样又得到一个 \(n/2\) 阶线性方程组。

时间复杂度 \(\mathcal{O}(n\log^{2}n)\)。

coldwater’s comment:

然而题目就是给了 \(a\) 和 \(x\) 求 FWT 的结果 \(b\)，求解 \(x\)，直接 FWT 就完事儿了。

B. Enumeration not optimization

题目大意：给出一个 \(n\le12\) 个点，\(m\le1000\) 条边的无向连通图。对于原图的任意一个有根生成树，树中一条边的贡献是它的边权乘上两个点中较大的深度。求所有有根生成树中边的贡献之和，答案取模。

题解：令 \(f[u][s]\) 和 \(g[u][s]\) 分别为以 \(u\) 为根其它点的集合为 \(s\) 时的所有方案的深度之和，以及方案数。转移时枚举 \(s\) 的一个子集（必须包括 \(\text{lowbit}(s)\) ），这个子集只由一条边连接到 \(u\)，剩下的部分随意，就不会重复了。

最后枚举每条边，枚举两个端点两边的连通块集合算答案即可。根据实现方法不同，时间复杂度为 \(\mathcal{O}(n^2\cdot3^n)\) 或 \(\mathcal{O}(n^2\cdot2^n+n\cdot3^n)\)。

C. Gambling

题目大意：题意杀。按照题解的意思大概是这样：两个队进行 \(2n-1\) 场比赛，先赢 \(n\) 场的队赢得整个比赛。一个人来赌博，他想赌 \(2^{2n-1}\) 元某个队赢。但是按规定他只能一场一场地赌，设某场比赛他押了 \(x\) 元，如果赢了，他收益 \(x\) 元，否则损失 \(x\) 元。另外，要求这个人当前的财产 \(s\) 和该队的胜率 \(p\) 必须时刻满足 \(s=2^{2n}p-2^{2n-1}\)（也就是和他赌整个比赛等价）。这样一来，他每场下注的金额就唯一确定了，求每场的金额。

题解：可见题目的关键在于求胜率。设 \(dp_{i,j}\) 表示目前赢 \(i\) 场，输 \(j\) 场下的胜率，那么显然有 \(dp_{i,j}=\frac{1}{2}(dp_{i+1,j}+dp_{i,j+1})\)，即 \(dp_{i+1,j}-dp_{i,j}=dp_{i,j}-dp_{i,j+1}\)。

那么在赢 \(i\) 场，输 \(j\) 场的情况下，应下的赌注即为 \(2^{2n}(dp_{i+1,j}-dp_{i,j})\)。但是这样 \(dp\) 的复杂度太高，考虑用组合数求解。不妨设 \(2n-1\) 场比赛全部打完，那么就是赢得 \(\ge n\) 场比赛的队伍获胜，显然这与原模型是等价的。我们有 \(\displaystyle{dp_{i+1,j}=\frac{\sum_{k=n-i-1}^{2n-2-i-j}{2n-2-i-j\choose k}}{2^{2n-2-i-j}}}\)，\(\displaystyle{dp_{i,j+1}=\frac{\sum_{k=n-i}^{2n-2-i-j}{2n-2-i-j\choose k}}{2^{2n-2-i-j}}}\)，那么答案为 \(\displaystyle{\frac{1}{2}(dp_{i+1,j}-dp_{i,j+1})\cdot 2^{2n}=\frac{{2n-2-i-j\choose n-i-1}}{2^{2n-1-i-j}}\cdot2^{2n}=2^{i+j+1}{2n-2-i-j\choose n-i-1}}\)。

D. The number of circuits

题目大意：给定 \(k\leq 7\) 和 \(n(2k+1\leq n\leq 10^9)\)。\(n\) 个点的有向图中边为 \(i\rightarrow (i+j)\text{ mod } n(\forall j \in [1, k])\)，问图中本质不同欧拉路的条数。

题解：best theorem 可知，答案为：

\[ t_w(G)\prod_{i=1}^n(\deg(i) - 1)!=t_w(G)\cdot ((k-1)!)^n \]

考虑计算 \(t_w(G)\)，用 matrix-tree 定理，可以发现对于固定的 \(k\)，\(n\) 是满足线性递推关系的，我们用 BM 计算即可。

E. Music Game

签到题

F. Typing practice

题目大意：有 \(n\le4\) 个字符串 \(s_1,\cdots,s_n\) ，总长度 \(m\le10^5\) ，只有小写英文字母。操作序列 \(t\)，长度 \(k\le10^5\) ，每次操作可以在末尾加一个字母或者退格。对于每次操作之后，询问至少要加多少字母，使得末尾出现至少一个字符串 \(s_i\) 。

题解：可以做 \(n\) 次 kmp 再对每个串的答案取最小，撤销操作会使 kmp 的势能分析失效，直接做是平方级别的，但是可以 bfs 一次 fail 树预处理出所有转移，复杂度 \(\mathcal{O}(|\Sigma|m+nk)\)。

G. Longest Common Subsequence

题目大意：给出四个长度为 \(n\le10000\) 的数列，值域都是 \([1,n]\)。满足前三个数列中，任意一个数字出现次数不超过两次，求四个数列的 LCS。

题解：第四个数列选择任意一种数字作为结尾，对应的其在前三个数列中的出现位置只有不超过 \(8\) 种。按 LCS 的结尾在第四个数列中的位置升序进行 dp ，用 kd 树维护一下三维偏序求最大值即可。复杂度 \(\mathcal{O}(n^{5/3})\)。

H. Prefix Sum

题目大意：\(k+1\) 行 \(n\) 列的矩阵，编号均从 \(0\) 开始。每一层是上一层的前缀和，也即 \(a[i][j]=\sum_{t=0}^{j}a[i-1][t]\) 。两种操作，修改操作会改变第 \(0\) 层 \(a[0][i]\)，询问操作会询问第 \(k\) 层某个 \(a[k][i]\)， \(k\) 固定。

题解：容易知道 \(a[k][i]=\sum_{j=0}^{i}{k-1+i-j\choose k-1}a[0][j]\)，接下来为了方便，用 \(k\) 来代替 \(k-1\)。注意到 \({k+i-j\choose k}\) 可以表示成关于 \(i-j\) 的 \(k\) 次多项式，不妨设它的系数为 \(b_{0},\cdots,b_{k}\)，那么有： \[ \begin{aligned} a[k][i]&=\sum_{j=0}^{i}a[0][j]\sum_{u=0}^{k}b_{u}(i-j)^{u}\\ &=\sum_{j=0}^{i}a[0][j]\sum_{u=0}^{k}b_{u}\sum_{v=0}^{u}i^{u-v}(-j)^{v}{u\choose v}\\ &=\sum_{v=0}^{k}\left(\sum_{j=0}^{i}(-j)^{v}a[0][j]\right)\left(\sum_{u=v}^{k}b_{u}i^{u-v}{u\choose v}\right) \end{aligned} \] 上面的乘积左边可以用 \(k+1\) 个树状数组来维护，右边是一个常数，可以 \(\mathcal{O}(k^{2})\) 计算。时间复杂度 \(\mathcal{O}(nk^{2}+nk\log n)\)。

I. Juggernaut

题目大意：求所有 \(n\times m\) 的 \(0/1\) 矩阵中，有多少种本质不同且使得每行每列的异或和均为 \(0\)。本质相同定义为存在 \(x,y\) 使得 \(A_{i,j}=B_{(i+x)\text{ mod }n,(j+y)\text{ mod }m}\)。\(n,m\le10^{9}\)，答案对 \(998244353\) 取模。

题解：根据 Burnside 引理，答案为 \(\displaystyle{\frac{\sum_{i=1}^{n}\sum_{j=1}^{m}f_{i,j}}{nm}}\)，其中 \(f_{i,j}\) 表示 \(x=i,y=j\) 的循环移动下保持不变的方案数。

容易发现，\(\displaystyle f_{i,j}=f_{\gcd(i,n),\gcd(j,m)}\)。因此答案为 \(\displaystyle{\frac{\sum_{u\mid n}\sum_{v\mid m}\varphi(\frac{n}{u})\varphi(\frac{m}{v})f_{u,v}}{nm}}\)。由于 \(10^{9}\) 以内的数的约数至多有 \(1344\) 个，因此我们可以暴力枚举 \(u,v\)。

考虑 \(f_{u,v}\) 的计算，其中 \(u\mid n,v\mid m\)。如果不考虑异或和为 \(0\)，那么我们有 \(A_{[0,u)\times [0,v)}\) 中的 \(uv\) 个元素互不相关，考虑把它们缩成一块（其它块以此类推）。这样，我们的循环同构就可以写成 \(\displaystyle{A'_{i,j}=B'_{(i+1)\text{ mod }n/u,(j+1)\text{ mod }m/v}}\)。

考虑计算每一块在每行每列出现的次数。一块在整个矩阵中出现的次数是 \(\text{lcm}(n/u,m/v)\)（不妨记为 \(\text{lcm}\)），那么它在每一行出现的次数是 \(\displaystyle{\frac{\text{lcm}}{n/u}}\)，在每一列出现的次数是 \(\displaystyle{\frac{\text{lcm}}{m/v}}\)。接下来分情况讨论：

• 若在每行每列都出现奇数次，例如： \[ \begin{pmatrix} a_{1}&a_{2}&a_{3}\\ a_{3}&a_{1}&a_{2}\\ a_{2}&a_{3}&a_{1} \end{pmatrix} \] 那么块 \(a_{3}\) 中最右边一列和最下面一行的元素不能自由选取，而是由前面的元素中 \(1\) 的个数唯一决定，因此答案为： \[ 2^{\displaystyle nm/\text{lcm}-u-v+1} \]

• 若在每行出现奇数次，在每列出现偶数次，例如： \[ \begin{pmatrix} a_{1}&a_{2}&a_{1}&a_{2}&a_{1}&a_{2}\\ a_{2}&a_{1}&a_{2}&a_{1}&a_{2}&a_{1}\\ a_{1}&a_{2}&a_{1}&a_{2}&a_{1}&a_{2}\\ a_{2}&a_{1}&a_{2}&a_{1}&a_{2}&a_{1}\\ \end{pmatrix} \] 那么块 \(a_{2}\) 中最右边一列的元素不能自由选取，因此答案为： \[ 2^{\displaystyle{nm/\text{lcm}-u+1}} \]

• 若在每行出现偶数次，在每列出现奇数次，例如： \[ \begin{pmatrix} a_{1}&a_{2}&a_{1}&a_{2}\\ a_{2}&a_{1}&a_{2}&a_{1}\\ a_{1}&a_{2}&a_{1}&a_{2}\\ a_{2}&a_{1}&a_{2}&a_{1}\\ a_{1}&a_{2}&a_{1}&a_{2}\\ a_{2}&a_{1}&a_{2}&a_{1}\\ \end{pmatrix} \] 那么块 \(a_{2}\) 中最下面一行的元素不能自由选取，因此答案为： \[ 2^{\displaystyle{nm/\text{lcm}-v+1}} \]

• 每行每列都出现偶数次是不可能的，因为 \(\text{lcm}\) 中 \(2\) 的幂次至少跟 \(n/u\) 和 \(m/v\) 中的一个相同。

当 \(n,m\) 中至少有一个等于 \(998244353\) 时，除法操作就无法完成了。这里有一个常见技巧，就是在计算过程中对 \(nmp\) 取模，最后再直接除以 \(nm\)。这样中间过程的数据范围会达到 \(10^{54}\)，需要使用大整数。

Dirt Replay

A: -1 一个地方取模写错

F: -3 退格处理错误；算法TLE；假的记忆化TLE（小错误掩盖了算法错误）

G: -2 kd树询问坐标没减一；变量n打成了tot导致RE