CF1864H
给定变量
x x x ，初始为
1 1 1 ，每次等概率随机进行以下两种操作之一：
x ← x + 1 , x ← x × 2 x \leftarrow x+1,x \leftarrow x \times 2 x ← x + 1 , x ← x × 2 。求期望多少次操作之后
x x x 会
≥ n \ge n ≥ n 。
令
n ← n − 1 n \leftarrow n-1 n ← n − 1 。
首先拆贡献，转化为对于
i ∈ [ 1 , n ] i \in [1,n] i ∈ [ 1 , n ] ，求
x x x 经过
i i i 的概率和。
可以发现
2 2 2 操作最多只有
log n \log n log n 次。考虑枚举
2 2 2 的操作次数
L L L ，则对于一个具体的
n ′ n' n ′ ，求
∑ i = 0 L c i 2 i = n ′ \sum \limits_{i=0}^L c_i2^i=n' i = 0 ∑ L c i 2 i = n ′ 的操作序列
c c c 的方案数（
c i c_i c i 为第
i i i 次
2 2 2 操作之前的
1 1 1 操作数量）。考虑到枚举
n ′ n' n ′ 实质上是枚举一个
Δ \Delta Δ ，使得
Δ + ∑ i = 0 L c i 2 i = n \Delta + \sum \limits_{i=0}^L c_i2^i = n Δ + i = 0 ∑ L c i 2 i = n 。
遇到值域巨大，物品数量贼小的一种方法就是数位 DP。具体地，当枚举到第
b b b 位时，对于每个权值为
2 i 2^i 2 i 的物品，枚举其的二进制第
b − i b-i b − i 位，以达成进位值极小的目的。进位的位数显然至多为
O ( L ) O(L) O ( L ) ，所以时间复杂度为
O ( T log 4 n ) O(T\log^4 n) O ( T log 4 n ) 。（转移
O ( log ) O(\log) O ( log ) ，枚举进位
O ( log n ) O(\log n) O ( log n ) ，枚举当前位
O ( log ) O(\log) O ( log ) ，枚举
L L L 为
O ( log n ) O(\log n) O ( log n ) ）。但是常数比较小。
观察转移方程：
p i = 1 2 ( [ i 为偶数 ] p i 2 + p i − 1 ) p_i = \frac{1}{2}([i 为偶数]p_{\frac{i}{2}}+p_{i-1}) p i = 2 1 ([ i 为偶数 ] p 2 i + p i − 1 ) ，发现
i i i 的转移涉及的项数极小，于是考虑矩阵快速幂。
首先尝试维护
p i p_i p i 与
p i 2 p_{\frac{i}{2}} p 2 i 两项，发现当
i + 1 i+1 i + 1 模
4 4 4 余
2 2 2 时，
p i + 1 p_{i+1} p i + 1 直接从
p i p_{i} p i 以及
p i + 1 2 p_{\frac{i+1}{2}} p 2 i + 1 转移，而
p i + 1 2 p_{\frac{i+1}{2}} p 2 i + 1 只是从
p i 2 p_{\frac{i}{2}} p 2 i 处继承，可以搞。但是如果
i + 1 i+1 i + 1 被
4 4 4 整除，那么还得涉及到
i 4 \frac{i}{4} 4 i ，由此就要涉及
log n \log n log n 项。于是可以预处理出当
i + 1 i+1 i + 1 的最低位的
0 0 0 的个数为
j j j 的转移矩阵
M j M_j M j 。令
v j v_j v j 为
j j j 的最低位
0 0 0 个数，考虑预处理
F j F_j F j 与
G j G_j G j ，为
∏ j = 1 2 j M v ( j ) \prod \limits_{j=1}^{2^{j}} M_{v(j)} j = 1 ∏ 2 j M v ( j ) 以及
∏ j = 1 2 j + 1 − 1 M v ( j ) \prod \limits_{j=1}^{2^{j+1}-1} M_{v(j)} j = 1 ∏ 2 j + 1 − 1 M v ( j ) ，则
F 0 = G 0 = M 1 F_0=G_0 = M_1 F 0 = G 0 = M 1 。
F i = G i − 1 M 2 i F_i=G_{i-1}M_{2^{i}} F i = G i − 1 M 2 i ，
G i = F i G i − 1 G_i=F_iG_{i-1} G i = F i G i − 1 。预处理时间复杂度
O ( log 4 ) O(\log^4) O ( log 4 ) 。每次询问时对
n n n 进行二进制分解，从高到底加入
F F F ，时间复杂度
O ( T log 3 n ) O(T\log^3 n) O ( T log 3 n ) 。
Gym102411D
定义一个字符串是好的当且仅当其本身是一个回文串或者其能够分割成两个回文串。对于一个
n n n 以及一个字符集大小
k k k ，求长度为
n n n 的好字符串个数。
首先一种直观的想法是对分割方式计数，显然会算重。回文统计问题算重时可以往循环节方面想。
定义：只有唯一的分割方案的串为本源字符串。
断言：如果一种好字符串能够有两种分割方式，那么其必然有唯一的能够表示成若干个本源字符串叠在一起的方式。
证明：存在性：事实上我们只需要证明一种非本源字符串有整周期即可。因为该周期如果不是本源字符串的话可以被继续划分至本源字符串。
记录
s i s_i s i 为
s [ 1 : i ] 。 s[1:i]。 s [ 1 : i ] 。 假设对于一个字符串
s s s ，有两种划分方案，分别在
p , q p,q p , q 分割开来，由于
s p s_p s p 与
s q s_q s q 均为回文串，而
s p s_p s p 与
s [ q − p + 1 : q ] s[q-p+1:q] s [ q − p + 1 : q ] 互为反转，所以
s [ 1 : p ] s[1:p] s [ 1 : p ] 为
s [ 1 : q ] s[1:q] s [ 1 : q ] 的一个
border \text{border} border 。所以
s [ p + 1 , q ] s[p+1,q] s [ p + 1 , q ] 为
s [ 1 , q ] s[1,q] s [ 1 , q ] 的一个周期。令
len = q − p \text{len}=q-p len = q − p ，令
r = q m o d len r=q \bmod \text{len} r = q mod len ，并令
S S S 为
s [ q − p + 1 , q ] s[q-p+1,q] s [ q − p + 1 , q ] 。由于
s r s_r s r 本身是
S S S 的一个后缀，所以其与
s [ q − r + 1 , q ] s[q-r+1,q] s [ q − r + 1 , q ] 相同。又由于
s q s_q s q 回文，所以
s r s_r s r 回文。
令
s q s_q s q 去掉前后
r r r 位的串为
T T T ，则
T T T 的前后
len − r \text{len}-r len − r 位均为
S S S 该长度的后缀，由于
T T T 回文，所以
S [ r + 1 , len ] S[r+1,\text{len}] S [ r + 1 , len ] 回文，所以
S S S 存在一种从
r r r 划分的方案。
令
r ′ r' r ′ 为
( ∣ s ∣ − p ) m o d len (|s|-p) \bmod \text{len} ( ∣ s ∣ − p ) mod len ，则同理可得将长度为
r ′ r' r ′ 的后缀划分开也是一种合法方案。
如果
r r r 与
r ′ r' r ′ 均为
0 0 0 ，显然
S S S 为
s s s 的一个周期。如果
r + r ′ = len r+r'=\text{len} r + r ′ = len ，则
s len s_{\text{len}} s len 为
S S S 的一个周期。否则可以继续递归。
唯一性：即证对于任意的本源字符串
p ≠ q p \neq q p = q ，其任意叠加形成的字符串不同。
当
∣ p ∣ = ∣ q ∣ |p|=|q| ∣ p ∣ = ∣ q ∣ 时显然。
反证法。不妨设
∣ p ∣ > ∣ q ∣ |p|>|q| ∣ p ∣ > ∣ q ∣ 。假设
p , q p,q p , q 均是
T T T 的一个整周期，则
∣ T ∣ ≥ 2 max ( ∣ p ∣ , ∣ q ∣ ) |T| \ge 2\max(|p|,|q|) ∣ T ∣ ≥ 2 max ( ∣ p ∣ , ∣ q ∣ ) ，由弱周期引理得，
g = gcd ( ∣ p ∣ , ∣ q ∣ ) g = \gcd(|p|,|q|) g = g cd( ∣ p ∣ , ∣ q ∣ ) 为
∣ T ∣ |T| ∣ T ∣ 的一个周期长度，即为
q q q 的一个周期长度。由于
∣ p ∣ > ∣ q ∣ |p|>|q| ∣ p ∣ > ∣ q ∣ ，所以
∣ q ∣ ≥ 3 g |q| \ge 3g ∣ q ∣ ≥ 3 g 。所以如果
q g q_g q g 回文，那么
∣ q ∣ |q| ∣ q ∣ 在
g g g 以及
2 g 2g 2 g 处均有划分方案，与
p , q p,q p , q 均为本源字符串矛盾。考察
q q q 的唯一分配点
p o s pos p os 。如果
p o s pos p os 正好把
q q q 分成两半，则
q g q_g q g 回文。
否则
q g q_g q g 可以表示成
S T ST ST 的形式，其中
S , T S,T S , T 均为回文串。对于任意的
p o s + k g pos+kg p os + k g ，其前缀均为
S T S T … S STST\dots S STST … S ，后缀均为
T S T S T … T TSTST \dots T TSTST … T ，显然回文。
事实上，还有一个结论：
s s s 本身回文。你交替去除长度为
r r r 的前后缀与长度为
r ′ r' r ′ 的前后缀最终要么得到原串中长度
r r r 的前缀，要么得到长度为
r ′ r' r ′ 的后缀。由于
r r r 前缀与
r ′ r' r ′ 后缀均回文，所以整个过程都是回文的。
从这里我们可以得出，如果
s s s 为非本源字符串，则假设其唯一本源周期为
g g g ，则划分方案只有
s g \frac{s}{g} g s 种：各个空隙与边界。
由此，我们就可以求出
f i f_i f i 为长度为
i i i 的本源回文串的方案数了。令
F i F_i F i 为划分方案数总和，则
f i = F i − ∑ j ∣ i , j < i i j f i f_i = F_i-\sum \limits_{j|i,j<i} \frac{i}{j}f_i f i = F i − j ∣ i , j < i ∑ j i f i 。然后就可以求
ans = ∑ i ∣ n f i \text{ans}= \sum \limits_{i|n} f_i ans = i ∣ n ∑ f i 了。
时间复杂度
O ( d ( n ) 2 ) O(d(n)^2) O ( d ( n ) 2 ) 。
Be careful
有一棵树，叶子的权值你需要自己赋，非叶子节点的权值为所有儿子权值的
mex \text{mex} mex 。问对于
k ∈ [ 0 , n ] k \in [0,n] k ∈ [ 0 , n ] ，有多少种赋权方案使得根节点权值为
k k k 。
超级天赋哥做法。
令
d p i , j dp_{i,j} d p i , j 为
i i i 号点权值为
j j j 的方案数。
显然有这么一件事情：
d e g deg d e g 过大的点数量有限，
d e g deg d e g 过小的点的权值有限。
所以在对当前节点
u u u 求的时候，考虑处理一个阈值
B B B ，满足
B + ∣ { i ∣ i ∈ son u , d e g i > B } ∣ B+|\{i|i \in \text{son}_u,deg_i>B\}| B + ∣ { i ∣ i ∈ son u , d e g i > B } ∣ 最小。称
d e g i ≤ B deg_i \le B d e g i ≤ B 的点为小点，其余类型的点为大点（不考虑叶子）。令
C = ∣ { i ∣ i ∈ son u , d e g i > B } ∣ C=|\{i|i \in \text{son}_u,deg_i>B\}| C = ∣ { i ∣ i ∈ son u , d e g i > B } ∣ 。
考虑直接求
f S f_{S} f S 为枚举到第
i i i 个小点，
[ 1 , B + C ] [1,B+C] [ 1 , B + C ] 中已经被取到的数的集合为
S S S 的方案数。转移即为枚举下一个儿子取什么数。时间复杂度
2 B + C B 2^{B+C}B 2 B + C B 。
如何处理叶子的贡献？直接拆贡献，算
mex ≥ \text{mex} \ge mex ≥ 指定值的方案数。具体地，令枚举值为
x x x ，则把先前的集合
S S S 中
x x x 及以下的部分填满的方案数仅与
S S S 在
x x x 及以下填了多少数有关。于是可以维护一个数组
a i a_i a i ，表示在
x x x 及以下填了
i i i 个数的
f S f_S f S 的总和。假如一个集合
S S S 在第
i i i 位迎来第
j j j 个
1 1 1 ，那么就可以让
x x x 在扫描线扫到
i i i 的时候
a j − 1 ← a j − 1 − f S a_{j-1} \leftarrow a_{j-1}-f_S a j − 1 ← a j − 1 − f S ，
a j ← a j + f S a_j \leftarrow a_j+f_S a j ← a j + f S 。这个可以记录
Δ i , j \Delta_{i,j} Δ i , j 为
x x x 扫到
i i i 时
j j j 的变化量。时间复杂度
O ( ( B + C ) 2 B + C + poly ( n ) ) O((B+C)2^{B+C}+\text{poly}(n)) O (( B + C ) 2 B + C + poly ( n )) 。
还可以优化！你可以直接动态维护
g i , S g_{i,S} g i , S 为当扫描线扫到
x x x ，
x x x 及以下选择了
i i i 个，以上已经选择了
S S S 这个集合的方案数。时间复杂度
∑ i = 0 B + C 2 i ( B + C − i ) \sum \limits_{i=0}^{B+C}2^i(B+C-i) i = 0 ∑ B + C 2 i ( B + C − i ) ，大概在
2 B + C + 1 2^{B+C+1} 2 B + C + 1 级别。
时间复杂度
O ( ∑ ( 2 B + C B + poly ( n ) ) ) O(\sum(2^{B+C}B+\text{poly}(n))) O ( ∑ ( 2 B + C B + poly ( n ))) 。经过一些神人的复杂度分析是
O ( 2 2 n ) O(2^{\sqrt {2n}}) O ( 2 2 n ) 的。
AT_xmascon22_f
给定一张图，其中
i i i 号点与
j j j 号点有
a i , j a_{i,j} a i , j 条边，对于
k ∈ [ 0 , n 2 ] k \in [0,\frac{n}{2}] k ∈ [ 0 , 2 n ] ，求大小为
k k k 的匹配有多少种。
令
k = n 2 k=\frac{n}{2} k = 2 n 。
对于 i ∈ [ 1 , k ] i \in [1,k] i ∈ [ 1 , k ] ( 2 i − 1 , 2 i ) (2i-1,2i) ( 2 i − 1 , 2 i ) 。此时对于任意一个匹配，其与新边构成的集合一定只有环与链。可以考虑分别求出
f S , g S f_{S},g_{S} f S , g S 表示
S S S 构成一个环的方案数。
当求链的时候，可以设
d p S , i dp_{S,i} d p S , i 为有哪些点
j j j ，满足
2 j + 1 , 2 j + 2 2j+1,2j+2 2 j + 1 , 2 j + 2 中的某个点已经在链内的集合
S S S ，并且当前链的一段为
i i i 节点的方案数。转移时直接枚举下一个节点即可。时间复杂度
O ( 2 k k 2 ) O(2^kk^2) O ( 2 k k 2 ) 。统计的时候要除以
2 2 2 。
当求环的时候，考虑钦定从最大的点开始枚举，则转移过程中其余所有的点都应该小于集合中最大的点。即设状态
d p S , i dp_{S,i} d p S , i 为
S S S 在环内，
i i i 为端点的方案数。在某个状态统计完毕后，可以直接令
i i i 连向
S S S 最大点累加答案。时间复杂度
O ( 2 k k 2 ) O(2^kk^2) O ( 2 k k 2 ) 。顺时针逆时针各会计算一次，除以
2 2 2 即可。
由于边数只与链的个数有关，所以需要对于每一个
i ∈ [ 1 , n 2 ] i \in [1,\frac{n}{2}] i ∈ [ 1 , 2 n ] ，需要求出
f i i ! , g i i ! \frac{f^i}{i!},\frac{g^i}{i!} i ! f i , i ! g i 。每次卷积是
O ( 2 k k 2 ) O(2^kk^2) O ( 2 k k 2 ) 的，卷积
k k k 次就是
O ( 2 k k 3 ) O(2^kk^3) O ( 2 k k 3 ) 的。每次再乘起来就是
O ( 2 k k 2 ) O(2^kk^2) O ( 2 k k 2 ) 的。总时间复杂度
O ( 2 k k 3 ) O(2^kk^3) O ( 2 k k 3 ) 。
P9563
在一个
n × n n \times n n × n 的矩形内有
m m m 个禁止点，问有多少个正方形一个禁止点都不覆盖。
n ≤ 10 9 , m ≤ 5000 n \le 10^9,m \le 5000 n ≤ 1 0 9 , m ≤ 5000 。
显然有一个
O ( 2 m ) O(2^m) O ( 2 m ) 的暴力：考虑枚举禁止点集合
S S S 作容斥，容斥系数为
2 ∣ S ∣ 2^{|S|} 2 ∣ S ∣ 。
结论：对于一个禁止点集合
∣ S ∣ |S| ∣ S ∣ ，如果点集合所构成的矩形内部有点，那么这个禁止点集合
S S S 无用。
证明：不删内部任意点的系数为
( − 1 ) ∣ S ∣ (-1)^{|S|} ( − 1 ) ∣ S ∣ ，删了的贡献为
( − 1 ) ∣ S ∣ − 1 (-1)^{|S|-1} ( − 1 ) ∣ S ∣ − 1 ，加起来正好为
0 0 0 。
于是只需找到合法的禁止点集合即可。
首先随机扰动使得所有点横纵坐标不等。
具体地，首先枚举点
p , q p,q p , q ，满足
x p < x q x_p<x_q x p < x q ，并且以
p , q p,q p , q 为对角线内的矩形内没有其它点。这意味着
p , q p,q p , q 定死了
x x x 的限制。不妨设
y p > y q y_p>y_q y p > y q ，则上界既可以取
y p y_p y p ，也可以取
p p p 上面的
x ∈ [ x p , x q ] x \in [x_p,x_q] x ∈ [ x p , x q ] 的一个前驱，并且要求在这范围的只有一个与前驱等高的点。下界同理。否则构成的矩形将会有内部点。
特别地，还须注意只有一个点的情况。
这样矩形数量就压到了
O ( k 2 ) O(k^2) O ( k 2 ) 了。每个矩形的贡献是容易计算的。
QOJ9254
有一个长度为
n n n ，值域为
[ 1 , m ] [1,m] [ 1 , m ] 的随机序列，问众数的期望出现次数。
首先直接枚举众数的期望次数肯定死完了，考虑拆贡献拆成
m n n − ∑ i = 2 n + 1 c n t i m^nn-\sum \limits_{i=2}^{n+1} cnt_i m n n − i = 2 ∑ n + 1 c n t i 。其中
c n t i cnt_i c n t i 为众数出现次数
< i <i < i 的序列个数。
令阈值为
k k k 。
魔怔做法：
考虑直接枚举
i i i ，则每种数出现次数至多为
i i i 的方案数则为：
[ x n n ! ] ( ∑ j = 0 k 1 j ! x j ) m [\frac{x^n}{n!}](\sum \limits_{j=0}^{k} \frac{1}{j!}x^j)^m [ n ! x n ] ( j = 0 ∑ k j ! 1 x j ) m 直接多项式快速幂即可。时间复杂度
O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) 。
常规做法：
令
f i , j f_{i,j} f i , j 为考虑到第
i i i 个位置，可以填写
1 1 1 到
j j j 的方案数。
首先随便选，有
f i , j ← j f i − 1 , j f_{i,j} \leftarrow jf_{i-1,j} f i , j ← j f i − 1 , j 。
其次减去不合法的方案数，此时新加的数次数一定为
k + 1 k+1 k + 1 。即
f i , j ← f i , j − j ( i − 1 k ) f i − 1 − k , j − 1 f_{i,j} \leftarrow f_{i,j} - j\binom{i-1}{k}f_{i-1-k,j-1} f i , j ← f i , j − j ( k i − 1 ) f i − 1 − k , j − 1 。
然后，你不必使用
f n , m f_{n,m} f n , m 直接作为答案。观察到你只要钦定有
i i i 种数出现次数
= k + 1 = k+1 = k + 1 ，你就可以容斥解决了。在此基础上，
j j j 每减少
1 1 1 ，
i i i 就减少
k + 1 k+1 k + 1 。所以
m − j ≤ n k + 1 m-j \le \frac{n}{k+1} m − j ≤ k + 1 n 。实现上，你只需要保留
i + ( k + 1 ) ( m − j ) ≤ n i+(k+1)(m-j) \le n i + ( k + 1 ) ( m − j ) ≤ n 的状态即可。
时间复杂度
O ( n 2 ln n ) O(n^2 \ln n) O ( n 2 ln n ) 。