二进制翻转（rev）
给定 n≤1015n\le 10^{15}n≤1015，定义 r(i)r(i)r(i) 表示 iii 二进制翻转后的结果，c(i)c(i)c(i) 表示 iii 二进制下 111 的个数，求：
∑i=0nc(i+r(i))\sum_{i=0}^n c(i+r(i))
i=0∑nc(i+r(i))
显然的数位 DP。
由于有翻转的存在，我们的数位 DP 的阶段 iii 应该表示同时包含低位 iii 和高位 iii 的状态。
并且，由于 +++ 的存在，数位 DP 同时应该包含低位 iii 的受到进位状态 j=0/1j=0/1j=0/1。
然后，考虑到高位 iii 也有进位。但是由于我们的数位 DP 在高位来看是倒着的，于是我们应该模仿传统加法模拟进位：记录 kkk 表示高位 iii 之前最后一个进位的位置。那么转移的时候只需要将中间的所有 111 变为 000 并计算代价即可。
接着，由于低位也可以向高位进位；同时这个 DP 具有对称性，所以我们可以一眼看出如下结论：如果状态 kkk（注意这个 kkk 是上面的那个 kkk）对应的低位有进位，那么一定会导致 ...
[JOI 2026 SemiFinal] 顺流而下 / River Rafting
[JOI 2026 SemiFinal] 顺流而下 / River Rafting。
JOI 国有 NNN 个城镇，城镇编号为 111 到 NNN。这些城镇之间有 N−1N-1N−1 条道路，编号为 111 到 N−1N-1N−1。道路 iii (1≤i≤N−11 \le i \le N-11≤i≤N−1) 双向连接城镇 PiP_iPi (Pi≤iP_i \le iPi≤i) 和城镇 i+1i+1i+1。保证从城镇 111 出发，可以通过若干条道路到达任意城镇。
此外，JOI 国有 N−1N-1N−1 条与道路平行的河流，河流编号为 111 到 N−1N-1N−1。河流 iii (1≤i≤N−11 \le i \le N-11≤i≤N−1) 与道路 iii 平行，从城镇 PiP_iPi 流向城镇 i+1i+1i+1。
NNN 个城镇中各放置了一盏灯。每盏灯都有一个强度。当城镇 ttt (1≤t≤N1 \le t \le N1≤t≤N) 处的灯强度为 lll 时，从该城镇出发，经过少于 lll ...
[JOI Open 2025] 抽奖 / Lottery
有 nnn 个盒子，第 iii 个盒子有 XiX_iXi 个红球和 YiY_iYi 个蓝球。
定义一次试验的结果如下：
取出区间 [l,r][l,r][l,r]，满足区间长度偶数；
多次操作，每次操作可以选择 r−l+12\frac{r-l+1}{2}2r−l+1 个盒子，取出其中的红球，并对于剩下的盒子，取出蓝球。直到某一个盒子为空为止。
你能进行的最多的操作次数就是这次试验的结果。
多次询问，每次给一个区间，求试验结果。
n≤105,Xi,Yi≤109n\le 10^5,X_i,Y_i\le 10^9n≤105,Xi,Yi≤109。
看起来没什么头绪。
不妨设 l=1,r=nl=1,r=nl=1,r=n，考虑二分答案，那么问题就变成判定 kkk 轮操作是否能经行。
设 aia_iai 表示最终 iii 盒子取了多少个红球，那么显然要满足 max{0,Yi−k}≤ai≤min{Xi,K}\max\{0,Y_i-k\}\le a_i\le \min\{X_i,K\}max{0,Yi−k}≤ai≤mi ...
Color the Tree
简单题。
HDU2013。
有 nnn 个节点的树，边有颜色且带权，W 和 R 要在上面博弈。
一次博弈的结果定义为这样：
树初始所有边为白色，W 初始在 aaa，R 初始在 bbb。W 和 R 交替操作，W 先手。
每次若操作者为 W，则其可以选择一个与他目前节点 xxx 的相邻的节点 yyy，满足 xxx 到 yyy 的边为白色或者红色，然后将这条边染红，接着 W 到 yyy。
否则若操作者 R，则其可以选择一个与他目前节点 xxx 的相邻的节点 yyy，满足 xxx 到 yyy 的边为白色或者蓝色，然后将这条边染蓝，接着 R 到 yyy。
最终 valWval_WvalW 为所有红色边的权值和，valRval_RvalR 为所有蓝色权值和。
W 希望 valWval_WvalW 最大，R 希望 valRval_RvalR 最大，两人都绝顶聪明，那么这次博弈的结果为 valWval_WvalW。
mmm 次询问，第 iii 次询问给定 W 和 R 的初始点 a,ba,ba,b，求博弈结果。
n,m≤105n,m\le 10^5n,m≤ ...
排列（perm）
一个排列 aaa，每次你可以交换一个逆序对。求你可以生成多少个不同的排列。
n≤20n\le 20n≤20。
考虑如何判断一个排列 ppp 是否能被生成。我们拿样例举例：
样例： 2 4 1 3。
首先我们先观察所有排列的第一项：显然，如果一个排列的第一项为 3,43,43,4，即 >a1>a_1>a1，那么这种排列肯定不行，原因是一个数能被交换到首位，必然需要和 a1a_1a1 交换。
那么我们就可以排除掉 121212 个排列。
然后我们看 a2a_2a2：由于 a2a_2a2 是 444，这导致我们什么也排除不掉。
接着看 a3a_3a3：a3a_3a3 是 111，那么，对于所有的排列，前 333 位中没有 1,21,21,2 的排列肯定也不行，因为如果是这样的话，原序列前 333 位的 1,21,21,2 必须被换到后面去，然而并没有数能把它换到后面去，所以所有前 333 不包含 1,21,21,2 的排列必然不行。
这样就只剩下 888 个排列了，恰好是答案。
思考一下上面排除方案的本质：对于 i<ji<j ...
Exclusive or
某人号 Sam 声称这是找规律题目。
HDU 2014。
给定 nnn，求：
∑i=1n−1i⊕(n−i)\sum_{i=1}^{n-1}i\oplus (n-i)
i=1∑n−1i⊕(n−i)
n≤10500n\le10^{500}n≤10500。
注意到这样一件事情：i⊕(n−i)=2(⌊i2⌋⊕⌊n−i2⌋)+[n mod 2]i\oplus(n-i)=2(\lfloor\frac{i}{2}\rfloor\oplus\lfloor\frac{n-i}{2}\rfloor)+[n\bmod 2]i⊕(n−i)=2(⌊2i⌋⊕⌊2n−i⌋)+[nmod2]。
于是，设 f(n)=∑i=0ni⊕(n−i)f(n)=\sum\limits_{i=0}^n i\oplus(n-i)f(n)=i=0∑ni⊕(n−i)，那么：
Case #1: nnn 为偶数
此时设 n=2kn=2kn=2k，那么考虑 f(k)f(k)f(k)：这个值恰好是对于 i=0∼ki=0\sim ki=0∼k，有 ∑ii⊕(n−i)=2f(k)\sum\limits_i i ...
[JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater
题目链接：[JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater。
给定长度为 nnn 的序列 aaa，然后进行变换：令所有偶数下标的位置变为相反数，即 ai←−aia_i\leftarrow-a_iai←−ai。
mmm 次询问，每次询问区间 [l,r][l,r][l,r]，求不交的甜菜的区间的最大个数，其中甜菜区间定义为区间和 ≥k\ge k≥k 的区间。
n,m≤5×105n,m\le 5\times10^5n,m≤5×105。
首先贪心的想，我们可以进行一个类似于“分段”的操作：每次只要最大子段和 ≥k\ge k≥k 就切一个区间，然后一直到最大子段和为 000，那么这个就为“一段”。
那么询问时我可以一直跳这个段。然而这个是 O(n2)\mathcal{O}(n^2)O(n2) 的。
然后你就发现：其实可以倍增的跳（我为什么没有想到！）。
想到这个后就做完了，只需要求出这个每一次“分段”到哪里即可。这个可以使用 ODT 搞一搞，倒序 ...
[JOI Final 2026] 传送机 2 / Teleporter 2
[JOI Final 2026] 传送机 2 / Teleporter 2。
给定直线 1∼n1\sim n1∼n，以及 mmm 个区间 [si,ti)[s_i,t_i)[si,ti)，要求不交区间的最大个数不超过 kkk。你可以通过花费 cic_ici 的代价删除区间 iii。求最小代价。
n,m,k≤105,ci≤109n,m,k\le 10^5,c_i\le 10^9n,m,k≤105,ci≤109。
首先有一个很厉害的转化：
不交区间的最大个数不超过 kkk，等价于放置 kkk 个点，使得这 kkk 个点可以覆盖所有区间。
乍一看挺显然的，但是想到这个真的很难啊！
那么有了这个转化后，我们就可以写出一个简单的 O(n3)\mathcal{O}(n^3)O(n3) 的 DP：
定义 fi,jf_{i,j}fi,j 表示考虑 1∼i1\sim i1∼i，放置了 jjj 个点的最小代价。那么如果定义 w(l,r)w(l,r)w(l,r) 表示所有完全包含在区间 [l,r][l,r][l,r ...
[蓝桥杯 2024 国研究生组] 深度优先搜索
我不会卡特兰数。
给定长度 nnn 的序列 aaa 满足 ai∈[−1,n]a_i\in[-1,n]ai∈[−1,n]，求有多少种将 −1-1−1 替换为 [0,n][0,n][0,n] 任意数的方案使得：
有且仅有 a1=0a_1=0a1=0；
对于任意一个 2≤i≤n2\le i\le n2≤i≤n，有 ai−1+1≥aia_{i-1}+1\ge a_iai−1+1≥ai。
对 109+710^9+7109+7 取模。
套路的差分，令 bi=ai−ai−1b_i=a_i-a_{i-1}bi=ai−ai−1，则 bi≤1b_i\le 1bi≤1。
不妨分段考虑，即，考虑 a0,an≠−1a_0,a_n\ne -1a0,an=−1，ai=−1a_i=-1ai=−1的弱化版。
那么首先我们有限制：
a0+∑bi=ana_0+\sum b_i=a_n
a0+∑bi=an
由于 bi≤1b_i\le 1bi≤1 不太好处理，我们不妨令 ci=1−bic_i=1-b_ici=1−bi，这样限制变为 c ...
Rikka with Match
某人号 Sam 尝曰：最大独立集乃树上背包也。
余曰：误人子弟。最大独立集乃贪心也。
Rikka with Match。
给定 nnn 个点的树，求有多少中割边的方案使得最大匹配大小被 mmm 整除。
n≤5×104,m≤200n\le 5\times10^4,m\le 200n≤5×104,m≤200。
将最大匹配转化为最大独立集后，首先我们应该想如何刻画最大独立集：
贪心：
按深度从大到小选择点。只要这个点可以选择就选择。
那么我们就可以得出一个 DP 状态并利用上述贪心转移：定义 fi,j,kf_{i,j,k}fi,j,k 为 iii 的子树，最大独立集模 mmm 为 jjj，且 iii 选择/不选择的方案数。
然后初始化是比较简单的，因为按照贪心，一开始是时候只有 iii 一个点，于是必须选择，那么就有 fx,1,1=1f_{x,1,1}=1fx,1,1=1，其余为 000。
考虑仿照树形背包，逐步加入儿子 uuu。
那么对于儿子 uuu，我既可以断掉这条边，也可以不断。
Case #1：断
这个时候 uuu 的选择就与 xxx ...
