哈希 Hash
概述
Hash （散列函数），其核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。这种转换是一种压缩映射，也就是说，不同的输入可能会映射到相同的值，造成哈希碰撞。
在 OI 中我们常用哈希来比较两数据是否相同，如：字符串哈希（序列哈希），树哈希（树同构），集合哈希。还有一种以 「key-value」 形式存储数据的数据结构：哈希表。
我们通常会设计一个 Hash 函数 FFF 将不方便比较的数据映射到整数。我们希望通过这个函数判断两个数据是否相等，具体来说，哈希函数最重要的性质可以概括为下面两条：
在 Hash 函数值不一样的时候，两个数据一定不一样；
在 Hash 函数值一样的时候，两个数据不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。
字符串哈希（序列哈希）
顾名思义，就是用哈希来判断字符串（序列）是否相等。
实现
通常我们采用的是多项式 Hash 的方法，现有 一个长度为 nnn 的字符串 SSS（下标以 111 开始），我们定义哈希函数 （其中 b,Mb,Mb,M 都是常数）
F(S)=∑i=1nS[i]×bn−i(modM)F(S)=\sum_{i ...
「CF213E」 Two Permutations
线段树维护序列哈希。
CF213E
题意
给出两个排列 a,ba,ba,b，长度分别为 n,mn,mn,m，你需要计算有多少个 xxx，使得 a1+x,a2+x,…,an+xa_1 + x,a_2 + x,\dots,a_n + xa1+x,a2+x,…,an+x 是 bbb 的子序列，n≤m≤2×105n \le m \le 2 \times 10^5n≤m≤2×105。
题解
枚举 xxx，由于 aia_iai 是排列，此时对应 aaa 的值域为 [1+x,n+x][1+x,n+x][1+x,n+x]，此时我们只需要将 bib_ibi 中在这个值域内的数提取出来（不改变顺序），判断与 a1+x,a2+x,…,an+xa_1+x,a_2+x,\dots,a_n+xa1+x,a2+x,…,an+x 是否相同即可。
考虑序列相同这里用到序列哈希，对于 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an，先预处理其哈希值 fff，那么 a1+x,a2+x,…,an+xa_1+x,a_2+x,\dots,a_n+xa1+x,a2+x,…,a ...
树上直径期望
微积分，多项式，概率期望。
GYM102155B Short Random Problem
题意
给你一颗 n (n≤80)n\;(n\le 80)n(n≤80) 个点的树，树上的每一条边的长度都是 [1,n][1,n][1,n] 的随机实数。 求直径的期望长度，对 109+710^9+7109+7 取模。
题解
总的思路：枚举一条边 (u,v)(u,v)(u,v) 计算直径中心在其上的贡献，即 直径中心在该边上的概率 乘 直径长度期望。
设 fu(x)=Pr[d(u)≤x]f_u(x)=Pr[d(u)\le x]fu(x)=Pr[d(u)≤x]，即表示 uuu 到子树中最长链长度小于 xxx 的概率，这是可以用多项式表示的，而且是一个连续的分段函数，以整数为分段界限。
考虑加上一条边：f(x)=∫x−1xg(y) dy\displaystyle f(x)=\int_{x-1}^x g(y)\,\mathrm{d}yf(x)=∫x−1xg(y)dy 。
考虑多条链中取最大：f(x)=∏fi(x)f(x)=\prod f_i(x)f(x)=∏fi(x)。
因为 Pr[m ...
「XXI Open Cup GP of Koread」
「XXI Open Cup. Grand Prix of Koread」
GYM 102759
官方题解(英文)
jiangly大佬的题解
Update 2021-4-18: 终于刷完了 QAQ。E,F,H 是之前写的，题解先咕了……
A - Advertisement Matching
GYM102759A
题意
有 nnn 个广告商，第 iii 个有 aia_iai 份广告，有 mmm 个人，第 iii 个人最多看 bib_ibi 份不同的广告。qqq 次修改，每次将 ax±1a_x\pm 1ax±1 或者 bx±1b_x\pm 1bx±1，修改是累计的。问每次修改后是否能将所有广告发完。（保证所有 ai,bia_i,b_iai,bi 在任意时刻为非负整数）
1≤n,m,q≤250000,0≤ai,bj≤2500001\le n,m,q\le 250000,0\le a_i,b_j\le 250000
1≤n,m,q≤250000,0≤ai,bj≤250000
题解
这显然有一个网络流做法，给 nnn 个广告商分别建一个点，源点向其连容量 aia_ia ...
省选联考 2021 A卷
2021 联合省选解题报告 A卷
D2T3 给咕了
卡牌游戏（card）
[省选联考 2021 A/B 卷] 卡牌游戏
nnn 张牌，第 iii 张牌正面为 aia_iai，反面为 bib_ibi，最多 mmm 次翻牌（使某张牌反面向上）。最小化朝上面数字的极差。
保证 2n2n2n 个数互不相同。m<n≤106,1≤ai,bi≤109m < n \le 10^6,1\le a_i,b_i\le 10^9m<n≤106,1≤ai,bi≤109
题解
考虑枚举答案（极差），我们把所有 ai,bia_i,b_iai,bi 丢在一起排序，如果确定了极差，我们枚举最小值，最大值可以用双指针维护，并且维护这段区间是否每个位置都有、翻牌次数是否超过限制。。
考虑枚举的极差越大，那双指针维护的区间会越宽，更易满足条件。具备单调性，二分即可。
复杂度 O(nlogn)O(n\log n)O(nlogn)
CODE
矩阵游戏（matrix）
[省选联考 2021 A 卷] 矩阵游戏
n×mn\times mn×m 的矩阵 ai,ja_{i,j}ai,j 满足 0≤ai ...
XJ - 数数题
92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685bec981c6c4e63d59ce40dd35f6f2babe32071cef15e81b1a3272ef19e860708a05b8d1c527161bb5cefa494b6ba01bad7d1be073497e14012e2902863541acedc92c2010142634baa1ceb6c7ae0a7059755bf2491e8ae4fb8d66fb8c7436595b45248cb9661890de0e215e834913d469821b383ccb0b5acd40827a9ff05841993cc4aa88d27598b4894a88e9716ed2e4774d59eb65f9811bd3c3438242e1432fd2d44100156fcb0a07fcce1f89cd422a29fef441078a9a692bb15a3596fdcc4c1879e9787751d775a79ad9e5013d17ae04f4d6e0c4e8e0fb097a ...
「CF932G」 Palindrome Partition
CF932G
PAM,回文自动机
题意
给定一个串 SSS（2≤∣S∣≤1062\le|S|\le 10^62≤∣S∣≤106），把串分为偶数段，假设分为了s1,s2,s3,…,sks_1,s_2,s_3,\dots,s_ks1,s2,s3,…,sk 求，满足s1=sk,s2=sk−1…s_1=s_k,s_2=s_{k-1}\dotss1=sk,s2=sk−1… 的方案数。
题解
记 n=∣S∣n=|S|n=∣S∣，设 dpidp_{i}dpi 表示搞定了 S[1:i]S[1:i]S[1:i] 的方案数，显然有：
dpi←∑j<idpj[S[j+1:i]=S[n−i+1:n−j]]dp_{i}\gets\sum_{j<i} dp_{j}\big[S[j+1:i]=S[n-i+1:n-j]\big]
dpi←j<i∑dpj[S[j+1:i]=S[n−i+1:n−j]]
然而这看着就不可做。
我们重新构造字符串 T=S1SnS2Sn−1…T=S_1S_nS_{2}S_{n-1}\dotsT=S1SnS2Sn−1…
考虑我们选了 S[i:j ...
XJ - vodka
92ce3867a25b048540c10275d83b5b1fdf7791515dce79b514403f8566cc218d0492235a5486ebd967a43c7ae3b394f064c10ffba361f9ee919751b3adcf08917e2ea516742890c4494c08b2b471e7080a8836160b5b6241d8a7cd71425656cb701cda3bfe941b44ecd4fb143055cff833496123289d495841f998505d2955819af6f5c5cbc5fd3c12e502156ace8192096c19a6746a292cf02dcd7e671ce52bb3e0ea1b8de81dfa373e535e4cd3cc0ba1b724e6eb7bf010aee41149800a48d1e67859fafdfc8ae166ca237de6105fd36b15283c11d7022a290dafe202d05c1b8d951f4de4f97653cdf9194f995977ac0a64a517a06c8c783 ...
PGF 概率生成函数
在 OGF 普通生成函数的基础上，把系数换成随机变量取到某值的概率，具体的：
F(x)=∑i=0∞P(X=i)xi{F}(x)=\sum_{i=0}^{\infty}P(X=i)x^i
F(x)=i=0∑∞P(X=i)xi
其中 XXX 表示随机变量，P(X=i)P(X=i)P(X=i) 表示随机变量取 iii 的概率。
显然有以下结论：
F(1)=1F(1)=1
F(1)=1
所有事件的概率和等于 111 ，没毛病。
E[X]=∑i=0∞iP(X=i)=F′(1)\mathbb{E}\left[X\right] =\sum_{i=0}^{\infty} iP(X=i)=F'(1)
E[X]=i=0∑∞iP(X=i)=F′(1)
离散期望 === 概率 ×\times× 数值，显然（F′(1)F'(1)F′(1) 展开就是了）。
E[Xk‾]=F(k)(1)\mathbb{E}\left[X^{\underline{k}}\right] =F^{(k)}(1)
E[Xk]=F(k)(1)
暴力展开易得，F(k)F^{(k)}F(k) 表 FFF 的 kkk ...
「CF891E」 Lust
CF891E Lust
生成函数,期望
题意
你有 nnn 个数 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an 要进行 kkk 次操作，每次随机选择一个数 x∈[1,n]x \in [1,n]x∈[1,n]，把 axa_xax 减一，并将答案增加除 axa_xax 外所有数的乘积。
求最终答案的期望，答案对 109+710^9 + 7109+7 取模。
1≤n≤5000, 1≤k≤109, 0≤ai≤1091\le n \le 5000,\;1\le k\le 10^9,\;0\le a_i\le 10^9
1≤n≤5000,1≤k≤109,0≤ai≤109
题解
可以发现，答案的增加量等于 ∏ai\prod a_i∏ai 的减少量。设最后得到的序列为 {bi}\left\{b_i\right\}{bi} ，那么答案为：
∏i=1nai−∏i=1n(ai−bi)\prod_{i=1}^{n} a_i - \prod_{i=1}^{n} (a_i-b_i)
i=1∏nai−i=1∏n(ai−bi)
右边，求期望值
E=1nk( ...