题解
状态压缩动态规划（状压 DP）
题目大意
有 $n$ 个人做报告，第 $i$ 个人会使兴奋度 $x$ 变成 $a_i\lvert x\rvert+b_ix+c_i$ 。
初始兴奋度为 $s$ ，调整报告顺序使得最后的兴奋度最大。
$n,s,|a_i|,|b_i|,|c_i|\le15$ .
思路
调整顺序，范围又很小，于是考虑状压 DP。
贡献是分段函数，可以看作是端点在 $y$ 轴上的两条射线，并不是 …
Jayun 发布于 2025-06-18 20:44:39
10
快速数论变换（NTT）计数
题目大意
给定以 $1$ 为根结点的一棵树，有 $n(n\leq5\times10^5)$ 个节点，对于每个 $k\leq n$ ，求随机选取 $k$ 的结点的期望 LCA 深度，结果对 998244353 取模。
题解
考虑每个点 $u$ 的贡献为
$$\text{dep}(u)\left(\binom{|T_u|}{k}-\sum_{v\in\text{son}(u)}\bi …
Jayun 发布于 2025-06-16 21:07:38
10
普通生成函数数学推导杂项排列组合计数
题目大意
$n$ 排两列，塞 $n$ 对情侣，求恰好 $k$ 对情侣没有被拆散的数量。对 $998244353$ 取模。
题解
注意到，答案表达式为
$$\binom{n}{k}\cdot n^{\underline{k}}\cdot 2^k\cdot f_{n-k}
$$
其中 $f_i$ 是 $i$ 对情侣全被拆散的数量。有
$$f_i=4i(i-1)\left(f_{ …
Jayun 发布于 2025-06-12 21:26:59
10
矩阵快速幂组合意义线性动态规划（线性 DP）数学推导杂项
给定 $n$ , $p$ , $r$ , $k$ ( $1\le n\le 10^9$ , $0\le r,2\le p\le 2^{30}-1$ )，求
$$\sum_{i\bmod k=r}{nk\choose i}\bmod p
$$
题解
$$\begin{aligned}&\sum_{i\bmod k=r}{nk\choose i}\\=&\sum_{i\bm …
Jayun 发布于 2024-03-01 14:13:10
10
匈牙利算法
Maximize Mex
题面
在一所学校里有 $n$ 名学生和 $m$ 个社团，社团被编号为 $1$ ~ $m$ 。第 $i$ 个学生有一个能力值 $p_i$ ，且属于社团 $c_i$ （每个学生恰好属于一个社团） 。
学校将要举行一个为期 $d$ 天的活动，每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中各选出一个人（如果某个社团没有人，就不选）组成一个 …
Jayun 发布于 2024-02-29 18:32:31
00
排列组合范德蒙德卷积计数容斥原理
Koxia and Sequence
题面
给定非负整数 $n,x,y$ ，对于所有满足 $\sum_{i=1}^n a_i=x,\text{OR}_{i=1}^n a_i=y$ ，的序列 $\{a_n\}$ 。求 $\bigoplus_{i=1}^n a_i$ 的异或和。
$1 \leq n < 2^{40} , 0 \leq x < 2^{60} , 0 \leq …
Jayun 发布于 2024-02-28 22:00:46
00
最小割最大流SPFA
题面
有 $n$ 个变量 $w[1]\sim w[n]$ ，每个变量的值为 $W$ 或 $-W$ 。
有 $p$ 个公式 $f(i)=a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[x_i]|+d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$ 。 其中 $ …
Jayun 发布于 2024-02-28 20:20:20
00
数学推导杂项线性动态规划（线性 DP）
[AGC020C] Median Sum
题面
给定由 $n$ 个正整数 $a _ {1, 2, \cdots, n}$ 组成的可重集合，请求出它的非空子集的和的中位数。
$1\ \leq\ n\ \leq\ 2000, 1\ \leq\ A_i\ \leq\ 2000$
题解
发现重要性质，非空子集的和在值域上是对称的。bitset 背包即可。
代码
const int N = 20 …
Jayun 发布于 2024-02-28 18:37:23
00
数学推导杂项计数
题面
有一个 $1\sim n$ 的排列 $\{p_i\}$ ，对应了 $i$ 条有向边为 $(i,p_i)$ 的图。由于 $p_i$ 是排列，可以证明图由若干个环组成。你希望知道有多少种可能的排列 $\{p_i\}$ ，使得图中每一个环长度都为偶数，答案对 $998244353$ 取模。其中一部分 $p_i$ 已经给定。
$n\leq 10^5$ 。
题解
特 …
Jayun 发布于 2024-02-28 18:33:50
00