NOI2012 随机数生成器

注意到可以用矩阵快速幂求解。

$\begin{bmatrix} X_1 & 1 \end{bmatrix} \times \begin{bmatrix} a & 0\\ c & 1 \end{bmatrix}^n$

NOI2013 矩阵游戏

神秘题目，感觉比较简单。

注意到答案可以写作：

$\begin{bmatrix} 1 & 1\\ \end{bmatrix} \times \begin{bmatrix} a & 0\\ b & 1 \end{bmatrix} ^{m-1} \times \left(\begin{bmatrix} c & 0\\ d & 1 \end{bmatrix} \times \begin{bmatrix} a & 0\\ b & 1 \end{bmatrix} ^{m-1}\right)^{n-1}$

考虑使用十进制快速幂求解，那么我们每一位的考虑，对于乘 $[0,9]$ 的幂次用普通快速幂。

于是做完了，时间复杂度为 $O(\lvert n\rvert+\lvert m\rvert)$。

CQOI2013 新Nim游戏

先读题，需要注意是第一次乱拿而后面按照 nim 游戏进行博弈。

首先，有定没有必败情况，我们可以先拿 $n-1$ 堆，然后让对面什么都干不了，最后把最后一堆全部拿了直接获胜。

考虑怎么求出最小值，因为 nim 的必败情况是所有的数 $\oplus$ 起来是 $0$，于是我们就需要从里面找出一个 $\sum$ 最大的集合满足其所有的子集 $\oplus$ 起来都不是 $0$。

于是想到线性基，我们排序之后向线性基内加入，时间复杂度为 $O(n\log V)$。

CF895C Square Subsets

对于平方数，容易理解其所有的因子出现的次数都是偶数，于是我们可以开一个数组用二进制记录每个数因子的情况。

把他们塞到一个线性基里面，那么剩下的元素都是可以用线性基里面元素随意组合得到的，于是最终方案事就为 $2^{m-\lvert S\rvert }-1$ 种。

CF1163E Magical Permutation

首先我们把 $S$ 中的数丢到一个线性基里面，那么有结论 $x$ 就是线性基的大小。

首先有性质，所有的魔法序列中的元素都是线性基中的元素可以表示出来的。

我们不妨设第一个元素为 $0$，那么第二个元素就一定是线性基中的元素，因为 $2,3$ 个元素之间的之一定是 $S$ 中的元素，所以也一定是线性基中的若干元素，于是第 $3$ 个元素也一定是线性基内可以表示出来的。

所以 $x$ 的上限就是线性基的大小，接下来我们可以通过构造的方式得到一个长度为 $2^{x}$ 的序列。

考虑我们先构造一个长度为 $2^x$ 的 $1\sim 2^x$ 的格雷码（就是相邻两个数 $\oplus$ 起来的 $\operatorname{popcount}=1$），那么我们不妨设 $p$ 是 $a_i\oplus a_{i+1}$ 为 $1$ 的那一位。

于是我们把线性基中最高位是 $p$ 的那个元素，把它作为 $ans_i\oplus ans_{i+1}$ 的值。

考虑怎么构造一个格雷码，我们先把少一位的格雷码复制一遍然后反转一次最后接到后面，在原本的位置左侧加上一个 $0$，复制的在左侧上加一个 $1$，于是我们就得到了一个新的格雷码。

做完了，时间复杂度为 $O(n\log n)$。

CF1100F Ivan and Burgers

一个很牛的想法，先考虑如果知道 $[l,r]$ 的线性基怎么做。

我们直接写线性基，需要注意因为二进制天然可以贪心，所以我们从最高位开始考虑。

那么我们只需要判断 $\oplus$ 上这一位是否更优就行了，时间复杂度为 $O(\log V)$。

考虑一个类似于扫描线的思虑，我们给所有的右端点都开一个线性基，从最高位开始向地位位置尽量靠近 $r$ 的线性基。

询问的时候我们在判断 $\oplus$ 上是否优秀时同时判断是否在 $[l,r]$ 中就行了，时间复杂度为 $O(q\log V)$。

NOI2018 冒泡排序

https://www.明天动手.top/post/qia-te-lan-shu-he-si-te-lin-shu

Harvest of Apples

我们令：

$F(n,m)=\sum\limits_{i=0}^m {n\choose i}$

那么，就有：

$F(n+1,m)=\sum\limits_{i=0}^ m{n\choose i}+{n\choose i-1}=F(n,m)+F(n,m-1)$

于是就有：

$F(n,m)=2\times F(n-1,m)-{n-1\choose m}$

我们对行进行分块，把 $\sqrt{N}$ 行压成一块，那么我们直接取靠近的 $n$ 的块头然后 $\sqrt{n}$ 递推即可。

对于最后无法处理的，直接暴力计算即可，时间复杂度为 $O(q\sqrt n)$，略慢于莫队做法。

一种不正确的推法：

首先需要学习范德蒙恒等式，式子为：

$\sum\limits_{j=0}^m {i\choose j}{n-i\choose m-j}={n\choose m}$

对于这个式子，我们可以理解为 ${i\choose j}$ 置对 ${n\choose m}$ 造成的贡献为 ${n-i\choose m-j}$。
那么我们考虑题目的求解：

$\sum\limits_{p=0}^ m{n\choose p}=\sum\limits_{p=0}^{m}\sum\limits_{j=0}^p{i\choose j}{n-i\choose p-j}$

我们交换求和顺序，得到：

$\sum\limits_{j=0}^m{i\choose j}\sum\limits_{p=j}^m {n-i\choose p-j}$

注意到后面的 $\sum$ 获取的式子其实对 $j,m$ 的具体值不感兴趣，实际上重要的就只有 $m-j$，于是得到：

$\sum\limits_{j=0}^m{i\choose j}\sum\limits_{p=0}^{m-j}{n-i\choose p}$

那么我们把所有的 $m$（一共 $n\sqrt{n}$）个位置进行分块，拿出 $n$ 个块头，处理其向下走 $\sqrt{n}$ 步的结果。
因为我们要处理 $n\sqrt{n}$ 个位置，所以需要 $O(1)$ 处理 $n\gets n+1$ 的变化情况，那么就需要：

$F(n,m)=2\times F(n-1,m)-{n-1\choose m}$

于是我们就把一个简单题做困难了。

Separated Number

一个比较简单的题目，自己思考复杂了。

考虑第 $i$ 位对答案的贡献，容易理解其一定是一个形式如下的式子：

$a_i\times\sum\limits_{j=0}^{n-i} ct\times 10^j$

考虑把后面的 $ct$ 带着式子算出来。

如果 $i+j<n$，那么我们就已经把原数分成了 $2$ 段了，现在还需要插最多 $k-2$ 个板，那么方案数为：

$\sum\limits_{p=0}^{k-2} {n-j-2\choose p}$

如果 $i+j=n$，那么其实就之分成了一段，则方案数为：

$\sum\limits_{p=0}^{k-1}{n-j-1\choose p}$

我们令：

$F(n,m)=\sum\limits_{i=0}^m {n\choose i}$

则：

$\sum\limits_{j=0}^{n-i}ct\times 10^j=F(i-1,k-1)\times 10^{n-i}+\sum\limits_{j=0}^{n-i-1} F(n-j-2,k-2)\times 10^j$

那么我们令：

$G(m)=\sum\limits_{j=0}^m F(n-j-2,k-2)\times 10^j$

则我们可以通过上一个题目提前预处理出 $F(x,k-2)$，然后再算出 $G(x)$，后直接计算即可。

$Ans=\sum\limits_{i=1}^n a_i\times \left(F(i-1,k-1)\times 10^{n-i}+G(n-i-1)\right)$

CF1716F Bags with Balls

假设：

$x=\lceil\frac{m}{2}\rceil,y=\lfloor\frac{m}{2}\rfloor$

那么有柿子：

$\sum\limits_{i=0}^n i^k\times {n\choose i}\times x^iy^{n-i}$

注意到本题 $O(k^2)$ 可做，考虑写成斯特林数的形式，然后不展开通项公式。

$i^n=\sum\limits_{j=0}^n \dfrac{n!}{(i-j)!}\times \begin{Bmatrix} n\\j\end{Bmatrix}$

得到：

$\sum\limits_{i=0}^n \sum\limits_{j=0}^k \dfrac{i!}{(i-j)!}\times \begin{Bmatrix} k\\ j\end{Bmatrix}\times \dfrac{n!}{i!\times (n-i)!}\times x^iy^{n-i}$

简化一下：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\sum\limits_{i=0}^n \frac{n!\times x^iy^{n-i}}{(n-i)!\times (i-j)!}$

进行一些不好想的变化：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \sum\limits_{i=0}^n \frac{n!\times (n-j)!}{(n-j)!\times (n-i)!\times (i-j)!}\times x^iy^{n-i}$

然后：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \frac{n!}{(n-j)!}\times \sum\limits_{i=0}^n \frac{(n-j)!}{ (n-i)!\times (i-j)!}\times x^iy^{n-i}$

最后套路的把后面的阶乘写成组合数：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \frac{n!}{(n-j)!}\times \sum\limits_{i=0}^n {n-j\choose n-i}\times x^iy^{n-i}$

又是套路的，令 $p=n-i$，则：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \frac{n!}{(n-j)!}\times \sum\limits_{p=0}^{n-j} {n-j\choose p}\times x^{n-p}y^p$

注意到后面是一个类似于二项式定理的东西，那么我们调整一下系数：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \frac{n!}{(n-j)!}\times x^j\times \sum\limits_{p=0}^{n-j} {n-j\choose p}\times x^{n-p-j}y^p$

于是得到：

$\sum\limits_{j=0}^k \begin{Bmatrix} k\\ j\end{Bmatrix}\times \frac{n!}{(n-j)!}\times x^j\times m^{n-j}$

我们递推处理 $\begin{Bmatrix} n\\ m\end{Bmatrix}$，时间复杂度为 $O(k^2+qk)$。

ARC137D Prefix XORs

不是很有养分的套路题。

首先需要知道卢卡斯定理，即：

${n\choose m}\equiv {\lfloor\frac{n}{p}\rfloor\choose \lfloor \frac{m}{p}\rfloor}\times {n\bmod p\choose m\bmod p}\pmod p$

我们可以理解为在 $p$ 进制下整体左移一位乘以其末尾。

于是就有推论，在 $p=2$ 时只有 $m\subseteq n$ 的时候为 $1$。

于是考虑怎么做，我们把第 $i$ 次操作之后第 $j$ 个位置的值记作 $s_{i,j}$，那么显然：

$s_{i,j}=s_{i,j-1}\oplus s_{i-1,j}$

那么我们注意到 $s_{i,j}$ 会直接对 $s_{i+1,j}$ 和 $s_{i,j+1}$ 造成贡献，那么 $(i,j)$ 对 $(n,m)$ 造成的贡献就是通过向右和向下走到 $(n,m)$ 的方案数。

那么我们就得到 $s_{0,i}$ 对第 $k$ 次的贡献为 ${n+k-i\choose n-i}$，但是这个东西太丑了，考虑把 $a$ 反转，下表从 $0$ 开始用。

现在得到的贡献为 ${i+k\choose k}$，于是根据卢卡斯定理就有 $(i+k)\&k=k$ 时有贡献，换而言之就是 $i\cap k=\varnothing$。

那么我们只需要获得 $k$ 补集的所有子集的异或和就行了，于是我们记 $s_i$ 表示所有所有的 $j\cap i=j$ 的 $a_j$ 的异或和。

于是有转移：

$s_i=a_i\oplus \left(\bigoplus\limits_{j\subseteq i\wedge \operatorname{popcnt}(i\oplus j)=1} s_j\right)$

于是做完了，时间复杂度为 $O(n\log n)$。

CF1713F Lost Array

太帅的一个题目，注意到就是上一个题目的逆运算。

因为上一个题目需要用到补集的子集，所以不能直接快速的计算。

那么我们把行数从 $0$ 开始用，列数从 $1$ 开始用，借助反对角线为中间变量，就有：

$(0,n-k)\overset{{k\choose i}}{\rightarrow} (i,n-i),(i,n-i)\overset{{j\choose i}}{\rightarrow}(j,n)$

因为异或的子集和超集的逆运算都是其本身，所以我们输入 $a[0,n-1]$ 进行两次操作之后得到的就是 $a_n\sim a_1$。