20200423 SCOI模拟2

A - 矩阵求和

答案是

$$\begin{gathered} \sum_{i=lx}^{rx} \sum_{j=ly}^{ry} (a_i (m-1) + b_j) \binom{rx-i+k}{k} \binom{ry-j+k}{k} \end{gathered}$$

把组合数拆开，用树状数组维护区间的 $\sum a_i i^j (j\in [0,maxk])$。

时间复杂度 $O\left(q\left(k\log n + k^2\right)\right)$。

B - 西行寺无余涅槃

可以参考一下CF1119H（点此传送到command_block的题解）的做法。

下文中，把 $F$ 数组 FWT 之后的结果写为 $FWT(F)$，把其中第 $i$ 个元素写为 $FWT(F)[i]$。

设

$$F_t[x] = \sum_{p_{t,j} = x} a_j$$

只要对每个 $i\in [0,2^m)$，求出 $\prod_{t=1}^n \left(FWT(F_t)[i]\right)$，就能得到答案。

$FWT(F_t)$ 中的每一项一定都是 $(-1)^{x_1} a_1 + (-1)^{x_2}a_2 + \cdots + (-1)^{x_k}a_k$ 的形式，这只有 $2^k$ 种不同的取值。由于 $k$ 很小，考虑求出每种取值出现了多少次。

设

$$C_{i,S} = \sum_{t=1}^n \prod_{j=0}^{k-1}\left[{bitcount(i\& p_{t,j})\bmod {2}} = [j\in S]\right]$$

显然有

$$\begin{gathered} \prod_{t=1}^n (FWT(F_t)[i])\\ = \prod_{S=0}^{2^k-1}\left( \sum_{j\notin S} a_j - \sum_{j\in S} a_j\right)^{C_{i,S}} \end{gathered}$$

想办法构建方程解出 $C_{i,S}$。

选取一个 $\{0,1,\cdots k-1\}$ 的子集 $T$，令

$$\begin{gathered} G_{T,t}[j] = \left[\bigoplus_{x\in T} p_{t,x} = j\right]\\ D_{i,T} = \sum_{t=1}^n \left(FWT(G_{T,t})[i]\right) \end{gathered}$$

则

$$\begin{gathered} FWT(G_{T,t})[i]=(-1)^{bitcount\left(i\& \left(\bigoplus_{x\in T} p_{t,x}\right)\right)}\\ = (-1)^{\sum_{x\in T} bitcount(i\& p_{t,x})}\\ D_{i,T}\\ = \sum_{t=1}^n \left(FWT\left(G_{T,t}\right)[i] \right)\\ = \sum_{t=1}^n (-1)^{\sum_{x\in T} bitcount(i\& p_{t,x})}\\ = \sum_{S\in [0,2^k)} (-1)^{bitcount(S\&T)} \cdot C_{i,S} \end{gathered}$$

所以 $C_{i} = IFWT(D_i)$。

而 $\sum_t FWT(G_{T,t}) = FWT\left(\sum_t G_{T,t} \right)$，枚举完 $T$ 之后 $O(nk + 2^m m)$ 计算即可求出所有的 $D_{i,T}$ 。

总时间复杂度为 $O(2^k (nk+2^m m) + 2^m2^k k)$。

C - 鱼贯而入

做法 0

特判 $n=1,2,3$。对于 $a_i$ 随机的数据来说，最优的 $len$ 一定不会比 $n$ 大太多。

做法 1

显然只有当 $\exists i,j, len\mid (a_i - a_j)$ 的时候，$Ans > 0$。如此直接枚举 $len$ 计算。

做法 3

根据模运算的一些性质，$kp$ 有的寻址时间 $p$ 一定也有。设 $mind(n)$ 为 $n$ 的最小质因子，那么我们只需要检查满足 $\frac{len}{mind(len)} < n \le len$ 的 $len$。

$a_i - a_j$ 的大于等于 $n$ 的质因子一定是可以的。可以的合数一定在 $[n,n^2]$ 内。分别枚举并检查即可。

做法 4

把 Pollard-rho 求 gcd 的那个 $O(\log n)$ 优化掉（可以参考wch的博客）。这样可以得到 100 分。