随机化

杂题

[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.

注意事项:

ull自然溢出是废物, 只要01串为 $\mathrm{popcount(x)}$ 奇偶性, 无论基数是什么都冲突.
固定质数 $p$ , 在 $[1, p)$ 中随机基数, 固定基数, 在 $[n, 2n]$ 中随机质数, 出错概率在 $10^{-4}$ 量级
__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说不能用多项式复合, 原因是”不是自由群”? ?

从这往下的部分是231221南外随机化专题

P9737 [COCI2022-2023#2] Lampice

$n\times m$ 平面上 $k$ 种灯, 每种有两盏, 求有多少个矩形满足不存在一对同种灯一盏在矩形内一盏在矩形外.

$n\le 150, m\le 1000, k\le 200000$

看到这种两个都在等于两个都不在的情况, 考虑异或, 给每种灯一个异或值满足条件当且仅当为 $0$.

枚举矩形判定即可.

CF1310D Tourism

$N$ 个点的图, 给你图的邻接矩阵, 求从点 $1$ 出发经过 $K$ 条边回到点 $1$, 且路径上没有奇环的最短距离

$2 \leq N \leq 80 , 2 \leq K \leq 10$

没有奇环考虑二分图染色, 那么随便染色钦点走的路径相邻两点颜色不同, 那么染对的概率是 $\dfrac{1}{512}$, 算一下发现跑5000遍差不多了.

HDU6664 Andy and Maze

给一张图 $Graph(n, m)$, 求经过 $k$ 个点的简单路径的长度最大值

$n, m\le 10^4, k\le 6$

如果 $n$ 很小可以直接记录点集编号. 因为 $k$ 很小, 考虑给每个点随一个 $1\ldots k$ 的编号要求走过路径编号不重复, 正确率显然是 $\dfrac{k! }{k^k}\approx 0. 98$, 多跑几遍.

CF364D Ghd

定义一个集合的Ghd为所有大小至少为一半的子集的 $\mathrm{gcd}$ 的最大值.

给定集合 $a$, 求 $a$ 的Ghd.

和刚才那个类似? 随一个数有一半的概率在最终子集中, 所以随十几次, 每次枚举这个数的因数, 遍历所有的数加到对应因数上, 然后做一遍超集和, 从大到小枚举判定

CF1728E Red-Black Pepper

有 $n$ 盘菜, 每盘菜要加入红辣椒或黑辣椒, 其中第 $i$ 盘菜加入红辣椒会增加 $a_i$ 点美味值, 黑辣椒增加 $b_i$ 点. (每盘菜都会且只会加入一份红辣椒或一份黑辣椒, 且不能两种都加)

现在有 $m$ 个商店, 每个商店 $j$ 有无数包两种辣椒, 一包红辣椒有 $x_j$ 份红辣椒, 一包黑辣椒有 $y_j$ 份黑辣椒(每份辣椒只可以加入一盘菜), 求对于每个商店, 若只从这个商店买辣椒得到的最大美味值是多少(买到的辣椒份数必须正好等于 $n$, 不能多也不能少, 若无法实现则输出 $-1$).

$n, m\le 3\times 10^5$

没有懂和随机化有什么关系, 但反正简单题

设 $n$ 份辣椒中有 $i$ 份为红辣椒的答案为 $f_i$, 可以先全选 $a$ 然后按 $b-a$ 排序加入.

然后众所周知的结论因为 $x_ja+y_jb=n$ 的同余方程中 $a$ 的取值是等差数列, $x_ja$ 也是, 所以就是查等差数列位置最值, 直接根号分治秒了.

[ABC314Ex] Disk and Segments

给定 $n$ 条线段, 求最小的圆使得没有一条线段全部在圆外.
$n\le 100$, 误差 $10^{-5}$

退火!

CF1114E Arithmetic Progression

交互题, 有一个 ${a_n}$, 保证从小到大排序后是等差数列, 不超过 $60$ 次询问求公差和首项, 每次可以给定 $x$ 问 $a_x$ 或问是否有严格大于 $x$ 的数.

$n\le 10^6, a_i\le 10^9$

末项可以二分, 任意问两个数, 公差一定是它们差的因数, 期望很少次gcd出公差, 然后就能确定首项.