[sdfzoj contest #1]记录

构造一个有向图满足其以1为根的内向生成树个数对 $10^18+3$ 取模为 $k$ .
要求构造的有向图点数不超过100, 边数不超过 $3\times 10^5$

首先众所周知的一个DAG的生成树个数是所有节点的入度的乘积. 那么要控制入度, 考虑直接让1到每个节点连一堆边就控制了入度, 所以现在问题是要选若干个数乘积在膜意义下等于 $k$ .

这个东西我们不会做, 可以智慧. 假设要等于一个数, 那么给2号点随机一个入度, 就直接给 $k$ 乘上一个逆元, 这很好因为你发现这样做把出题人精心构造的 $k$ 变成了近乎随机的. 那么现在你手里由一个随机的 $k$ , 于是接着随机每个节点的入度, 判断此时乘上一堆逆元之后的 $k$ 是否可以由小于某个阈值的质数表示, 如果随到最后还没弄出来就从头再来.

复杂度算不出来, 但qyc说他写出来之后只跑了1s多一点. 考虑剪枝, 考虑判断一个数是不是可以分解为小于某个数的质数这件事比较费时, 所以仅在它膜常数 $C$ 为0的时候去判断. 这样做相当于把值域缩小到 $\dfrac{1}{C}$ , 就能跑了.

qyc说比较好的参数是 $5\times 10^4$ , $C=360$

Hash

模拟赛被卡hash.

注意事项:

  1. ull自然溢出是废物, 只要01串为 $\operatorname{popcount(x)}$ 奇偶性, 无论基数是什么都冲突.
  2. 固定质数 $p$ , 在 $[1, p)$ 中随机基数, 固定基数, 在 $[n, 2n]$ 中随机质数, 出错概率在 $10^{-4}$ 量级
  3. __int128的确慢的离谱, 使用双模hash代替一个大质数

EI说哈希常用的两个理论:

  • 一个是非零向量点乘一个随机向量, 那为0的概率是 $\dfrac{1}{q}$ , $q$ 是域的大小.
  • Schwarz–Zippel引理: 对域 $F$ 上一个不恒为0的多项式 $n$ 元 $d$ 次多项式 $P$ , 独立随机 $n$ 个变量 $x_1\ldots x_n$ 使得 $P(x_1, \ldots, x_n)=0$ 的概率是 $\dfrac{d}{\vert F\vert}$

~~但我不知道怎么用. ~~

Qoj #6504. Flower’s Land 2

有 $k$ 种引号, $q$ 次询问区间是否引号匹配, 或者区间把 $i$ 种引号改成 $(i+1)\pmod k$ 种引号.

$n, q\le 5\times 10^5, k=3$

“这是想得到啊”

对每种引号, 随机一个可逆矩阵, 然后为奇数次出现赋值这个矩阵, 为偶数次赋值它的逆, 然后判断区间乘起来是不是单位矩阵. 因为修改直接维护加一次, 加两次的结果.

这里不能用多项式乘法, 素数等等, 因为你需要它不交换, 性质尽可能烂.

然后qyc说sqy说不能用多项式复合, 原因是”不是自由群”? ?