「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 - 数数题
fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca404691e5fc60ba7c499cfa1158c115698c3a347b07c4115adf430bd7591c0a434b27fb2fdea6d00cd143a1ecca9b3bea4cdc55410675a4e36883523cac9d3fb44f05cb5d769aa27444391c57e0baf41a06537621d7c451a660609bc493cf7b9549d34b16626363785066a66471a0f9b3d94d0179ec95e71a35923e7881ecb3f9c5d3f7826606be3b627ed0bd24bbb8e03c1e64ce3c876460712a947780489259933eb818a0b054e43bd21181989e75f1d3c158f1edd0c45c68fb0bbc972564181a5fbbff7540fadd3a5a5d5d71d81514030b9366461d0c69f47c ...
「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
fdbc2997623a61cf73a7235ddd7595319a534b1b88b448bf9454b515924b8b23ddb5c2472a1f018c70d2fe2396cf30a74267773b866d929552deae39cb5d9c406ddc505ec5bccea4053aa9ed90d0c68642eb1463878432b8b27a17c6d96e8783cee1b96d9c096f2b96539c36733aa8cc0c155f8ed119b8caf694426aacf0bb4bea8616fe88a3f71c144e054ffed1b9443e5c4a30bcc57207b74b882e0b5bff2fc77e28c310f5564d8d60dd05143ea211adf7c27a4cead7d427b9faa1b6706476d1537c33fc5461d1ec16eb61de56bae337d8463405b7021783e5fc659f18bc4c8fcd0854c4abd005d3592c19eb954cc57133fecc80ec3bf89 ...
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( ...
「CF708E」 Student’s Camp
CodeForces 708E
动态规划，dp优化
题意
给你一个 n+2n+2n+2，宽 mmm 的矩形，其中第 111 行和第 n+1n+1n+1 行是坚不可摧的。有 ttt 天，每天对于每行有 ppp 的概率消掉最左块，同样的也有 ppp 的概率消掉最右块。求 ttt 天后所有格子构成一个联通块的概率。
1≤n,m≤1500,0≤t≤1000001\le n,m\le 1500,0\le t\le 100000
1≤n,m≤1500,0≤t≤100000
题解
能消掉的只有 nnn 行 mmm 列，对于一行，在 ttt 天后留下 [l,r][l,r][l,r] 这段的概率为
(tl−1)pl−1(1−p)t−l+1×(tm−r)pm−r(1−p)t−m+r\binom{t}{l-1}p^{l-1} (1-p)^{t-l+1} \times \binom{t}{m-r} p^{m-r}(1-p)^{t-m+r}
(l−1t)pl−1(1−p)t−l+1×(m−rt)pm−r(1−p)t−m+r
记 Gl=(tl−1)pl−1(1−p)t−l+1,Hr=(tm−r)pm−r(1 ...