【杂文】NOI Online2020 Round3 划水记

# **【杂文】NOI Online2020 Round3 划水记** [$\mathcal{My}\ \mathcal{Blog}$](https://www.cnblogs.com/Xing-Ling/p/12950475.html) 今天的题依旧水得不行（$...$ 卡常大赛？） 这次准备按顺序做。 $T1:$ $...$ 我怀疑你在侮辱我的智商，而且我有证据 $...$ $T2:$ 暗示已经很明显了，把边信息存到一个 $n^2$ 大小的矩阵里，直接跑矩阵快速幂即可。 具体的说，设 $v(i)=f(0,i )$，矩阵 $base$ 中 $a(i,j)$ 表示点 $i,j$ 之间是否有边，矩阵 $A(t)$ 中 $a(i,j)$ 表示 $f(i,t)$ 异或到 $v(j)$ 的次数，按照标准矩阵乘法转移即可。对于一次询问 $time$，求出 $B=A(0)*base^{time}$，然后对于每个 $i$，把 $v(i)$ 拿来异或 $B.a(1,i)$ 次即为答案。 复杂度 $O(qn^3\log inf)$，过不去。 由于异或的良好性质，可以把矩阵中的所有值都对 $2$ 进行取模，这样答案是不会变的。取模后就只有 $0$ 和 $1$ 了，上 $bitset$ 。 复杂度 $O(\frac{qn^3}{w}\log inf)$ 。 刚好 $10^8$，有点悬，极限数据跑了 $1.34s$，还需要卡下常 想了一下，把快速幂换成倍增就可以了，极限 $0.47s$ 。 $T3:$ 首先，选子序列可以视为选出一些排列。 先考虑 $and$ 的特性，发现最终的 $\sum a$ 不会超过 $2^{18}=262144$，于是很自然地想到预处理 $phi$，然后分别计算加出每一种 $\sum a$ 的方案数，最后扫一遍可能的值统计答案。 一开始想的是按照顺序一个一个往后面加，用 $f(i,j)$ 表示加到第 $i$ 个点，目前 $\sum a$ 的值为 $j$ 的方案数，则有 $f(i,j)=\sum_{i \& j=0,i|j=k} f(i-1,k)*cnt(l)$，但这里的 $cnt$ 极其难搞，于是作罢。 又重新 $yy$ 了一下，发现第一维根本就不需要啊，直接 $f(j)=\sum_{i \& j=0,i|j=k} f(k)*cnt(l)$，其中 $cnt(l)$ 为 $1$ 至 $n$ 中值为 $l$ 的个数。 这样的话就很简单了，对于每个 $j$，直接枚举它的子集作为 $k$ 进行转移即可。 复杂度 $O(3^{\log inf})$，最大是 $3*10^8$，极限 $3.5s$，于是又是一波恶心人的卡常（最难受的就是取模，慢得不行），好不容易才卡进了 $1.7s$，突然意识到自己造的随机数据有大量空状态，常数小是必然的..... 懒得想其他做法了，把一切都交给 $\text{CCF}$ 的老爷机吧... $updata:$ 经 [$\text{Owen\_codeisqueen}$](https://www.luogu.com.cn/user/77426) 聚佬指点，用 [$\text{[WC2018]}$ 州区划分](https://www.luogu.com.cn/problem/P4221) 类似的做法可以优化到 $O(2^{\log}\log^2)$ 。 期望得分： $100+100+100$ 。 民间数据：$100+100+10$ 。 哎... $T3$ 写挂了... $f(0)$ 应该初始化为 $2^{cnt(0)}$ 的，不知道为啥我写了个 $cnt(0)+1$ ...而且对拍也莫名其妙地没有拍出来...自闭... 实际得分：$100+100+10$ 。 嘛..不管怎么说，至少比第二场要好些了...