我咋啥都不会。
P1117 优秀的拆分 \color{red}\text{P1117 优秀的拆分} P1117 优秀的拆分 Problem 多测，每次给定
s s s ，求
s s s 的所有子串的所有拆分中，有多少个是
AABB \operatorname{AABB} AABB 的形式。
T ≤ 10 T \le 10 T ≤ 10 ，
n ≤ 3 × 10 4 n \le 3\times 10^4 n ≤ 3 × 1 0 4 1.5 s , 512 M B 1.5s, 512MB 1.5 s , 512 MB Sol n 2 n^2 n 2 是简单的，记
f i f_i f i 表示以
i i i 结尾的
AA \operatorname{AA} AA 串，
g i g_i g i 表示以
i i i 开头的
AA \operatorname{AA} AA 串即可。然后是一个快速统计这种复制串的经典技巧：枚举
l l l ，每隔
l l l 设置一个断点，这样的话一个长为
2 l 2l 2 l 的串一定穿过两个断点。只需要知道相邻断点的
LCP&LCS \operatorname{LCP \& LCS} LCP&LCS ，然后就是区间覆盖，差分即可。复杂度是调和级数的。
ABAB \operatorname{ABAB} ABAB 的形式比较好通过
LCP&LCS \operatorname{LCP \& LCS} LCP&LCS 统计？
扩展：求区间复制串数
P1186 玛丽卡 \color{green}\text{P1186 玛丽卡} P1186 玛丽卡 Problem 求删边最短路。
n ≤ 1000 n \le 1000 n ≤ 1000 ，
1 ≤ m ≤ n ( n + 1 ) 2 1\le m \le \frac{n(n+1)}{2} 1 ≤ m ≤ 2 n ( n + 1 ) 1 s , 128 M B 1s, 128MB 1 s , 128 MB Sol 先跑出一棵最短路树。然后只考虑
1 ⇝ n 1 \leadsto n 1 ⇝ n 的路径。对于不包含在这上面的边
( u , v ) (u, v) ( u , v ) ，求出
1 ⇝ u 1 \leadsto u 1 ⇝ u ，
v ⇝ n v \leadsto n v ⇝ n 在
1 ⇝ n 1 \leadsto n 1 ⇝ n 这条路径上第一个离开/进入的点，记为
l , r l, r l , r ，然后对
[ l , r ] [l, r] [ l , r ] 内的点
chkmax \operatorname{chkmax} chkmax 即可。
Q：可能有多条
1 ⇝ u 1 \leadsto u 1 ⇝ u 的最短路，选择的
l l l 是否会有问题？
A：不会。对于两个离开点
i , j i, j i , j ，找到
i ⇝ u i \leadsto u i ⇝ u 的第一条边，我们对这条边算贡献的时候，就可以算对了。对于进入点同理。
P1852 跳跳棋 \color{green}\text{P1852 跳跳棋} P1852 跳跳棋 Problem 给定
a , b , c , x , y , z a, b, c, x, y, z a , b , c , x , y , z 。分别表示三颗珠子的初始位置和目标位置（珠子间相同）。每次可以遵循跳棋的规则进行一次操作。问是否可以达到，并求出最少步数。
1 s , 125 M B 1s, 125MB 1 s , 125 MB Sol 先判断是否合法，由于操作是可逆的，可以直接求出终态（
2 y = x + z 2y=x+z 2 y = x + z ）判断是否相等。
找最少步数我们难以找到一个类似于拐弯的地方。但是我们发现一个状态想要缩小的话只有一步，这是一个类似于树的结构，然后需要找的是 LCA。二分即可。时间复杂度是两个
log \log log 。
P2135 方块消除 \color{red}\text{P2135 方块消除} P2135 方块消除 Problem 给定
n n n 个相邻的区域，每个区域有长度
l i l_i l i 和颜色。对相同颜色的长为
l l l 一段消除的代价为
l 2 l^2 l 2 ，求最大代价。
n ≤ 50 , l i ≤ 20 n \le 50, l_i \le 20 n ≤ 50 , l i ≤ 20 1 s , 512 M B 1s, 512MB 1 s , 512 MB Sol 考虑区间 DP。
但是发现对于
111100001111 这种情况是难以处理的，因为正解应该是先消
0 0 0 再一起消
1 1 1 。但是无法记录当前区间剩余段的长度&颜色（时空难以接受）。考虑简单的变一下，变为
f l , r , k f_{l, r, k} f l , r , k 表示消除了
[ l , r + k ] [l, r + k] [ l , r + k ] （
r ∼ r + k r\sim r+k r ∼ r + k 这一段同色）这一段的最大代价。
转移则直接扩展
k k k 或枚举断点（因为这样的话要消一定要）即可。
P3286 [SCOI2014] 方伯伯的商场之旅 \color{blue}\text{P3286 [SCOI2014] 方伯伯的商场之旅} P3286 [SCOI2014] 方伯伯的商场之旅 Problem 对于一个
n n n 堆石子
p 1.. n p_{1..n} p 1.. n ，每次可以移动一堆石子到另一堆石子上，代价为距离乘石子数，令
p p p 的代价为其移成一堆的最小代价。
定义一个
p ( x ) p(x) p ( x ) 表示
x x x 在
K K K 进制下每一位构成的序列。对
L ≤ x ≤ R L \le x \le R L ≤ x ≤ R ，求出
p ( x ) p(x) p ( x ) 的代价和。
L ≤ R ≤ 10 15 L \le R \le 10^{15} L ≤ R ≤ 1 0 15 ，
2 ≤ K ≤ 20 2 \le K \le 20 2 ≤ K ≤ 20 1 s , 125 M B 1s, 125MB 1 s , 125 MB Sol 最小代价是都移到中位数的位置。暴力的想法是枚举中位数的位置，但是这样会很麻烦，因为会有两个限制（
L + x > R L + x > R L + x > R ，
R + x > L R + x > L R + x > L ），并且可能会有两个位置都有中位数。考虑一下这个东西的本质，就是类似于左右移导数均小于
0 0 0 ，由于和在 DP 的过程中是可计算的，因此可以直接使用这个东西来进行调整：先都移到
1 1 1 ，然后再枚举
1 → 2 1\to 2 1 → 2 ，
2 → 3 2\to 3 2 → 3 等过程中减小的代价。
P3327 [SDOI2015] 约数个数和 \color{green}\text{P3327 [SDOI2015] 约数个数和} P3327 [SDOI2015] 约数个数和 Problem 求
∑ i ≤ n ∑ j ≤ m d ( i j ) \sum_{i\le n} \sum_{j \le m} d(ij) ∑ i ≤ n ∑ j ≤ m d ( ij ) 。
n , m ≤ 10 5 n, m \le 10^5 n , m ≤ 1 0 5 1 s , 125 M B 1s, 125MB 1 s , 125 MB Sol 知道
d ( i j ) = ∑ x ∣ i , y ∣ j [ x ⊥ y ] d(ij) = \sum_{x|i, y|j} [x \perp y] d ( ij ) = ∑ x ∣ i , y ∣ j [ x ⊥ y ] 即可。证明这玩意可以直接把
i , j , i j i,j,ij i , j , ij 质因数分解后考虑。
P3586 [POI 2015 R2] 物流 Logistics \color{blue}\text{P3586 [POI 2015 R2] 物流 Logistics} P3586 [POI 2015 R2] 物流 Logistics Problem 给定数组
a a a ，每次单点修改。或给定
c , s c, s c , s ，每次选出
c c c 个正数减一，问能否操作
s s s 次。询问的修改不会对序列造成真正的修改。
Sol 有一个比较简单的贪心，就是每次选择最大的
c c c 个，但是这样并不好维护。考虑把
a i a_i a i 填到次数里面去。由于
a i ≥ s a_i \ge s a i ≥ s 的时候只能填
s s s 次，先把这些数扔出去。把每一次选出的集合列成一行。则填入
a i a_i a i 的时候是从上到下扔进没有满的集合。然后你发现这个东西只需要判定，因此我可以直接把没有填满的列接着填而不是从上到下填（因为这时候一定不会产生重复）。于是只需要维护
a i < s a_i < s a i < s 的
∑ a i \sum a_i ∑ a i 与
a i ≥ s a_i \ge s a i ≥ s 的
i i i 的数量。可以使用 BIT 维护。
P11368 [Ynoi2024] After god \color{blue}\text{P11368 [Ynoi2024] After god} P11368 [Ynoi2024] After god Problem 有两个初始为
0 0 0 的序列
a 1.. n a_{1..n} a 1.. n ，
b 1.. n b_{1..n} b 1.. n ，每次修改给定
x , y x, y x , y ，表示
a x ← y a_x \gets y a x ← y ，然后对
i = 1 , … , n i = 1, \dots , n i = 1 , … , n 将
b i b_i b i 加上
max j ≤ i a j \max_{j \le i} a_j max j ≤ i a j ，然后查询
∑ i ≤ x b i \sum_{i \le x} b_i ∑ i ≤ x b i 。
n , m ≤ 10 6 n,m \le 10^6 n , m ≤ 1 0 6 ，
1 ≤ x , y ≤ n 1\le x,y \le n 1 ≤ x , y ≤ n 2.5 s , 512 M B 2.5s, 512MB 2.5 s , 512 MB Sol 你想对这个东西直接上历史和，但是失败了，因为
chkmax \operatorname{chkmax} chkmax 操作没法子拆。使用单侧递归的技巧是
2 log 2\log 2 log 的。想想这玩意求的实际上是什么：把
max a \max a max a 按时间从上到下拆开变为
c 1.. t , 1.. n c_{1..t, 1..n} c 1.. t , 1.. n 。然后求和是
∑ i ≤ x , j ≤ t c j , i \sum_{i \le x, j \le t} c_{j, i} ∑ i ≤ x , j ≤ t c j , i ，即矩形和。区间改值是一个上下左有边界的矩形
chkmax \operatorname{chkmax} chkmax ，我们直接历史和失败的原因是因为上下界均有限制并且没法差分。考虑换成从左到右扫描线（即
交换求和顺序 ），于是就可以直接维护历史和做到线对了。
CF1342F Make It Ascending \color{green}\text{CF1342F Make It Ascending} CF1342F Make It Ascending Problem 给定长为
n n n 的序列
a a a ，每次可以把一个数合并到另一个数上，要求合并完后的序列单调递增，求出最小操作次数即方案。多测。
n = 15 n = 15 n = 15 不超过
1 1 1 个，
n ≥ 14 n \ge 14 n ≥ 14 不超过
3 3 3 个，
n ≥ 13 n \ge 13 n ≥ 13 不超过
10 10 10 个，
n ≥ 12 n \ge 12 n ≥ 12 不超过
25 25 25 个。
7 s , 500 M B 7s, 500MB 7 s , 500 MB Sol 直接的不是很好做，因为可能涉及到插入。直接对最后的序列 DP（按合并的位置的顺序），由于值域是很大的，因此把答案扔进状态：
f i , j , S f_{i, j, S} f i , j , S 表示当前用了
i i i 个集合，第
i i i 个集合合并的位置在
j j j ，用了
S S S 中的数的情况下最后一个子集的和的最小值。转移枚举超集，新的
j ′ j' j ′ 一定是
S S S 中合法的里面最小的。时间复杂度是
O ( n 2 3 n ) O(n^23^n) O ( n 2 3 n ) 。
trick：定义域和值域的交换。
P1251 餐巾计划问题 \color{green}\text{P1251 餐巾计划问题} P1251 餐巾计划问题 Problem 总共
n n n 天，第
i i i 天需要
r i r_i r i 块餐巾。餐巾可以购买，或将用完的餐巾快洗或慢洗。三项操作每个餐巾分别花钱：
p 1 , p 2 , p 3 p_1,p_2,p_3 p 1 , p 2 , p 3 （递减的非负整数），三项操作花费时间
0 , t 2 , t 3 0,t_2,t_3 0 , t 2 , t 3 （递增）天。用完的餐巾可以延期送洗，问满足每天要求的最小费用。
n ≤ 2000 , 1 ≤ r i ≤ 10 7 , 1 ≤ p 1 , p 2 , p 3 ≤ 10 4 n\le 2000, 1 \le r_i \le 10^7, 1\le p_1, p_2, p_3 \le 10^4 n ≤ 2000 , 1 ≤ r i ≤ 1 0 7 , 1 ≤ p 1 , p 2 , p 3 ≤ 1 0 4 4 s , 125 M B 4s, 125MB 4 s , 125 MB Sol 对每天拆点为
( i 0 , i 1 ) (i_0, i_1) ( i 0 , i 1 ) 。令
( u , v , [ l , r ] , p ) (u, v, [l, r], p) ( u , v , [ l , r ] , p ) 表示
u u u 连向
v v v ，流量在
[ l , r ] [l, r] [ l , r ] 之间，费用为
c c c 。
连边：
对于
i ∈ [ 1 , n ] i \in [1, n] i ∈ [ 1 , n ] ，连边
( i 0 , i 1 , [ r i , r i ] , 0 ) (i_0, i_1, [r_i, r_i], 0) ( i 0 , i 1 , [ r i , r i ] , 0 ) ，
( i 0 , ( i + 1 ) 0 , [ 0 , + ∞ ) , 0 ) (i_0, (i+1)_0, [0, +\infin), 0) ( i 0 , ( i + 1 ) 0 , [ 0 , + ∞ ) , 0 ) ，
( 0 , i 0 , [ 0 , + ∞ ) , p 1 ) (0, i_0, [0, +\infin), p_1) ( 0 , i 0 , [ 0 , + ∞ ) , p 1 ) ，
( i 1 , ( i + t 2 ) 0 , [ 0 , + ∞ ) , p 2 ) (i_1, (i+t_2)_0, [0, +\infin), p_2) ( i 1 , ( i + t 2 ) 0 , [ 0 , + ∞ ) , p 2 ) ，
( i 1 , ( i + t 3 ) 0 , [ 0 , + ∞ ) , p 3 ) (i_1, (i+t_3)_0, [0, +\infin), p_3) ( i 1 , ( i + t 3 ) 0 , [ 0 , + ∞ ) , p 3 ) ，
( i 1 , 0 , [ 0 , + ∞ ) , 0 ) (i_1, 0, [0, +\infin), 0) ( i 1 , 0 , [ 0 , + ∞ ) , 0 ) 。
然后求上下界无源汇最小费用可行流。
P1361 小M的作物 \color{green}\text{P1361 小M的作物} P1361 小 M 的作物 Problem 小 M 现在有
n n n 种作物，第
i i i 种作物种植在
A A A 中种植可以获得
a i a_i a i 的收益，在
B B B 中种植可以获得
b i b_i b i 的收益，小 M 还找到了规则中共有
m m m 种作物组合，第
i i i 个组合中的作物共同种在
A A A 中可以获得
c 1 , i c_{1,i} c 1 , i 的额外收益，共同种在
B B B 中可以获得
c 2 , i c_{2,i} c 2 , i 的额外收益。
求最大种植收益。
2 ≤ n ≤ 10 3 , 1 ≤ m ≤ 10 3 2 \le n \le 10^3, 1 \le m \le 10^3 2 ≤ n ≤ 1 0 3 , 1 ≤ m ≤ 1 0 3 2 s , 250 M B 2s, 250MB 2 s , 250 MB Sol 二者选其一，考虑最小割建模。
对于
i ∈ [ 1 , n ] i\in[1, n] i ∈ [ 1 , n ] ，连边
( s , i , a i ) , ( i , t , b i ) (s, i, a_i), (i, t, b_i) ( s , i , a i ) , ( i , t , b i ) 。
对于第
j j j 个作物集合
S j S_{j} S j ，连边
( j A , t , c 2 , j ) , ( s , j B , c 1 , j ) (j_A, t, c_{2, j}), (s, j_B, c_{1, j}) ( j A , t , c 2 , j ) , ( s , j B , c 1 , j ) 。对
i ∈ S j i \in S_j i ∈ S j ，连边
( i , j A , + ∞ ) , ( i , j B , + ∞ ) (i, j_A, +\infin),(i, j_B, +\infin) ( i , j A , + ∞ ) , ( i , j B , + ∞ ) 。
答案为
( ∑ a i + b i ) + ( ∑ c 1 , i + c 2 , i ) − mincut (\sum a_i+b_i) + (\sum c_{1, i}+c_{2, i}) - \operatorname{mincut} ( ∑ a i + b i ) + ( ∑ c 1 , i + c 2 , i ) − mincut 。
P3978 [TJOI2015] 概率论 \color{blue}\text{P3978 [TJOI2015] 概率论} P3978 [TJOI2015] 概率论 Problem 求
n n n 个点的有根二叉树的叶子节点数的期望（两两不同）。
Sol 先考虑 DP。令
f i f_i f i 表示
i i i 个点的不同构二叉树个数，
g i g_i g i 表示其叶子的个数和。则
f i g i \frac{f_i}{g_i} g i f i 即为所求，有：
f i = ∑ j = 0 i − 1 f j f i − j − 1 f_i = \sum_{j = 0}^{i-1}f_jf_{i-j-1} f i = j = 0 ∑ i − 1 f j f i − j − 1 g i = 2 ∑ j = 0 i − 1 f j g i − j − 1 g_i = 2\sum_{j=0}^{i-1}f_jg_{i-j-1} g i = 2 j = 0 ∑ i − 1 f j g i − j − 1 初值：
f 0 = 1 f_0=1 f 0 = 1 ，
g 0 = 0 , g 1 = 1 g_0=0, g_1 = 1 g 0 = 0 , g 1 = 1 。
感觉这个很有一个卷积的形式，我们使用生成函数求出这两个的通项。
卡特兰数（即
f f f ）的生成函数
C ( x ) = ∑ n ≥ 0 C n x n C(x) = \sum_{n \ge 0} C_nx^n C ( x ) = ∑ n ≥ 0 C n x n 。拆开，有：
∑ n ≥ 0 C n x n = 1 + ∑ n > 0 ∑ i = 0 n − 1 C i C n − i − 1 x n \sum_{n \ge 0} C_nx^n = 1+\sum_{n > 0} \sum_{i=0}^{n-1}C_iC_{n-i-1}x^n n ≥ 0 ∑ C n x n = 1 + n > 0 ∑ i = 0 ∑ n − 1 C i C n − i − 1 x n = 1 + x ∑ n > 0 ∑ i = 0 n − 1 C i x i C n − i − 1 x n − i − 1 = 1+x\sum_{n > 0} \sum_{i=0}^{n-1}C_ix^iC_{n-i-1}x^{n-i-1} = 1 + x n > 0 ∑ i = 0 ∑ n − 1 C i x i C n − i − 1 x n − i − 1 = 1 + x ∑ i ≥ 0 C i x i ∑ j ≥ 0 C j x j = 1+x\sum_{i\ge0}C_ix^i\sum_{j\ge0}C_jx^j = 1 + x i ≥ 0 ∑ C i x i j ≥ 0 ∑ C j x j = 1 + x C 2 ( x ) = 1+xC^2(x) = 1 + x C 2 ( x ) 解得：
C ( x ) = 1 ± 1 − 4 x 2 x = 2 1 ∓ 1 − 4 x C(x) = \frac{1 \pm \sqrt{1-4x}}{2x} = \frac{2}{1\mp\sqrt{1-4x}} C ( x ) = 2 x 1 ± 1 − 4 x = 1 ∓ 1 − 4 x 2 。
带入 C 0 = 1 C_0=1 C 0 = 1 1 − 1 − 4 x 2 x \frac{1-\sqrt{1-4x}}{2x} 2 x 1 − 1 − 4 x 。
使用牛顿二项式定理拆开
1 − 4 x \sqrt{1-4x} 1 − 4 x ：
( 1 − 4 x ) 1 2 = ∑ n ≥ 0 ( 1 2 n ) ( − 4 x ) n (1-4x)^{\frac12} = \sum_{n \ge 0} \binom{\frac12}n(-4x)^n ( 1 − 4 x ) 2 1 = n ≥ 0 ∑ ( n 2 1 ) ( − 4 x ) n 然后把组合数拆成下降幂后再展开：
= ∑ n ≥ 0 ( − 1 ) n − 1 ( 2 n − 3 ) ! ! n ! 2 n ( − 4 x ) n =\sum_{n \ge 0} \frac{(-1)^{n-1}(2n-3)!!}{n!2^n}(-4x)^n = n ≥ 0 ∑ n ! 2 n ( − 1 ) n − 1 ( 2 n − 3 )!! ( − 4 x ) n = ∑ n ≥ 0 − 2 ( 2 n − 2 ) ! ( n − 1 ) ! n ! x n =\sum_{n \ge 0} -2\frac{(2n-2)!}{(n-1)!n!}x^n = n ≥ 0 ∑ − 2 ( n − 1 )! n ! ( 2 n − 2 )! x n C ( x ) = 1 + ∑ n ≥ 0 ( 2 n − 2 ) ! ( n − 1 ) ! n ! x n x C(x) = \frac{1+\sum_{n \ge 0} \frac{(2n-2)!}{(n-1)!n!}x^{n}}x C ( x ) = x 1 + ∑ n ≥ 0 ( n − 1 )! n ! ( 2 n − 2 )! x n 常数项消了，得到。
C ( x ) = ∑ n ≥ 0 ( 2 n ) ! n ! ( n + 1 ) ! x n C(x) = \sum_{n \ge 0} \frac{(2n)!}{n!(n+1)!}x^{n} C ( x ) = n ≥ 0 ∑ n ! ( n + 1 )! ( 2 n )! x n 我们推导
G ( x ) = ∑ n ≥ 0 g n x n G(x) = \sum_{n \ge 0} g_nx^n G ( x ) = ∑ n ≥ 0 g n x n 。带入转移式：
g i = 2 ∑ j = 0 i − 1 f j g i − j − 1 g_i = 2\sum_{j=0}^{i-1}f_jg_{i-j-1} g i = 2 ∑ j = 0 i − 1 f j g i − j − 1 。
G ( x ) = x + 2 ∑ n ≥ 2 ∑ i = 0 n − 1 f i g n − i − 1 x n G(x) = x+2\sum_{n\ge 2}\sum_{i=0}^{n-1}f_ig_{n-i-1}x^n G ( x ) = x + 2 n ≥ 2 ∑ i = 0 ∑ n − 1 f i g n − i − 1 x n = x + 2 x ∑ n ≥ 2 ∑ i = 0 n − 1 f i x i g n − i − 1 x n − i − 1 = x+2x\sum_{n\ge 2}\sum_{i=0}^{n-1}f_ix^ig_{n-i-1}x^{n-i-1} = x + 2 x n ≥ 2 ∑ i = 0 ∑ n − 1 f i x i g n − i − 1 x n − i − 1 由于
g 0 = 0 g_0 = 0 g 0 = 0 ，可以得到：
G ( x ) = x + 2 x C ( x ) G ( x ) G(x) = x+2xC(x)G(x) G ( x ) = x + 2 x C ( x ) G ( x ) 。
故
G ( x ) = x 1 − 2 x C ( x ) G(x)=\frac{x}{1-2xC(x)} G ( x ) = 1 − 2 x C ( x ) x 。带入
C ( x ) = 1 − 1 − 4 x 2 x C(x)=\frac{1-\sqrt{1-4x}}{2x} C ( x ) = 2 x 1 − 1 − 4 x ：
G ( x ) = x 1 − 4 x G(x)=\frac{x}{\sqrt{1-4x}} G ( x ) = 1 − 4 x x = x ∑ n ≥ 0 ( − 1 2 n ) ( − 4 x ) n =x\sum_{n\ge0}\binom{-\frac12}{n}(-4x)^n = x n ≥ 0 ∑ ( n − 2 1 ) ( − 4 x ) n = x ∑ n ≥ 0 ( − 1 ) n ( 2 n ) ! ( n ! ) 2 x n =x\sum_{n\ge0}(-1)^n\frac{(2n)!}{(n!)^2}x^n = x n ≥ 0 ∑ ( − 1 ) n ( n ! ) 2 ( 2 n )! x n 得到
g ( n ) = ( 2 n − 2 ) ! ( ( n − 1 ) ! ) 2 g(n) = \frac{(2n-2)!}{((n-1)!)^2} g ( n ) = (( n − 1 )! ) 2 ( 2 n − 2 )! 。则
g ( n ) f ( n ) \frac{g(n)}{f(n)} f ( n ) g ( n ) 为：
( 2 n − 2 ) ! ( ( n − 1 ) ! ) 2 ( 2 n ) ! n ! ( n + 1 ) ! = n 2 2 ( n + 1 ) 2 n ( 2 n − 1 ) = 2 n ( n + 1 ) 2 ( 2 n − 1 ) \frac{\frac{(2n-2)!}{((n-1)!)^2}}{\frac{(2n)!}{n!(n+1)!}} = \frac{n^22(n+1)}{2n(2n-1)}=\frac{2n(n+1)}{2(2n-1)} n ! ( n + 1 )! ( 2 n )! (( n − 1 )! ) 2 ( 2 n − 2 )! = 2 n ( 2 n − 1 ) n 2 2 ( n + 1 ) = 2 ( 2 n − 1 ) 2 n ( n + 1 ) 至此，我们完成了这道题。
P3599 Koishi Loves Construction \color{green}\text{P3599 Koishi Loves Construction} P3599 Koishi Loves Construction Problem 给定
n n n ，要求构造两个
1 ∼ n 1\sim n 1 ∼ n 的排列
a , b a, b a , b 满足
a a a 的前缀和在模
n n n 意义下两两不同，
b b b 的前缀积在模
n n n 意义下两两不同。
1 s , 125 M B 1s, 125MB 1 s , 125 MB Sol a a a 的构造：
n , 1 , n − 2 , 3 , n − 4 , … n, 1, n-2, 3, n-4, \dots n , 1 , n − 2 , 3 , n − 4 , … 。这个东西在
n n n 为奇数的时候无解。证明一下，因为
1 + 2 + ⋯ + n = n ( n + 1 ) 2 1+2+\dots+n=\frac{n(n+1)}2 1 + 2 + ⋯ + n = 2 n ( n + 1 ) 在
n n n 为奇数的时候模
n n n 为
0 0 0 ，因此会有两个前缀和相同。
由于最后乘
n n n 一定会让积变为
0 0 0 ，因此一定是把
n n n 放在最后。当
∏ i < n i m o d n = 0 \prod_{i < n} i \bmod n=0 ∏ i < n i mod n = 0 时无解。考虑如下构造：
1 × 1 2 × 2 3 × 3 4 × 4 5 × 5 6 × ⋯ × n − 2 n − 1 × n 1 \times \frac12\times\frac23\times\frac34\times\frac45\times\frac56\times\dots\times\frac{n-2}{n-1}\times n 1 × 2 1 × 3 2 × 4 3 × 5 4 × 6 5 × ⋯ × n − 1 n − 2 × n 。由于
1 i \frac1i i 1 在
m o d n \bmod n mod n 意义下两两不同，所以
1 − 1 i 1-\frac1i 1 − i 1 也一定两两不同。
把它和第一问关联一下。由于
n n n 只有
2 , 4 , p 2, 4, p 2 , 4 , p ，因此找一个原根，对
g k g^k g k 做类似构造即可。
P3447 [POI 2006] KRY-Crystals \color{red}\text{P3447 [POI 2006] KRY-Crystals} P3447 [POI 2006] KRY-Crystals Problem 给定
n n n ，
m 1.. n m_{1..n} m 1.. n 。求满足
0 ≤ a i ≤ m i 0\le a_i\le m_i 0 ≤ a i ≤ m i 且
⊕ a i = 0 \oplus a_i=0 ⊕ a i = 0 的序列
a a a 的个数。
n ≤ 50 , 1 ≤ m i ≤ 2 32 − 1 n \le 50, 1 \le m_i \le 2^{32}-1 n ≤ 50 , 1 ≤ m i ≤ 2 32 − 1 。
Sol 有一个
O ( 2 n V poly ( n ) ) O(2^nV\operatorname{poly}(n)) O ( 2 n V poly ( n )) 的做法是从大到小考虑每一位，然后记录有没有顶到上界。
但是异或的性质非常好啊，你发现如果现在有一个上界是
1 1 1 或没有上界就可以剩下的位随便选，然后用这一个
1 1 1 来补。于是从高到低枚举
i i i ，表示第
i + 1 ∼ 32 i+1\sim 32 i + 1 ∼ 32 位这些位都是满的。然后枚举这一位第一个没有填满的地方，让它作为调整位，记为
j j j 。则
1 ∼ j − 1 1\sim j-1 1 ∼ j − 1 的位置都是满的，它们在剩下的位数中的贡献即为它们的低位组成的数。对于一个
j j j ，需要统计
j + 1 ∼ n j+1\sim n j + 1 ∼ n 的位置异或和与前面相同的方案数（未填满的贡献是
2 k 2^k 2 k ），这个显然需要进行一个 DP。令
f k , 0 / 1 f_{k, 0/1} f k , 0/1 表示
k ∼ n k\sim n k ∼ n 这些数的第
i i i 位异或和为
0 / 1 0/1 0/1 的方案数。时间复杂度
O ( n log V ) O(n\log V) O ( n log V ) 。