dp.go

package copypasta

import (
	"container/heap"
	"math"
	"math/bits"
	"slices"
	"sort"
	"strconv"
)

/* 动态规划（Dynamic Programming，DP）

【题单】入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望
https://leetcode.cn/circle/discuss/tXLS3i/

https://www.luogu.com.cn/training/440704

入门视频
https://www.bilibili.com/video/BV1Xj411K7oF/

如何用记忆化搜索打印具体方案
https://leetcode.cn/problems/shortest-common-supersequence/solution/cong-di-gui-dao-di-tui-jiao-ni-yi-bu-bu-auy8z/

前缀/后缀之间的转移，例如从 f[i-1] 转移到 f[i]，或者从 f[j] 转移到 f[i]
LC70 爬楼梯 https://leetcode.cn/problems/climbing-stairs/
- 有花费 LC746 https://leetcode.cn/problems/min-cost-climbing-stairs/
- https://atcoder.jp/contests/dp/tasks/dp_a
- https://atcoder.jp/contests/dp/tasks/dp_b
- 有障碍物 https://atcoder.jp/contests/abc129/tasks/abc129_c
LC198 打家劫舍 https://leetcode.cn/problems/house-robber/
- 值域打家劫舍 LC740 https://leetcode.cn/problems/delete-and-earn/
   - 分组+值域打家劫舍 https://atcoder.jp/contests/abc403/tasks/abc403_d
   - 类似思路的题目 https://leetcode.cn/problems/the-number-of-beautiful-subsets/
- 恰好选 floor(n/2) 个 https://atcoder.jp/contests/abc162/tasks/abc162_f
- 矩阵打家劫舍 https://codeforces.com/problemset/problem/1195/C
- 环形 LC213 https://leetcode.cn/problems/house-robber-ii/
- 环形 https://atcoder.jp/contests/abc251/tasks/abc251_e
LC2369 https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/ 1780
- 变形：改成环形数组要怎么做
- 相似题目 https://codeforces.com/problemset/problem/1624/E 2000
https://codeforces.com/problemset/problem/1547/E 1500
https://codeforces.com/problemset/problem/1881/E 1500
https://codeforces.com/problemset/problem/1875/D 1600
https://codeforces.com/problemset/problem/30/C 1800
https://codeforces.com/problemset/problem/1627/E 2200 刷表法 双指针
https://codeforces.com/problemset/problem/1739/E 2400
另见「最长递增子序列」

双序列问题，一般定义 f[i][j] 表示对子问题 (s1[:i],s2[:j]) 的求解结果
见下面的「最长公共子序列」，包含大量扩展题目
https://codeforces.com/problemset/problem/2050/E 1500

多维 DP
https://codeforces.com/problemset/problem/2027/D1 1700
https://codeforces.com/problemset/problem/404/D 1900
https://codeforces.com/problemset/problem/1920/E 2000
https://codeforces.com/problemset/problem/2027/D2 2200 在 DP 数组上滑窗
https://codeforces.com/problemset/problem/2045/H 2200
https://codeforces.com/problemset/problem/6/D 2600
https://codeforces.com/problemset/problem/367/E 2700 状态设计
https://atcoder.jp/contests/dp/tasks/dp_t 状态设计
https://www.luogu.com.cn/problem/P2258

合法子序列 DP
https://www.luogu.com.cn/problem/P4933
- LC446 https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

输出具体方案
做这一道题就够了 https://codeforces.com/problemset/problem/56/D 2100

从 X 操作到 Y（部分题目也可以用 BFS）
+1 -1 /2 [397. 整数替换](https://leetcode.cn/problems/integer-replacement/)
-1 +1 /5 /11 [2998. 使 X 和 Y 相等的最少操作次数](https://leetcode.cn/problems/minimum-number-of-operations-to-make-x-and-y-equal/) 1795
+a[i] -a[i] ^a[i] [2059. 转化数字的最小运算数](https://leetcode.cn/problems/minimum-operations-to-convert-number/) 1850
-1 *2 [991. 坏了的计算器](https://leetcode.cn/problems/broken-calculator/) 1909
/2 /3 [1553. 吃掉 N 个橘子的最少天数](https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/) 2048
-1 /k https://codeforces.com/problemset/problem/940/B 1400
[LCP 09. 最小跳跃次数](https://leetcode.cn/problems/zui-xiao-tiao-yue-ci-shu/)
[LCP 20. 快速公交](https://leetcode.cn/problems/meChtZ/)
*5 /6 https://ac.nowcoder.com/acm/contest/71512/D

预处理
LC2638 https://leetcode.cn/problems/count-the-number-of-k-free-subsets/

题单 https://www.luogu.com.cn/training/83815#problems

https://atcoder.jp/contests/abc289/tasks/abc289_d 跳台阶+禁入点
https://atcoder.jp/contests/abc248/tasks/abc248_c 入门计数 DP
https://atcoder.jp/contests/abc281/tasks/abc281_d
https://codeforces.com/contest/1525/problem/D 选或不选 [1800·hot10]
https://codeforces.com/problemset/problem/176/B
https://codeforces.com/problemset/problem/1324/E
https://codeforces.com/problemset/problem/505/C
https://atcoder.jp/contests/abc267/tasks/abc267_d
https://codeforces.com/problemset/problem/9/D 由 n 个值互不相同的点组成的高度不小于 h 的 BST 有多少个
https://codeforces.com/problemset/problem/38/E
https://codeforces.com/problemset/problem/358/D 好题：涉及到相邻状态先后关系的 DP（喂兔子）
https://codeforces.com/problemset/problem/446/A
https://codeforces.com/problemset/problem/603/A
https://codeforces.com/problemset/problem/811/C 处理区间元素不能在区间外面的技巧 https://codeforces.com/contest/811/submission/174568255
https://codeforces.com/problemset/problem/1120/C
https://codeforces.com/problemset/problem/1163/D 与 KMP 结合
https://codeforces.com/problemset/problem/1168/C
https://codeforces.com/problemset/problem/1542/D
https://codeforces.com/problemset/problem/1845/E
https://www.luogu.com.cn/problem/T576294?contestId=224129

不相交区间 DP
https://codeforces.com/problemset/problem/1801/C

排列型/插入型
LC629 https://leetcode.cn/problems/k-inverse-pairs-array/ https://www.luogu.com.cn/problem/P2513
https://www.lanqiao.cn/problems/240/learning/
https://atcoder.jp/contests/abc282/tasks/abc282_g

介值定理
https://codeforces.com/contest/1695/problem/C
https://codeforces.com/contest/2043/problem/C

网格路径问题 网格图 DP
技巧：对于求方案数的题目，可以初始化 f[0][1] = 1，从而避免单独讨论左上角 f[1][1] 的计算
- [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii/)
	- https://atcoder.jp/contests/dp/tasks/dp_h
- [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum/)
	- 变形：连续性 & 上下界思想 https://codeforces.com/contest/1695/problem/C
    - https://atcoder.jp/contests/arc137/tasks/arc137_b 也用到了这个思想
- [120. 三角形最小路径和](https://leetcode.cn/problems/triangle/)
	- https://www.luogu.com.cn/problem/P1216
    - 额外状态 https://www.luogu.com.cn/problem/P1544
- [741. 摘樱桃](https://leetcode.cn/problems/cherry-pickup/)
   - https://codeforces.com/problemset/problem/213/C 2000
   - https://www.luogu.com.cn/problem/P1004 [NOIP2000 提高组] 方格取数
   - https://atcoder.jp/contests/abc320/tasks/abc320_f 2042
- [1463. 摘樱桃 II](https://leetcode.cn/problems/cherry-pickup-ii/) 1957
   - 回文串 https://codeforces.com/problemset/problem/570/E
每行至多选三个 https://atcoder.jp/contests/abc175/tasks/abc175_e
https://atcoder.jp/contests/abc147/tasks/abc147_e 1713

图 DP
https://codeforces.com/problemset/problem/346/D 2600

思考过程：
1. 把原问题重新复述一遍，例如「从前 n 个数中选择若干个数，这些数的和为 m 的方案数」。
2. 根据题意，尝试「缩小」问题的规模，我们可以怎样缩小？
   - 这里有两个变量 n 和 m，有什么方法可以把它们缩小？
3. 尝试「原子」操作（考虑其中「一个」数选或者不选，例如第 n 个数）：
   - 不选第 n 个数，问题变为「从前 n-1 个数中选择若干个数，这些数的和为 m 的方案数」。
   - 选第 n 个数，问题变为「从前 n-1 个数中选择若干个数，这些数的和为 m-a[n] 的方案数」。
   - 原问题可以不重不漏地分解成这两种情况。
   - 根据加法原理，原问题为这两种方案的和。
4. 这可以用记忆化搜索写。终点是什么？
   - n=0。（这里数组下标是从 1 开始的）
5. 如果用递推来思考，要怎么写？空间能否压缩？
   - 自底向上思考记忆化搜索的过程。
6.（进阶）如果复杂度过高，如何根据状态转移方程来优化？
7.（进阶）状态不好确定时，尝试转化问题模型、逆序思考、增加维度等等。（试试下面的题目）

常规题目
预处理 https://codeforces.com/contest/1932/problem/F

记忆化搜索
- [1387. 将整数按权重排序](https://leetcode.cn/problems/sort-integers-by-the-power-value/) 1507

状态个数优化
https://www.luogu.com.cn/problem/P7961

如何设计状态
https://codeforces.com/problemset/problem/1461/B 1400
https://codeforces.com/problemset/problem/553/A 1500
https://codeforces.com/problemset/problem/1286/A 1800
https://codeforces.com/problemset/problem/1987/D 1800
https://codeforces.com/problemset/problem/14/E 1900
https://codeforces.com/problemset/problem/452/D 1900 题解 https://www.luogu.com.cn/blog/endlesscheng/solution-cf452d
https://codeforces.com/problemset/problem/687/C 1900
https://codeforces.com/problemset/problem/1012/C 1900
https://codeforces.com/problemset/problem/360/B 2000
https://codeforces.com/problemset/problem/461/B 2000
todo https://codeforces.com/problemset/problem/571/B 2000
https://codeforces.com/problemset/problem/1408/D 2000
https://codeforces.com/problemset/problem/1783/D 2000 推公式
https://codeforces.com/problemset/problem/1025/D 2100
https://codeforces.com/problemset/problem/1027/E 2100
https://codeforces.com/problemset/problem/1579/G 2200
https://codeforces.com/problemset/problem/1927/G 2300
todo https://codeforces.com/problemset/problem/441/E 2400 考虑 x+i 的尾零个数
https://atcoder.jp/contests/arc115/tasks/arc115_e 容斥
- https://codeforces.com/contest/1591/problem/F
todo https://codeforces.com/problemset/problem/744/C 2400
https://codeforces.com/problemset/problem/1348/E 2400 做到 O(nk) todo 需要复习
https://codeforces.com/problemset/problem/840/C 2500
https://atcoder.jp/contests/abc237/tasks/abc237_f
https://atcoder.jp/contests/abc232/tasks/abc232_e
https://atcoder.jp/contests/arc097/tasks/arc097_c 混合逆序对
https://atcoder.jp/contests/arc116/tasks/arc116_d 寻找子问题
https://atcoder.jp/contests/arc107/tasks/arc107_d 2099=CF2299 状态设计 todo 容斥做法
todo https://atcoder.jp/contests/abc200/tasks/abc200_e
SEERC05，紫书例题 9-3，UVa 1347 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4093
LC2919 https://leetcode.cn/problems/minimum-increment-operations-to-make-array-beautiful/ 2031
LC3193 https://leetcode.cn/problems/count-the-number-of-inversions/ 利用排列的性质
LC956 https://leetcode.cn/problems/tallest-billboard/ 2381
LC1388 https://leetcode.cn/problems/pizza-with-3n-slices/ 2410
LC903 DI 序列的有效排列 https://leetcode.cn/problems/valid-permutations-for-di-sequence/ 2433
LC2638 https://leetcode.cn/problems/count-the-number-of-k-free-subsets/
https://www.luogu.com.cn/problem/P9688?contestId=133572
《挑战》pp.62-64 多重部分和问题

如何消除后效性（通过巧妙地设计状态/发现性质）
LC2896 执行操作使两个字符串相等 https://leetcode.cn/problems/apply-operations-to-make-two-strings-equal/
LC312 戳气球 https://leetcode.cn/problems/burst-balloons/
LC546 消消乐 https://leetcode.cn/problems/remove-boxes/ https://leetcode.com/contest/leetcode-weekly-contest-25
UVa1625 合并序列 最小化所有元素第一次和最后一次出现的位置差的和 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4500
涉及到相邻状态先后关系（喂兔子）https://codeforces.com/problemset/problem/358/D

状态优化
LC935 减少状态个数 https://leetcode.cn/problems/knight-dialer/
妙！https://atcoder.jp/contests/abc243/tasks/abc243_g

输出方案
LC1092 https://leetcode.cn/problems/shortest-common-supersequence/
- 题解：https://leetcode.cn/problems/shortest-common-supersequence/solution/cong-di-gui-dao-di-tui-jiao-ni-yi-bu-bu-auy8z/
LC2212 https://leetcode.cn/problems/maximum-points-in-an-archery-competition/

值域 DP
常见于递增子序列相关的题目
LC3041 https://leetcode.cn/problems/maximize-consecutive-elements-in-an-array-after-modification/
https://codeforces.com/problemset/problem/1582/F1

决策单调性
todo 决策单调性优化总结 https://www.luogu.com.cn/blog/command-block/dp-di-jue-ce-dan-diao-xing-you-hua-zong-jie
https://codeforces.com/problemset/problem/229/D

增量法
见 common.go

思维转换
谁来当 DP 对象 LC1434 https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/
扔蛋问题 LC887 https://leetcode.cn/problems/super-egg-drop/ https://www.bilibili.com/video/BV1KE41137PK
LC920* https://leetcode.cn/problems/number-of-music-playlists/ 注：官方题解给出了一种生成函数的做法
状态优化 https://codeforces.com/problemset/problem/838/E
「排序」题的转换 https://codeforces.com/problemset/problem/1223/D
https://codeforces.com/problemset/problem/1542/D
https://codeforces.com/problemset/problem/520/E
https://codeforces.com/problemset/problem/883/I
路径计数+推箱子 https://codeforces.com/problemset/problem/1225/E
找关键元素+状态机DP https://codeforces.com/problemset/problem/623/B
https://codeforces.com/problemset/problem/1624/E

贪心+DP
https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/
https://codeforces.com/problemset/problem/1799/F 2700

NOTE: 无后效性是指当前的决策只与过去的结果有关，而与过去的决策无关
NOTE: 若状态转移不构成 DAG，请尝试建图+BFS，见：
	https://ac.nowcoder.com/acm/contest/6218/B
	https://codeforces.com/problemset/problem/283/B 活用 012 染色
    https://codeforces.com/problemset/problem/1272/F
    - 也可以在记忆化搜索的过程中，提前设置 memo 的值，来避免陷入死循环 https://codeforces.com/problemset/submission/1272/208121980
NOTE: 递归套递归打印方案 https://leetcode.cn/problems/shortest-common-supersequence/solutions/2194615/cong-di-gui-dao-di-tui-jiao-ni-yi-bu-bu-auy8z/
NOTE: 若使用滚动数组，注意复用时可能要初始化
NOTE:（区间 DP）正向计算不易时，试着反向计算
TIPS: 若转移是若干相邻项之和，可以考虑 f(p) - f(p-1) 的值，用滑动窗口来维护区间和，从而优化转移
      例题 LC837 https://leetcode.cn/problems/new-21-game/
递归打印路径：https://codeforces.com/problemset/problem/2/B
需要补充额外的状态 https://codeforces.com/problemset/problem/682/D

todo Non-trivial DP Tricks and Techniques https://codeforces.com/blog/entry/47764

交替 DP
https://codeforces.com/problemset/problem/1479/B2
思路二 https://www.luogu.com.cn/blog/wsyhb/post-ti-xie-cf1479b2-painting-the-array-ii

计数 DP
另见 math_comb.go 中的「一些组合问题」
入门计数 DP https://atcoder.jp/contests/abc248/tasks/abc248_c
入门计数 DP LC1079 https://leetcode.cn/problems/letter-tile-possibilities/
- 相似技巧 LC1681 https://leetcode.cn/problems/minimum-incompatibility/discussion/comments/2051770
https://codeforces.com/problemset/problem/414/B 1400 刷表法
https://codeforces.com/problemset/problem/1794/D 1900
https://codeforces.com/problemset/problem/1767/C 2100 带约束的计数 DP
https://codeforces.com/problemset/problem/2060/F 2200
https://codeforces.com/problemset/problem/626/F 2400 转换
https://codeforces.com/problemset/problem/1237/F 2600
https://codeforces.com/problemset/problem/995/F 2700 也可以用拉格朗日插值
https://www.luogu.com.cn/problem/P5664 状态设计
todo https://atcoder.jp/contests/abc234/tasks/abc234_f

多重组合
- 见「多重背包 - 求方案数 - 同余前缀和优化」

多重排列
- f[i][j] 表示前 i 类数字组成长为 j 的排列个数
- f[i][j] = ∑f[i-1][k]*C(j,k), 0<=k<=min(j,cnt[i])
- 边界 f[0][0] = 1

贪心优化 DP
https://codeforces.com/problemset/problem/864/E

双指针优化 DP
https://codeforces.com/problemset/problem/883/I
https://training.olinfo.it/#/task/preoii_yutaka/statement

我的视频讲解：
https://www.bilibili.com/video/BV1Xj411K7oF 从记忆化搜索到递推
https://www.bilibili.com/video/BV16Y411v7Y6 背包问题
https://www.bilibili.com/video/BV1TM4y1o7ug LCS
https://www.bilibili.com/video/BV1ub411Q7sB LIS
https://www.bilibili.com/video/BV1ho4y1W7QK 状态机 DP
https://www.bilibili.com/video/BV1Gs4y1E7EU 区间 DP
https://www.bilibili.com/video/BV17o4y187h1 树形 DP
https://www.bilibili.com/video/BV1vu4y1f7dn 树形 DP
https://www.bilibili.com/video/BV1oF411U7qL 树形 DP

https://www.bilibili.com/video/BV1gf4y1i78H 动态规划的套路 by wisdompeak
https://www.bilibili.com/video/av70148899 DP 入门，01 背包，完全背包，多重背包
https://www.bilibili.com/video/av77393700 LCS LIS
https://www.bilibili.com/video/av83939419 区间 DP
https://www.bilibili.com/video/av93356551 状态压缩 DP
https://www.bilibili.com/video/av98090640 树形 DP
https://www.bilibili.com/video/av85636122 动态规划 · 零 - Introduction
https://www.bilibili.com/video/av86983419 动态规划 · 一 - 序列型
https://www.bilibili.com/video/av89052674 动态规划 · 二 - 坐标、双序列、划分 & 状态压缩

套题/总结：
推荐 AtCoder 上的经典 DP 场 https://atcoder.jp/contests/dp
    题解 https://www.cnblogs.com/shanxieng/p/10232228.html
        https://codeforces.com/blog/entry/92170
        https://www.hamayanhamayan.com/entry/2019/01/12/163853
    讨论 https://codeforces.com/blog/entry/64250
《挑战程序设计竞赛》上的练习题（均为 POJ）
2.3 节
3176 https://www.luogu.com.cn/problem/P1216 数字三角形
2229 https://www.luogu.com.cn/problem/P6065 将 n 分拆为若干个 2 的次幂的和的方法数 https://oeis.org/A018819
2385 https://www.luogu.com.cn/problem/P2690 f[i分钟][j移动次数] = max(f[i-1][j], f[i-1][j-1]) + 当前分钟是否有苹果落在 j 次移动后的位置   最后答案为 max{f[n-1]}
3616 https://www.luogu.com.cn/problem/P2889 DAG 最长路
3280 https://www.luogu.com.cn/problem/P2890 增删取 min，跑区间 DP
1742 http://acm.hdu.edu.cn/showproblem.php?pid=2844 多重背包
3046 http://poj.org/problem?id=3046 todo
3181 https://www.luogu.com.cn/problem/P6205 完全背包
1065 http://acm.hdu.edu.cn/showproblem.php?pid=1051 n 轮 LIS
1631 http://acm.hdu.edu.cn/showproblem.php?pid=1950 转换成 LIS
3666 https://www.luogu.com.cn/problem/P2893
     https://codeforces.com/problemset/problem/13/C
     https://codeforces.com/problemset/problem/713/C
     https://www.luogu.com.cn/problem/P4597 加强版
2392 https://www.luogu.com.cn/problem/P6771 多重背包，按高度限制排序。高度既是价值也是体积
2184 https://www.luogu.com.cn/problem/P2340 把 IQ 看成体积，EQ 看成价值，注意把负数偏移到非负数，以及负数的转移写法
todo 3.4 节
2686 https://www.luogu.com.cn/problem/SP1700
1769 https://www.luogu.com.cn/problem/SP90 https://www.luogu.com.cn/problem/UVA1322
2441
3254 https://www.luogu.com.cn/problem/P1879
2836
1795 https://www.luogu.com.cn/problem/SP1776
3411 https://www.luogu.com.cn/problem/SP3953
3420
3735
3171 https://www.luogu.com.cn/problem/P4644 见 graph.dijkstraShortestPath
CSES DP section editorial https://codeforces.com/blog/entry/70018
力扣上的 DP 问题
    分类汇总 https://zhuanlan.zhihu.com/p/126546914
    https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns
    https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md
    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems
    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/
    https://leetcode.cn/tag/dynamic-programming/
信息学奥赛一本通 第二部分 基础算法 --> 第九章 动态规划 http://ybt.ssoier.cn:8088/index.php
算法竞赛专题解析（11）：DP概述和常见DP面试题 https://blog.csdn.net/weixin_43914593/article/details/105444090
todo 题目推荐 https://www.luogu.com.cn/blog/wyy2020/dp-qian-tan
  https://www.cnblogs.com/flashhu/p/9480669.html

其他资料：
https://github.com/hzwer/shareOI/tree/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://oi-wiki.org/dp/
https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
https://wenku.baidu.com/view/7c9de809581b6bd97f19ea72.html 算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》
*/
func _(abs func(int) int) {
	// 如果用（多维）数组记忆化
	// 小技巧，可以在保存的时候把计算结果 +1（或者 +1e18），取出来的时候 -1（或者 -1e18）
	// 这样原来的 *p != -1 可以改成 *p > 0，避免初始化 memo 数组时的多重循环

	// 由于数据范围的原因，采用 map 记忆化         dpMap
	// LC1553 https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/
	// LC2998 https://leetcode.cn/problems/minimum-number-of-operations-to-make-x-and-y-equal/
	// LC638 https://leetcode.cn/problems/shopping-offers/
	// https://codeforces.com/problemset/problem/510/D
	// https://codeforces.com/problemset/problem/1746/D
	// 如何估计时间复杂度 https://atcoder.jp/contests/abc275/tasks/abc275_d
	mapDP := func(n int) (ans int) {
		{
			// 一维（多维见下）
			memo := map[int]int{}
			var f func(int) int
			f = func(x int) (res int) {
				//if x == 0 {
				//	return
				//}
				if v, ok := memo[x]; ok {
					return v
				}
				defer func() { memo[x] = res }()

				return
			}
			ans = f(n)
		}

		{
			// 多维
			type pair struct{ x, y int }
			memo := map[pair]int{}
			var f func(int, int) int
			f = func(x, y int) (res int) {
				//if x == n {
				//  return
				//}
				p := pair{x, y}
				if v, ok := memo[p]; ok {
					return v
				}
				defer func() { memo[p] = res }()

				return
			}
			ans = f(0, 0)
		}

		return
	}

	// 最大子段和 / 最大子数组和
	// 有三种思路
	// 1. Kadane 算法：定义状态 f[i] 表示以 a[i] 结尾的最大子段和，则有状态转移方程 f[i]=max(f[i−1],0)+a[i]，答案为 max(f)
	// 2. 前缀和：遍历 a 的同时维护前缀和的最小值，则遍历到 a[i] 时，当前最大子段和为 sum[i]-min(sum[j]), j<i
	//    - 我的题解：https://leetcode.cn/problems/maximum-subarray/solution/qian-zhui-he-zuo-fa-ben-zhi-shi-mai-mai-abu71/
	// 3. 分治：通常用于一些带修改的题目，需要用到线段树 https://www.luogu.com.cn/problem/P4513 https://codeforces.com/contest/1843/problem/F2
	//
	// LC53 https://leetcode.cn/problems/maximum-subarray/ 
	// https://www.luogu.com.cn/problem/P1115
	// LC2606 https://leetcode.cn/problems/find-the-substring-with-maximum-cost/
	//
	// 二维版本
	// https://leetcode.cn/problems/max-submatrix-lcci/
	// https://www.luogu.com.cn/problem/P1719
	//
	// 《算法导论》练习 4.1-5
	// [题型总结] 关于最大子段和及其变式 https://www.luogu.com.cn/blog/wey-yzyl/zui-tai-zi-duan-hu-ji-ji-bian-shi-di-qi-shi
	// 子段长度有上限的最大子段和：见单调队列，题目为 https://ac.nowcoder.com/acm/contest/1006/D
	// 子段长度有下限的最大子段和：转换为前缀和之差 sum[i]-sum[j]，i-j>=K，维护 mn=min(mn,sum[j])，同时更新 sum[i]-mn 的最大值（另见 sort.go 中的 0-1 分数规划）
	// - https://www.luogu.com.cn/problem/P1404
	// 一道题考察上面两个限制 https://codeforces.com/problemset/problem/1796/D
	// - O(n) 做法 https://codeforces.com/contest/1796/submission/263191415
	// 子段和有上限的最大子段和：转换为前缀和之差 sum[i]-sum[j]<=K，在平衡树上二分 sum[j] 
	// - LC363 https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/
	// 最大两段子段和：求每个位置上的前缀最大子段和和后缀最大子段和 https://www.luogu.com.cn/problem/P2642
	// - 等价题目：允许翻转一段子区间的最大子段和
	// 最大三段子段和 LC689 https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/ *长度固定为 k
	// 删除至多一个元素后的最大子段和 LC1186 https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/
	// - 也可以前后缀分解
	// 最大 m 段子段和 http://acm.hdu.edu.cn/showproblem.php?pid=1024
	// 环状最大子段和：转换为 max(最大子段和, 总和减去最小子段和) LC918 https://leetcode.cn/problems/maximum-sum-circular-subarray/
	// 环状最大两段子段和：思路类似，注意取反后需要传入 a[1:n-1] https://www.luogu.com.cn/problem/P1121 https://ac.nowcoder.com/acm/contest/7738/B
	// 去掉一个最大值的最大子段和（值域比较小）https://codeforces.com/contest/1359/problem/D
	// 变形题：
	// LC2321 https://leetcode.cn/problems/maximum-score-of-spliced-array/
	// LC1749 https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/
	// - 另一种做法是计算前缀和的最大值与最小值的差
	// LC1191 重复 k 次 https://leetcode.cn/problems/k-concatenation-maximum-sum/
	// https://codeforces.com/problemset/problem/1285/B 1300
	// https://codeforces.com/problemset/problem/788/A 1600
	// https://codeforces.com/problemset/problem/1373/D 1600
	// https://codeforces.com/problemset/problem/2043/C 1600 介值定理
	// https://codeforces.com/problemset/problem/33/C 1800
	// https://codeforces.com/problemset/problem/1845/D 1800 本质是去掉一个最小的子段
	// https://codeforces.com/problemset/problem/1155/D 1900
	// https://codeforces.com/problemset/problem/1197/D 1900 思路 https://docs.qq.com/sheet/DWGFoRGVZRmxNaXFz 里面搜本题链接
	// https://codeforces.com/problemset/problem/1082/E 2000 需要一些转换技巧
	// https://atcoder.jp/contests/arc137/tasks/arc137_b
	// https://codeforces.com/problemset/problem/75/D 2000 多个小数组合并
	// - 这题做法需要用到上面说到的第二种思路
	// https://codeforces.com/problemset/problem/1370/E 2100 转换
	// https://codeforces.com/problemset/problem/1843/F2 2300 树上的情况 
	// 二维的情况（最大子阵和）可以枚举上下边界，转换成一维   O(n^3)
	maxSubarraySum := func(a []int) int {
		if len(a) == 0 { // 根据题意返回
			return 0
		}
		maxS, sum := math.MinInt, 0
		for _, v := range a {
			sum = max(sum, 0) + v
			maxS = max(maxS, sum)
		}
		if maxS < 0 { // 根据题意返回
			//return 0
		}
		return maxS
	}

	// 除了返回最大子段和外，还返回最大子段和对应的子段 [l,r]
	// https://codeforces.com/contest/1692/problem/H
	maxSubarraySumWithRange := func(a []int) (maxS, l, r int) {
		if len(a) == 0 { // 根据题意返回
			return 0, -1, -1
		}
		maxS = a[0] // 注意 l 和 r 默认为 0，即 a[:1]
		for i, sum, st := 1, a[0], 0; i < len(a); i++ {
			if sum < 0 {
				sum, st = 0, i // 重新开始
			}
			sum += a[i]
			if sum > maxS {
				maxS, l, r = sum, st, i
			}
		}
		if maxS < 0 { // 根据题意返回
			//return 0, -1, -1
		}
		return
	}

	// 维护前缀和的最小值的写法
	// https://codeforces.com/contest/1692/problem/H
	maxSubarraySumWithRange = func(a []int) (maxS, l, r int) {
		if len(a) == 0 { // 根据题意返回
			return 0, -1, -1
		}
		maxS = a[0] // 注意 l 和 r 默认为 0，即 a[:1]
		sum, minS, minI := 0, 0, -1
		for i, v := range a {
			sum += v
			if sum-minS > maxS {
				maxS, l, r = sum-minS, minI+1, i
			}
			if sum < minS {
				minS, minI = sum, i
			}
		}
		if maxS < 0 { // 根据题意返回
			//return 0, -1, -1
		}
		return
	}

	// 最大两段子段和（两段必须间隔至少 gap 个数）
	maxTwoSubarraySum := func(a []int, gap int) int {
		// 注意下界
		n := len(a)
		suf := make([]int, n)
		suf[n-1] = a[n-1]
		curSum := a[n-1]
		for i := n - 2; i >= 0; i-- {
			v := a[i]
			curSum = max(curSum+v, v)
			suf[i] = max(suf[i+1], curSum)
		}
		curSum, pre := a[0], a[0]
		ans := pre + suf[1+gap]
		for i := 1; i < n-1-gap; i++ {
			v := a[i]
			curSum = max(curSum+v, v)
			pre = max(pre, curSum)
			ans = max(ans, pre+suf[i+1+gap])
		}
		return ans
	}

	// 最大子序列交替和（买卖股票）
	// 有两种思路：
	// 1. 动态规划，具体见我的题解 https://leetcode.cn/problems/maximum-alternating-subsequence-sum/solution/dong-tai-gui-hua-by-endlesscheng-d92a/
	// 2. 贪心，由于第一个值需要取正，将开头补上 0，就变成买卖股票问题了，只需关心波峰和波谷的值，即 ∑max(0,a[i+1]-a[i])
	// LC1911 https://leetcode.cn/problems/maximum-alternating-subsequence-sum/
	// 变形 LC1526 https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
	// LC122 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
	// 扩展：O(1) 回答交换其中两个元素后的最大子序列交替和 https://codeforces.com/problemset/problem/1420/C2
	maxAlternatingSumDP := func(a []int) int {
		f := [2]int{0, -1e9}
		for _, v := range a {
			f = [2]int{max(f[0], f[1]-v), max(f[1], f[0]+v)}
		}
		return f[1]
	}

	maxAlternatingSumGreedy := func(a []int) (ans int) {
		a = append([]int{0}, a...)
		for i := 1; i < len(a); i++ {
			ans += max(0, a[i]-a[i-1])
		}
		return
	}

	// 修改序列为非降或非增的最小修改次数，单次修改可以把某个数 +1 或 -1（L1 error）
	// https://writings.sh/post/slope-trick-mono-sequence
	//
	// 注：如果是差值的平方（L2 error），那么是 isotonic regression / monotonic regression
	// https://en.wikipedia.org/wiki/Isotonic_regression
	// O(n) PAVA 算法 https://zhuanlan.zhihu.com/p/30747186
	//
	// 通过一个例子来解释这个基于堆的算法：1 5 10 4 2 2 2 2
	// 假设当前维护的是非降序列，前三个数直接插入，不需要任何修改
	// 插入 4 的时候，可以修改为 1 5 5 5，或 1 5 6 6，或... 1 5 10 10，修改次数均为 6
	// 但我们也可以把修改后的序列视作 1 5 4 4，虽然序列不为非降序列，但修改的次数仍然为 6
	// 接下来插入 2，基于 1 5 5 5 的话，修改后的序列就是 1 5 5 5 5，总的修改次数为 9
	// 但我们也可以把修改后的序列视作 1 2 4 4 2，总的修改次数仍然为 9
	// 接下来插入 2，如果基于 1 5 5 5 5 变成 1 5 5 5 5 5，会得到错误的修改次数 12
	// 但是实际上有更优的修改 1 4 4 4 4 4，总的修改次数为 11
	// 同上，把这个序列视作 1 2 2 4 2 2，总的修改次数仍然为 11
	// ...
	// LC2263 https://leetcode.cn/problems/make-array-non-decreasing-or-non-increasing/
	// https://codeforces.com/problemset/problem/13/C 2200
	// https://codeforces.com/problemset/problem/713/C 2300 严格单调递增 https://codeforces.com/blog/entry/47094?#comment-315161
	//     这道题做了一个 a[i]-=i 的操作（i 从 1 开始），把严格单调递增变成了非降的情况，从而可以应用该算法
	//     这一技巧的原理是，对于整数来说，单调递增的最小情况是 y=x+C，减去这一函数，就得到了非降序列的最小情况 y=C
	// https://codeforces.com/problemset/problem/1852/C 2400
	// https://codeforces.com/problemset/problem/1787/H 3300
	// https://www.luogu.com.cn/problem/P4597
	// https://www.luogu.com.cn/problem/P2893
	// http://poj.org/problem?id=3666
	slopeTrick := func(a []int) int {
		h := hp{} // 大根堆
		ans := 0
		for _, v := range a {
			h.push(v)
			if d := h.IntSlice[0] - v; d > 0 {
				ans += d
				h.IntSlice[0] = v
				heap.Fix(&h, 0)
			}
		}
		return ans
	}

	// 返回一个矩阵 f，其中 f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
	// https://leetcode.cn/problems/find-the-minimum-area-to-cover-all-ones-ii/
	// 类似题目【分三块】：
	// https://www.luogu.com.cn/problem/P3625 
	// - https://atcoder.jp/contests/abc347/tasks/abc347_f
	// https://atcoder.jp/contests/abc062/tasks/arc074_a
	minimumArea := func(a [][]int) [][]int {
		n, m := len(a), len(a[0])
		// f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
		f := make([][]int, n+1)
		for i := range f {
			f[i] = make([]int, m+1)
		}
		type data struct{ top, left, right int }
		border := make([]data, m)
		for j := range border {
			border[j].top = -1 // 无
		}

		for i, row := range a {
			left, right := -1, 0
			for j, x := range row {
				if x > 0 {
					if left < 0 {
						left = j
					}
					right = j
				}
				preB := border[j]
				if left < 0 { // 这一排目前全是 0
					f[i+1][j+1] = f[i][j+1] // 等于上面的结果
				} else if preB.top < 0 { // 这一排有 1，上面全是 0
					f[i+1][j+1] = right - left + 1
					border[j] = data{i, left, right}
				} else { // 这一排有 1，上面也有 1
					l, r := min(preB.left, left), max(preB.right, right)
					f[i+1][j+1] = (r - l + 1) * (i - preB.top + 1)
					border[j] = data{preB.top, l, r}
				}
			}
		}
		return f
	}

	// 最长公共子序列 (LCS)
	// 视频讲解：https://www.bilibili.com/video/BV1TM4y1o7ug/
	// 更快的做法（位运算）见 SPOJ LCS0 https://www.luogu.com.cn/problem/SP12076
	//
	// 模板题 LC1143 https://leetcode.cn/problems/longest-common-subsequence/
	// - 输出具体方案 https://atcoder.jp/contests/dp/tasks/dp_f
	// 编辑距离 LC72 https://leetcode.cn/problems/edit-distance/    
	// - 热身 LC161 https://leetcode.cn/problems/one-edit-distance/
	// - 输出具体方案 https://codeforces.com/problemset/problem/56/D 2100
	// - 进阶：编辑距离 + 可以交换相邻字母 https://codeforces.com/problemset/problem/67/C 2600
	// LC1092 最短公共超序列 (SCS) https://leetcode.cn/problems/shortest-common-supersequence/ 1977
	// LC1713 https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/ 2351 若其中一个序列无重复元素，可以转换成 LIS
	// - https://www.luogu.com.cn/problem/P1439 
	// https://codeforces.com/problemset/problem/163/A 1700 其中一个改为子串 
	// https://codeforces.com/problemset/problem/1446/B 1800
	// https://codeforces.com/problemset/problem/463/D 1900 多个排列的 LCS 
	// - https://www.luogu.com.cn/problem/P2364 三个字符串的 LCS + 输出方案 
	// https://codeforces.com/problemset/problem/1114/D 1900 转换【巧妙】
	// https://codeforces.com/problemset/problem/346/B 2000 与 KMP 结合 
	// - follow up: 要求某个子串 sub 一定在 LCS 中
	// https://codeforces.com/problemset/problem/1701/E 2500 状态机 DP / 前后缀分解
	// https://codeforces.com/problemset/problem/1584/F 2600 多串 + 每种字母至多出现两次 
	// - f[c][mask]，其中 mask 记录字母 c 在每个字符串中的出现位置，0 表示左边那个，1 表示右边那个
	// https://codeforces.com/problemset/problem/1366/G 2700 结合括号匹配，挖掘性质
	// https://codeforces.com/problemset/problem/1789/F 2700 分类讨论 多串
	// https://atcoder.jp/contests/abc185/tasks/abc185_e 权值
	// https://atcoder.jp/contests/abc130/tasks/abc130_e 相同子序列个数
	// https://atcoder.jp/contests/abc391/tasks/abc391_g DDP / DP of DP
	// - https://www.luogu.com.cn/problem/P10614
	// - https://www.luogu.com.cn/problem/P4590
	// 2020 多校第二场 https://acm.hdu.edu.cn/showproblem.php?pid=6774
	lcs := func(s, t []byte) int {
		// f[i][j] = LCS(s[:i], t[:j])
		n, m := len(s), len(t)
		f := make([][]int, n+1)
		for i := range f {
			f[i] = make([]int, m+1)
		}
		for i, v := range s {
			for j, w := range t {
				if v == w {
					f[i+1][j+1] = f[i][j] + 1
				} else {
					f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
				}
			}
		}

		// 输出具体方案
		lcs := make([]byte, 0, f[n][m])
		for i, j := n-1, m-1; i >= 0 && j >= 0; {
			if s[i] == t[j] {
				lcs = append(lcs, s[i])
				i--
				j--
			} else if f[i+1][j+1] == f[i][j+1] {
				i--
			} else {
				j--
			}
		}
		slices.Reverse(lcs)

		return f[n][m] // string(lcs)
	}

	// LCS 个数
	// https://www.luogu.com.cn/problem/P2516
	lcsCount := func(s, t []byte) int {
		const mod = 1_000_000_007
		n, m := len(s), len(t)
		lcs := make([][]int, n+1)
		count := make([][]int, n+1)
		for i := 0; i <= n; i++ {
			lcs[i] = make([]int, m+1)
			count[i] = make([]int, m+1)
		}
		for i := 0; i <= n; i++ {
			count[i][0] = 1
		}
		for j := 0; j <= m; j++ {
			count[0][j] = 1
		}
		for i := 1; i <= n; i++ {
			for j := 1; j <= m; j++ {
				if s[i-1] == t[j-1] {
					lcs[i][j] = lcs[i-1][j-1] + 1
					count[i][j] = count[i-1][j-1] // 延续之前的子序列数
				} else {
					lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
				}
				if lcs[i][j] == lcs[i-1][j] {
					count[i][j] += count[i-1][j] // 加上不考虑 s2[j-1] 的子序列数
				}
				if lcs[i][j] == lcs[i][j-1] {
					count[i][j] += count[i][j-1] // 加上不考虑 s1[i-1] 的子序列数
				}
				if s[i-1] != t[j-1] && lcs[i][j] == lcs[i-1][j-1] {
					count[i][j] -= count[i-1][j-1] // 避免重复子序列的统计
				}
				count[i][j] %= mod
			}
		}
		return (count[n][m] + mod) % mod
	}

	// 最长回文子序列 (LPS)
	// 见下面的「区间 DP」

	// 最长上升子序列 (LIS)
	// 视频讲解：https://www.bilibili.com/video/BV1ub411Q7sB/
	// 这种写法适用于一些定义比较复杂的变形题
	// O(n^2) - 定义 f[i] 为以 a[i] 为末尾的 LIS 的长度
	//          可以把此问题想象成一个「跳跃游戏」，任选一个初始位置向右跳跃，每次只能跳到比当前位置更高的位置，问最多能跳多少次（最后答案加一）
	//          这样能更容易地看出转移的顺序，然后变成一个 DAG 上求最长路的问题
	// 转换 http://acm.hdu.edu.cn/showproblem.php?pid=1950
	// 变体 https://codeforces.com/problemset/problem/1350/B 1400
	// todo 转换 https://codeforces.com/problemset/problem/1562/E
	//【网络流 24 题】能取出多少个长为 len(LIS) 的不相交子序列 https://loj.ac/p/6005 https://www.luogu.com.cn/problem/P2766
	lisSlow := func(a []int) int {
		n := len(a)
		f := make([]int, n)
		for i, v := range a {
			f[i] = 1
			for j, w := range a[:i] {
				if w < v { // 改成 <= 为非降
					f[i] = max(f[i], f[j]+1)
				}
			}
		}
		return slices.Max(f)
	}

	// 最长上升子序列 (LIS)   最长递增子序列
	// 视频讲解：https://www.bilibili.com/video/BV1ub411Q7sB/
	// 方法一：二分
	// O(nlogn) - 定义 g[i] 为长度为 i+1 的上升子序列的末尾元素的最小值（技巧：交换 O(n^2) 定义中的状态与状态值）
	// 求下降，可以考虑取相反数
	// https://oi-wiki.org/dp/basic/#_12
	// 最小划分数 / 狄尔沃斯定理（Dilworth's theorem）https://en.wikipedia.org/wiki/Dilworth%27s_theorem
	//    偏序集的最少反链划分数等于最长链的长度
	// 随机排列 LIS 的长度期望 https://www.zhihu.com/question/266958886
	// On Range LIS Queries https://codeforces.com/blog/entry/111625 https://codeforces.com/blog/entry/111807 https://arxiv.org/pdf/0707.3619
	// - 推广到树上路径
	// 输出一个 LIS https://writings.sh/post/longest-increasing-subsequence-revisited#%E8%BE%93%E5%87%BA%E4%B8%80%E4%B8%AA%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97
	// - 更简单的做法是用线段树
	//
	// 模板题 LC300 https://leetcode.cn/problems/longest-increasing-subsequence/
	// LC1964 https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/ 1933
	// 建模 https://codeforces.com/problemset/problem/269/B 1700
	// 经典转换（最多相交问题） https://codeforces.com/problemset/problem/67/D https://atcoder.jp/contests/arc126/tasks/arc126_b
	// 最小划分数（导弹拦截）https://www.luogu.com.cn/problem/P1020
	// - https://atcoder.jp/contests/abc134/tasks/abc134_e
	// - LC3231 https://leetcode.cn/problems/minimum-number-of-increasing-subsequence-to-be-removed/
	// 转化成最小划分数+打印划分方案 https://codeforces.com/problemset/problem/1296/E2
	// 合唱队形 https://www.luogu.com.cn/problem/P1091
	// LC1671 合唱队形（至少有升有降）https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/ 1913
	// 二维 LIS LC354 https://leetcode.cn/problems/russian-doll-envelopes/
	// 二维 LIS + 打印方案 https://codeforces.com/problemset/problem/4/D 1700
	// 重复数组的 LIS https://codeforces.com/problemset/problem/582/B 1900 非降
	// - todo https://codeforces.com/problemset/problem/261/D 2600 严格递增
	// - todo https://codeforces.com/contest/261/submission/31860735
	// 若其中一个序列无重复元素，LCS 可以转换成 LIS https://www.luogu.com.cn/problem/P1439 
	// - LC1713 https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/ 2351
	// 在一维 LIS 的基础上，a[i] 可以从多个数中选一个，问 LIS 最长可以多长
	// - 思路：将各个 a[i] 的可选项从大到小排序，然后拼接成一个序列，求 LIS 即可（关键：从大到小排序避免了在同一个可选项中选择多个元素）
	// 插入后最小化 LIS https://codeforces.com/problemset/problem/1893/B 1700
	// 图上的路径的 LIS https://codeforces.com/problemset/problem/960/F 2100
	// 将所有 a[i] 分成三类：不在任何 LIS 中 / 在至少一个 LIS 中 / 在所有 LIS 中 https://codeforces.com/problemset/problem/486/E 2200
	// - 详细证明 https://www.luogu.com.cn/article/m4267u8v
	// - （弱化版）在至少一个 LIS 中 https://atcoder.jp/contests/abc354/tasks/abc354_f
	// - 删除元素+Dilworth https://ac.nowcoder.com/acm/contest/3782/C
	// - 修改一个数后的最大 LIS https://atcoder.jp/contests/abc360/tasks/abc360_g
	// - 修改 2 个数呢？修改 k 个数呢？
	// - 多个询问，单点修改后计算 LIS https://codeforces.com/problemset/problem/650/D 2600
	// LaIS 与单调栈结合 https://codeforces.com/problemset/problem/1468/A 2200
	// 状态设计 LIS 计数 https://atcoder.jp/contests/abc237/tasks/abc237_f
	// 逆向题：输入 LIS 返回字典序最小的排列 a https://atcoder.jp/contests/arc125/tasks/arc125_c
	// 反向构造：构造一个 LIS 个数是 x 的数组
	// - 这里把 x 定义成非空 LIS 的个数。把 x 二进制拆分成 2^m1 + 2^m2 + 2^m3 + ... 
	// - 例如 13 = 2^3 + 2^2 + 2^0，我们可以构造 91,91,92,92,93,93,81,82,82,83,83,71,72,73，
	// - 看成三段，每一段的贡献就是前面拆分出的二进制数（这里只是举了个例子，每一段的 gap 可以调大一些以满足构造要求）
	// bitset 优化 https://codeforces.com/contest/1826/problem/E
	// 思想 https://codeforces.com/problemset/problem/1582/F1
	// https://codeforces.com/problemset/problem/249/D 2700
	// https://atcoder.jp/contests/arc159/tasks/arc159_d 区间 LIS（思路类似珂朵莉树）
	// https://atcoder.jp/contests/arc149/tasks/arc149_b
	// https://atcoder.jp/contests/abc393/tasks/abc393_f
	lis := func(a []int) int {
		f := []int{}
		for _, v := range a {
			j := sort.SearchInts(f, v) // 改成 v+1 为非严格递增
			if j < len(f) {
				f[j] = v
			} else {
				f = append(f, v)
			}
		}
		return len(f)
	}

	// 方法二：线段树优化 DP
	// 在值域上建一棵线段树，单点维护的是 a[i] 对应的 dp 值，区间维护的就是一段值域的 dp 的最大值
	// 转移时，查询 < a[i] 的最大值，单点更新到线段树的 a[i] 上
	// 这种做法也可以做到 O(nlogn)，且更加灵活
	// https://www.acwing.com/problem/content/description/3665/
	// LC2407 https://leetcode.cn/problems/longest-increasing-subsequence-ii/

	// 方法三：平衡树
	// 参考 https://leetcode.cn/problems/longest-increasing-subsequence-ii/solution/jianjie-by-xing-chen-26-ydqp/

	// 方法四：分治 + 单调队列
	// 参考 https://leetcode.cn/problems/longest-increasing-subsequence-ii/solution/fen-zhi-by-heltion-h31y/

	// 每个前缀的 LIS
	// LC1964 https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/ 1933
	lisAll := func(a []int) []int {
		n := len(a)
		lis := make([]int, n)
		g := []int{}
		for i, v := range a {
			p := sort.SearchInts(g, v) // 改成 v+1 为非严格递增
			if p < len(g) {
				g[p] = v
			} else {
				g = append(g, v)
			}
			lis[i] = p + 1
		}
		return lis
	}

	// 修改 a 中至多 k 个数后的 LIS 长度
	// k=1 https://atcoder.jp/contests/abc360/tasks/abc360_g
	lisModify := func(a []int, k int) int {
		f := make([][]int, k+1)
		for i := range f {
			f[i] = []int{math.MinInt} // 哨兵
		}
		for _, v := range a {
			for i := k; i >= 0; i-- {
				j := sort.SearchInts(f[i], v)
				if j < len(f[i]) {
					f[i][j] = v
				} else {
					f[i] = append(f[i], v)
				}
				if i > 0 {
					// 注意这里没有二分，完全取决于 len(g)
					g := f[i-1]
					j = len(g)
					w := g[len(g)-1] + 1
					if j < len(f[i]) {
						f[i][j] = min(f[i][j], w)
					} else {
						f[i] = append(f[i], w)
					}
				}
			}
		}

		ans := 0
		for _, g := range f {
			ans = max(ans, len(g)-1) // 减去哨兵
		}
		return ans
	}

	// 撤销 LIS
	// https://www.lanqiao.cn/problems/2088/learning/ https://www.luogu.com.cn/problem/P8776
	lisRollback := func(a []int) {
		pre := []int{}
		type pair struct{ i, v int }
		rollback := make([]pair, len(a))
		for i, v := range a {
			j := sort.SearchInts(pre, v)
			if j < len(pre) {
				rollback[i] = pair{j, pre[j]}
				pre[j] = v
			} else {
				rollback[i] = pair{j, -1} // 注意题目是否有负数
				pre = append(pre, v)
			}
		}

		for i := len(a) - 1; i >= 0; i-- {
			p := rollback[i]
			if p.v < 0 {
				pre = pre[:len(pre)-1]
			} else {
				pre[p.i] = p.v
			}
			// ...
		}
	}

	// LIS 方案数 O(nlogn)
	// 原理见下面这题官方题解的方法二
	// LC673 https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
	// https://www.luogu.com.cn/problem/P1108
	cntLis := func(a []int) int {
		g := [][]int{}   // 保留所有历史信息
		cnt := [][]int{} // 个数前缀和
		for _, v := range a {
			p := sort.Search(len(g), func(i int) bool { return g[i][len(g[i])-1] >= v })
			c := 1
			if p > 0 {
				// 根据 g[p-1] 来计算 cnt
				i := sort.Search(len(g[p-1]), func(i int) bool { return g[p-1][i] < v })
				c = cnt[p-1][len(cnt[p-1])-1] - cnt[p-1][i]
			}
			if p == len(g) {
				g = append(g, []int{v})
				cnt = append(cnt, []int{0, c})
			} else {
				g[p] = append(g[p], v)
				cnt[p] = append(cnt[p], cnt[p][len(cnt[p])-1]+c)
			}
		}
		c := cnt[len(cnt)-1]
		return c[len(c)-1]
	}

	// LIS 相关构造题
	// https://codeforces.com/problemset/problem/1304/D
	// https://atcoder.jp/contests/arc091/tasks/arc091_c

	// 最大上升子序列和
	// 按值从小到大排序，值相同的下标从大到小排序
	// 然后用树状数组或线段树：单点更新，维护前缀最大值
	// https://www.acwing.com/problem/content/3665/

	// 最长公共上升子序列 (LCIS)
	// https://www.acwing.com/problem/content/274/
	// https://codeforces.com/problemset/problem/10/D
	lcis := func(a, b []int) int {
		n, m := len(a), len(b)
		f := make([][]int, n+1)
		for i := range f {
			f[i] = make([]int, m)
		}
		for i, v := range a {
			mx := 0
			for j, w := range b {
				if v == w {
					f[i+1][j] = mx + 1
				} else {
					f[i+1][j] = f[i][j]
				}
				if w < v {
					mx = max(mx, f[i][j])
				}
			}
		}
		return slices.Max(f[n])
	}

	// LCIS 打印方案
	lcisPath := func(a, b []int) (ans int, lcis []int) {
		n, m := len(a), len(b)
		f := make([][]int, n+1)
		fa := make([][]int, n+1)
		for i := range f {
			f[i] = make([]int, m)
			fa[i] = make([]int, m)
		}
		for i, v := range a {
			mx, k := 0, -1
			for j, w := range b {
				if v == w {
					f[i+1][j] = mx + 1
					fa[i+1][j] = k // k < j
				} else {
					f[i+1][j] = f[i][j]
					fa[i+1][j] = j
				}
				if w < v && f[i][j] > mx {
					mx, k = f[i][j], j
				}
			}
		}
		ansJ := 0
		for j, fv := range f[n] {
			if fv > f[n][ansJ] {
				ansJ = j
			}
		}
		ans = f[n][ansJ]
		var getLCIS func(i, j int)
		getLCIS = func(i, j int) {
			if i == 0 || j < 0 {
				return
			}
			getLCIS(i-1, fa[i][j])
			if fa[i][j] < j {
				lcis = append(lcis, b[j])
			}
		}
		getLCIS(n, ansJ)
		return
	}

	// 长度为 m 的 LIS 个数
	// 赤壁之战 https://www.acwing.com/problem/content/299/
	// 定义 f[i][j] 表示 a[:j+1] 的长度为 i 且以 a[j] 结尾的 LIS
	// 则有 f[i][j] = ∑f[i-1][k]  (k<j && a[k]<a[j])
	// 注意到当 j 增加 1 时，只多了 k=j 这一个新决策，这样可以用树状数组来维护
	// 复杂度 O(mnlogn)
	countLIS := func(a []int, m int) int {
		// 将 a 离散化成从 2 开始的序列
		b := slices.Clone(a)
		slices.Sort(b)
		for i, v := range a {
			a[i] = sort.SearchInts(b, v) + 2
		}

		n := len(a)
		tree := make([]int, n+2)
		add := func(i, val int) {
			for ; i < len(tree); i += i & -i {
				tree[i] = (tree[i] + val) % mod
			}
		}
		sum := func(i int) (res int) {
			for ; i > 0; i &= i - 1 {
				res = (res + tree[i]) % mod
			}
			return
		}

		f := make([][]int, m+1)
		for i := range f {
			f[i] = make([]int, n)
		}
		for i := 1; i <= m; i++ {
			tree = make([]int, n+2)
			if i == 1 {
				add(1, 1)
			}
			for j, v := range a {
				f[i][j] = sum(v - 1)
				add(v, f[i-1][j])
			}
		}
		ans := 0
		for _, v := range f[m] {
			ans = (ans + v) % mod
		}
		return ans
	}

	// 合法子序列 DP
	// 本质不同非空子序列个数
	// 详细讲解见 https://leetcode.cn/problems/distinct-subsequences-ii/solution/xi-fen-wen-ti-fu-za-du-you-hua-pythonjav-1ihu/
	// - [940. 不同的子序列 II](https://leetcode.cn/problems/distinct-subsequences-ii/) 1985
	// - [1987. 不同的好子序列数目](https://leetcode.cn/problems/number-of-unique-good-subsequences/) 2422
	// 需要一点构造能力 https://codeforces.com/problemset/problem/645/E
	distinctSubsequence := func(s string) int {
		f := [26]int{}
		sumF := 0
		for _, b := range s {
			b -= 'a'
			tmp := (sumF + mod - f[b]) % mod
			f[b] = (sumF + 1) % mod
			sumF = (tmp + f[b]) % mod
		}
		// 把空的也算上
		//sumF = (sumF + 1) % mod
		return sumF
	}

	// 扩展：长度为 k 的本质不同子序列个数
	// 返回一个数组 f，f[k] 表示长度为 k 的本质不同子序列个数
	// https://codeforces.com/problemset/problem/1183/H
	// https://ac.nowcoder.com/acm/contest/4853/C 题解 https://ac.nowcoder.com/discuss/394080
	//distinctSubsequenceWithFixedLength := func(s string) []int {
	//	const mod int = 1e9 + 7
	//
	//	panic("impl me")
	//	//f := [26]int{}
	//	//
	//	//return sumF
	//}

	// 滚动数组写法
	distinctSubsequence = func(s string) int {
		last := make([]int, 26)
		f := 1
		for _, v := range s {
			v -= 'a'
			res := f - last[v]
			if res < 0 {
				res += mod
			}
			f = (f + res) % mod
			last[v] = (last[v] + res) % mod
		}
		return (f + mod - 1) % mod // 去掉空序列
	}

	// 回文串：中心扩展法
	// 原理见 https://leetcode.cn/problems/palindromic-substrings/solutions/379987/hui-wen-zi-chuan-by-leetcode-solution/
	// LC647 https://leetcode.cn/problems/palindromic-substrings/
	// LC2472 https://leetcode.cn/problems/maximum-number-of-non-overlapping-palindrome-substrings/
	// https://codeforces.com/problemset/problem/557/E
	// https://ac.nowcoder.com/acm/contest/64272/D
	palindromeO1Space := func(s string) {
		n := len(s)
		// i 为偶数表示奇回文串，i 为奇数表示偶回文串
		for i := range 2*n - 1 {
			// 从闭区间 [l,r] 开始向左右扩展
			l, r := i/2, (i+1)/2
			for l >= 0 && r < n && s[l] == s[r] {
				//cnt[r]++
				l--
				r++
			}
		}
	}

	// O(n^2) 求每个子串是否是回文的
	// 一般用于 DP 预处理
	// LC132 https://leetcode.cn/problems/palindrome-partitioning-ii/
	// https://codeforces.com/problemset/problem/835/D 1900
	isPalindrome := func(s string) [][]bool {
		n := len(s)
		isPal := make([][]bool, n)
		for i := range isPal {
			isPal[i] = make([]bool, n)
			for j := range isPal[i] {
				isPal[i][j] = true
			}
		}
		for l := n - 2; l >= 0; l-- {
			for r := l + 1; r < n; r++ {
				isPal[l][r] = s[l] == s[r] && isPal[l+1][r-1]
			}
		}
		return isPal
	}

	// 回文串最小分割次数
	// 紫书例题 9-7，UVa 11584 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2631
	// LC132 https://leetcode.cn/problems/palindrome-partitioning-ii/
	minPalindromeCut := func(s string) int {
		n := len(s)
		isP := make([][]bool, n)
		for i := range isP {
			isP[i] = make([]bool, n)
		}
		for l := n - 1; l >= 0; l-- {
			for r := l; r < n; r++ {
				isP[l][r] = s[l] == s[r] && (r-l < 3 || isP[l+1][r-1])
			}
		}

		f := make([]int, n)
		for i, prefixP := range isP[0] {
			if prefixP { // f[i] = 0
				continue
			}
			f[i] = int(1e9)
			for j := 0; j < i; j++ {
				if isP[j+1][i] {
					f[i] = min(f[i], f[j]+1)
				}
			}
		}
		return f[n-1]
	}

	/* 背包问题

	0-1 背包 0-1 Knapsack
	完全背包  Unbounded Knapsack
	多重背包  Bounded Knapsack

	这类问题可以从物品选择次序的无后效性入手
	子区间 -> 前缀和
	子序列 -> 背包
	https://en.wikipedia.org/wiki/Knapsack_problem
	https://codeforces.com/blog/entry/59606
	浅谈 ZKP 问题 https://www.luogu.com.cn/blog/xww666/qian-tan-zkp-wen-ti-gai-post
	另见 math_ntt.go 中的生成函数

	O(n√nw) 的 shuffle 做法（这里 w=max(wi)）
	https://codeforces.com/blog/entry/50036 https://codeforces.com/contest/739/problem/E
	https://arxiv.org/pdf/2308.11307.pdf
	http://acm.hdu.edu.cn/showproblem.php?pid=6804

	NOTE: 若求能否凑成 1,2,3,...,M，只需判断 f[i] 是否为正 LC1049 https://leetcode.cn/problems/last-stone-weight-ii/
	套题 https://www.acwing.com/problem/
	混合背包 https://www.luogu.com.cn/problem/P1833
	*/

	// 0-1 背包 (n 个物品，背包容量为 maxW)   0-1 Knapsack
	// 视频讲解：https://www.bilibili.com/video/BV16Y411v7Y6/
	// 状态：从前 i 个物品中选择若干个，当容量限制为 j 时能获得的最大价值和  i∈[0,n-1], j∈[0,maxW]
	// 初始值：f(0,j)=0  j∈[0,maxW]
	// 除了初始状态，每个状态有两个来源，取最大值：
	// - 不选第 i 个物品：f(i-1,j) -> f(i,j)
	// - 选第 i 个物品：f(i-1,j-wi)+vi -> f(i,j)   j≥wi
	// 答案为 f(n-1,maxW)
	// https://oi-wiki.org/dp/knapsack/
	// 关于「超大背包问题」见 search.go
	//
	// https://www.luogu.com.cn/problem/P1048 模板题 
	// https://www.luogu.com.cn/problem/P2871 模板题 
	// https://atcoder.jp/contests/dp/tasks/dp_d 模板题 
	// https://atcoder.jp/contests/dp/tasks/dp_x 转换
	// https://atcoder.jp/contests/abc274/tasks/abc274_d 转换
	// https://atcoder.jp/contests/abc281/tasks/abc281_d 二维
	// https://atcoder.jp/contests/abc192/tasks/abc192_f 枚举+二维
	// https://codeforces.com/problemset/problem/212/E 1500
	// https://codeforces.com/problemset/problem/1516/C 1700 转换
	// https://codeforces.com/problemset/problem/2086/D 1700
	// https://codeforces.com/problemset/problem/1381/B 1800 转换
	// https://codeforces.com/problemset/problem/577/B 1900 抽屉原理
	// https://codeforces.com/problemset/problem/687/C 1900 恰好组成 k 的数中能恰好组成哪些数
	// https://codeforces.com/problemset/problem/864/E 2000 打印方案
	// https://atcoder.jp/contests/abc383/tasks/abc383_f 1706=CF2001 深刻理解 0-1 背包 & 完全背包
	// https://codeforces.com/problemset/problem/981/E 2200 转移对象是下标
	// https://codeforces.com/problemset/problem/1203/F2 2300 排序+转换
	// 正难则反 https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_d 2237=CF2403
	// - 我的题解 https://www.luogu.com.cn/article/b0q3ju8h
	// - 类似思路 https://codeforces.com/problemset/problem/1487/G 2700
	// 转移对象是下标 https://codeforces.com/edu/course/2/lesson/9/3/practice/contest/307094/problem/I
	// - f[i][j] 表示前 i 个数，凑成 j 的所有方案中，最小下标的最大值
	// - 变形，需要多加一个维度 https://atcoder.jp/contests/abc275/tasks/abc275_f
	// https://atcoder.jp/contests/abc159/tasks/abc159_f 贡献
	// https://atcoder.jp/contests/agc020/tasks/agc020_c 所有非空子集和的中位数
	// https://atcoder.jp/contests/dp/tasks/dp_x 邻项交换法
	// https://www.luogu.com.cn/problem/P1064 NOIP06·提高 金明的预算方案（也可以用树上背包做）
	// EXTRA: 恰好装满（相当于方案数不为 0）LC416 https://leetcode.cn/problems/partition-equal-subset-sum/
	//        必须定义成恰好装满（紫书例题 9-5，UVa 12563）https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=4008
	// EXTRA: 背包容量为 0 https://codeforces.com/problemset/problem/366/C 1900
	// EXTRA: 二维费用 LC474 https://leetcode.cn/problems/ones-and-zeroes/ https://www.luogu.com.cn/problem/P1507 
	// EXTRA: 把一个维度转换成 DP 的定义 https://codeforces.com/problemset/problem/837/D
	// EXTRA: 离散化背包 https://codeforces.com/contest/366/submission/61452111
	// EXTRA: 位运算背包 https://ac.nowcoder.com/acm/problem/270788 AND 和 OR 思路是一样的
	// 转换 https://leetcode.com/discuss/interview-question/2677093/Snowflake-oror-Tough-OA-question-oror-How-to-solve
	zeroOneKnapsack := func(values, weights []int, maxW int) int {
		// 至多装满
		f := make([]int, maxW+1)
		for i, w := range weights {
			v := values[i]
			// 这里 j 的初始值可以优化成前 i 个物品的重量之和（但不能超过 maxW）
			for j := maxW; j >= w; j-- {
				f[j] = max(f[j], f[j-w]+v)
			}
		}
		return f[maxW]
	}

	// 0-1 背包 EXTRA: 恰好装满
	// https://leetcode.cn/contest/sf-tech/problems/cINqyA/
	// 转换 二维费用 https://codeforces.com/problemset/problem/730/J
	zeroOneKnapsackExactlyFull := func(values, weights []int, maxW int) {
		f := make([]int, maxW+1)
		for i := range f {
			f[i] = -1e9 // -1e18
		}
		f[0] = 0
		for i, w := range weights {
			v := values[i]
			for j := maxW; j >= w; j-- {
				f[j] = max(f[j], f[j-w]+v)
			}
		}
		for i := maxW; i >= 0; i-- {
			if f[i] >= 0 { // 能恰好装满 i，此时背包物品价值和的最大值是 f[i]
				// ...
			}
		}
	}

	// 0-1 背包 EXTRA: 至少装入重量和为 maxW 的物品，求价值和的最小值 https://www.luogu.com.cn/problem/P4377
	// f[0] 表示至少为 0 的情况，也表示没有任何约束的情况
	// 比如选第 i 个物品后容量 <=0 了，那就表示前面的 i-1 个物品可以不受约束地随意选或不选了
	// 转换 https://codeforces.com/problemset/problem/19/B LC2742 https://leetcode.cn/problems/painting-the-walls/
	// 二维费用的情况+价值最小 https://ac.nowcoder.com/acm/contest/6218/C
	zeroOneKnapsackAtLeastFillUp := func(values, weights []int, maxW int) int {
		f := make([]int, maxW+1)
		for i := range f {
			f[i] = 1e9 // 1e18
		}
		f[0] = 0 // 无任何限制
		for i, v := range values {
			w := weights[i]
			for j := maxW; j >= 0; j-- {
				f[j] = min(f[j], f[max(j-w, 0)]+v) // 如果 j <= w，那么选之后没有任何限制，所以从 f[0] 转移过来
			}
		}

		{
			// 另一种写法
			for i, v := range values {
				w := weights[i]
				for j := maxW; j >= 0; j-- {
					k := min(j+w, maxW)
					f[k] = min(f[k], f[j]+v)
				}
			}
		}

		return f[maxW]
	}

	// 0-1 背包 EXTRA: 从序列 a 中选若干个数，使其总和为 sum 的方案数
	// 常见题目是算严格分拆（必须用不同数字） LC2787 https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/
	// - https://oeis.org/A000009
	// NOTE: 1,1,1,...1(32个1),s-32,s-31,...,s 可以让方案数恰好为 2^32
	// 二维+上限+下限 LC879 https://leetcode.cn/problems/profitable-schemes/
	// https://atcoder.jp/contests/arc060/tasks/arc060_a
	// https://codeforces.com/problemset/problem/1673/C
	// 转换 https://atcoder.jp/contests/abc169/tasks/abc169_f
	// 转换 https://codeforces.com/problemset/problem/478/D
	// 转换 LC494 https://leetcode.cn/problems/target-sum/
	// 转换 LC1434 https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/
	// 由于顺序不同也算方案，所以这题需要正序递推（爬楼梯）LC377 https://leetcode.cn/problems/combination-sum-iv/
	zeroOneWaysToSum := func(a []int, sum int) int {
		f := make([]int, sum+1)
		f[0] = 1
		for _, v := range a {
			for j := sum; j >= v; j-- {
				f[j] += f[j-v] // % mod
			}
		}
		return f[sum]
	}

	// 0-1 背包 EXTRA: 打印字典序最小的方案
	// 倒序遍历物品，同时用 fa 数组记录转移来源，这样跑完 DP 后，从第一个物品开始即可得到字典序最小的方案
	// https://www.acwing.com/problem/content/description/12/
	zeroOneKnapsackLexicographicallySmallestResult := func(values, weights []int, maxW int) (ans []int) {
		n := len(values)
		f := make([]int, maxW+1) // fill
		//f[0] = 0
		fa := make([][]int, n)
		for i := n - 1; i >= 0; i-- {
			fa[i] = make([]int, maxW+1)
			for j := range fa[i] {
				fa[i][j] = j // 注意：<w 的转移来源也要标上！
			}
			v, w := values[i], weights[i]
			for j := maxW; j >= w; j-- {
				if f[j-w]+v >= f[j] { // 注意这里要取等号，从而保证尽可能地从字典序最小的方案转移过来
					f[j] = f[j-w] + v
					fa[i][j] = j - w
				}
			}
		}
		for i, j := 0, maxW; i < n; {
			if fa[i][j] == j { // &&  weights[i] > 0      考虑重量为 0 的情况，必须都选上
				i++
			} else {
				ans = append(ans, i+1) // 下标从 1 开始
				j = fa[i][j]
				i++ // 完全背包的情况，这行去掉
			}
		}
		return
	}

	// 0-1 背包 EXTRA: 价值主导的 0-1 背包
	// 适用于背包容量很大，但是物品价值不高的情况
	// 把重量看成价值，价值看成重量，求同等价值下能得到的最小重量，若该最小重量不超过背包容量，则该价值合法。所有合法价值的最大值即为答案
	// 时间复杂度 O(n * sum(values)) 或 O(n^2 * maxV)
	// https://atcoder.jp/contests/dp/tasks/dp_e
	// https://codeforces.com/contest/1974/problem/E 1800
	// https://codeforces.com/contest/1650/problem/F 2200
	zeroOneKnapsackByValue := func(values, weights []int, maxW int) int {
		totValue := 0
		for _, v := range values {
			totValue += v
		}
		f := make([]int, totValue+1)
		for i := range f {
			f[i] = 1e18
		}
		f[0] = 0
		totValue = 0
		for i, v := range values {
			w := weights[i]
			totValue += v
			for j := totValue; j >= v; j-- {
				f[j] = min(f[j], f[j-v]+w)
			}
		}
		for i := totValue; ; i-- {
			if f[i] <= maxW {
				return i
			}
		}
	}

	// 完全背包   Unbounded Knapsack
	// 视频讲解 https://www.bilibili.com/video/BV16Y411v7Y6/
	// 更快的做法 https://www.zhihu.com/question/26547156/answer/1181239468
	// https://github.com/hqztrue/shared_materials/blob/master/codeforces/101064%20L.%20The%20Knapsack%20problem%20156ms_short.cpp
	// https://www.luogu.com.cn/problem/P1616
	// https://www.luogu.com.cn/problem/P2918 至少
	// https://www.luogu.com.cn/problem/P1450 容斥
	// https://codeforces.com/problemset/problem/632/E 2400
	// LC322 https://leetcode.cn/problems/coin-change/ 恰好装满 
	// LC1449 https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/ 恰好装满+打印方案 
	// 【脑洞】求极限：lim_{maxW->∞} f[maxW]/maxW
	unboundedKnapsack := func(values, weights []int, maxW int) int {
		f := make([]int, maxW+1) // fill
		//f[0] = 0
		for i, v := range values {
			w := weights[i]
			for j := w; j <= maxW; j++ {
				f[j] = max(f[j], f[j-w]+v)
			}
		}
		return f[maxW]
	}

	// 完全背包 EXTRA: 方案数
	// LC518 https://leetcode.cn/problems/coin-change-ii/
	// https://codeforces.com/problemset/problem/1673/C 1500
	// https://www.luogu.com.cn/problem/P1832
	// https://www.luogu.com.cn/problem/P6205（需要高精）
	unboundedWaysToSum := func(a []int, total int) int {
		f := make([]int, total+1)
		f[0] = 1
		for _, v := range a {
			for j := v; j <= total; j++ {
				f[j] = (f[j] + f[j-v]) % mod
			}
		}
		return f[total]
	}

	// 完全背包 EXTRA: 二维费用方案数
	// 注意：「恰好使用 m 个物品」这个条件要当成一种费用来看待
	// https://codeforces.com/problemset/problem/543/A

	// 多重背包   Bounded Knapsack
	// 模板题 https://codeforces.com/problemset/problem/106/C
	//       https://www.luogu.com.cn/problem/P1776
	// http://acm.hdu.edu.cn/showproblem.php?pid=2844 http://poj.org/problem?id=1742
	// https://www.luogu.com.cn/problem/P6771 http://poj.org/problem?id=2392
	// https://codeforces.com/contest/999/problem/F
	// https://codeforces.com/problemset/problem/95/E
	// https://atcoder.jp/contests/abc373/tasks/abc373_f 2018=CF2237 变形
	// https://www.luogu.com.cn/problem/P1833 多重背包+完全背包
	// - https://www.luogu.com.cn/problem/P1782
	// - https://www.luogu.com.cn/problem/P2851

	// 思考题：打印方案

	// 多重背包 - 未优化
	// 转换（价值主导）https://codeforces.com/problemset/problem/922/E（由于要取 min 所以不能用二进制优化）
	boundedKnapsack := func(stocks, values, weights []int, maxW int) int {
		n := len(stocks)
		f := make([][]int, n+1)
		for i := range f {
			f[i] = make([]int, maxW+1)
		}
		for i, num := range stocks {
			v, w := values[i], weights[i]
			for j := range f[i] {
				// 枚举选了 k=0,1,2,...num 个第 i 种物品
				for k := 0; k <= num && k*w <= j; k++ {
					f[i+1][j] = max(f[i+1][j], f[i][j-k*w]+k*v)
				}
			}
		}
		return f[n][maxW]
	}

	// 多重背包 - 优化 1 - 二进制优化
	// 常数小，可能比单调队列优化还快
	// 注意循环上界可以从 maxW 优化成 min(sum(w*num), maxW)
	boundedKnapsackBinary := func(stocks, values, weights []int, maxW int) int {
		f := make([]int, maxW+1) // 求最小就 fill inf
		for i, num := range stocks {
			v, w := values[i], weights[i]
			for pow2 := 1; num > 0; pow2 *= 2 {
				k := min(pow2, num)
				for j := maxW; j >= w*k; j-- {
					f[j] = max(f[j], f[j-w*k]+v*k) // 求最小改成 min
				}
				num -= k
			}
		}
		return f[maxW]
	}

	// 多重背包 - 优化 2 - 单调队列优化
	// 参考挑战 p.340
	// 时间复杂度 O(n*maxW)
	// 注意循环上界可以从 maxW 优化成 min(sum(w*num), maxW)
	boundedKnapsackMonotoneQueue := func(stocks, values, weights []int, maxW int) int {
		f := make([]int, maxW+1) // 求最小就 fill inf
		type pair struct{ maxF, j int }
		q := []pair{}
		for i, num := range stocks {
			v, w := values[i], weights[i]
			for rem := 0; rem < w; rem++ { // 按照 j%w 的结果，分组转移，rem 表示 remainder
				q = q[:0]
				// 为什么压缩维度了还可以正着枚举？因为转移来源都存到单调队列里面了，正序倒序都可以
				// 并且这样相比倒着枚举，不需要先往队列里面塞 num 个数据，更加简洁
				for j := 0; j*w+rem <= maxW; j++ {
					t := f[j*w+rem] - j*v
					for len(q) > 0 && t >= q[len(q)-1].maxF { // 求最小这里改成 <=
						q = q[:len(q)-1] // 及时去掉无用数据
					}
					q = append(q, pair{t, j})
					// 本质是查表法，q[0].maxF 就表示 f[(j-1)*w+r]-(j-1)*v, f[(j-2)*w+r]-(j-2)*v, …… 这些转移来源的最大值
					f[j*w+rem] = q[0].maxF + j*v // 把物品个数视作两个 j 的差（前缀和思想）
					if j-q[0].j == num {         // 至多选 num 个物品
						q = q[1:] // 及时去掉无用数据
					}
				}
			}
		}
		return f[maxW]
	}

	// 多重背包 - 求方案数 - 前缀和优化
	// 每个物品的体积都是 1
	// 如果题目要求每种物品至少选一个，可以把每个 cnts[i] 都减一，maxW 减去 len(cnts)，这样就转换成了每种物品至少选 0 个的情况了
	// 讲解 https://leetcode.cn/problems/find-the-original-typed-string-ii/solutions/2966856/zheng-nan-ze-fan-qian-zhui-he-you-hua-dp-5mi9/
	// https://atcoder.jp/contests/dp/tasks/dp_m
	// 挑战 pp.68-69 多重集组合数
	// 另见 math_comb.go 中的「多重集组合数」容斥做法
	// https://codeforces.com/problemset/problem/156/C 也可以用容斥
	boundedKnapsackWays := func(cnts []int, maxW int) int {
		// 从 len(cnts) 种物品中选出【至多】maxW 个物品的方案数
		// f[i+1][j] 表示从前 i 种物品中选【恰好】j 个物品的方案数（优化掉第一个维度）
		f := make([]int, maxW+1)
		f[0] = 1
		for _, c := range cnts {
			// 原地计算 f 的前缀和
			for j := 1; j <= maxW; j++ {
				f[j] = (f[j] + f[j-1]) % mod
			}
			// 计算子数组和
			for j := maxW; j > c; j-- {
				f[j] -= f[j-c-1] // 可能会算出负数，所以最后返回的时候要调整一下
			}
		}

		ans := 0
		for _, x := range f {
			ans += x
		}
		return (ans%mod + mod) % mod
	}

	// 多重背包 - 求方案数 - 同余前缀和优化
	// 第 i 种物品有 c 个，每个物品的体积都是 x，记录在 cnt 中
	// 讲解 https://leetcode.cn/problems/count-of-sub-multisets-with-bounded-sum/solution/duo-zhong-bei-bao-fang-an-shu-cong-po-su-f5ay/
	boundedKnapsackWays2 := func(a []int) []int {
		total := 0
		cnt := map[int]int{}
		for _, x := range a {
			total += x
			cnt[x]++
		}

		// total 表示背包容量
		f := make([]int, total+1)
		f[0] = cnt[0] + 1
		delete(cnt, 0)

		maxS := 0
		for x, c := range cnt {
			maxS += x * c
			// 同余前缀和
			for j := x; j <= maxS; j++ {
				f[j] = (f[j] + f[j-x]) % mod
			}
			for j := maxS; j >= x*(c+1); j-- {
				f[j] = (f[j] - f[j-x*(c+1)] + mod) % mod
			}
		}

		// f[j] 表示所选物品体积之和恰好为 j 的方案数
		// 注意 f[0]
		return f
	}

	// 分组背包·每组至多选一个（恰好选一个见后面）
	// https://www.acwing.com/problem/content/9/
	// https://atcoder.jp/contests/abc248/tasks/abc248_c 也可以用容斥或者生成函数做
	// https://www.luogu.com.cn/problem/P1757
	// LC2218 https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
	// https://codeforces.com/problemset/problem/148/E
	// todo 进一步优化 https://codeforces.com/problemset/problem/1442/D
	// 方案数（可以用前缀和优化）https://www.luogu.com.cn/problem/P1077
	groupKnapsack := func(groups [][]struct{ value, weight int }, maxW int) int {
		f := make([]int, maxW+1)
		for _, g := range groups {
			// 这里 j 的初始值可以优化成前 i 个组的每组最大重量之和（但不能超过 maxW）
			for j := maxW; j >= 0; j-- {
				for _, it := range g {
					v, w := it.value, it.weight
					if w <= j {
						// ！如果 it.w 可能为 0 则需要用 f[2][] 来滚动（或者保证每组至多一个 0 且 0 在该组最前面）
						f[j] = max(f[j], f[j-w]+v)
					}
				}
			}
		}
		return f[maxW]
	}

	// todo 撤销计数
	//  https://leetcode.cn/circle/article/YnZBve/

	// 分组背包·每组恰好选一个
	// 允许物品重量为 0
	// https://atcoder.jp/contests/abc240/tasks/abc240_c
	// LC1981 https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/
	// 与二分图染色结合 https://codeforces.com/problemset/problem/1354/E
	// 转换 https://codeforces.com/problemset/problem/1637/D
	groupKnapsackFill := func(groups [][]int, maxW int) []bool {
		f := make([]bool, maxW+1) // f[i][j] 表示能否从前 i 组物品中选出重量恰好为 j 的，且每组都恰好选一个物品
		f[0] = true
		for _, g := range groups {
		next:
			for j := maxW; j >= 0; j-- { // 这里 j 的初始值可以优化至前 i 组的最大元素值之和
				for _, w := range g {
					if w <= j && f[j-w] {
						f[j] = true
						continue next
					}
				}
				f[j] = false // 由于我们是滚动数组的写法，f[i][j] 无法满足时要标记成 false
			}
		}
		return f // f[j] 表示从每组恰好选一个，能否凑成重量 j
	}

	// 树上背包/树形背包/依赖背包 · 其一
	// 要求：对于每个选择的节点，其父节点一定要选
	// 等价表述：选一个包含根节点的连通块
	// 返回一个长为 n+1 的数组 f，其中 f[i] 表示在树上选 i 个节点的最大价值和
	//
	// 要求：子树 DP 数组长度 = O(子树大小)
	// 时间复杂度 O(n^2)
	// 横看成岭侧成峰，（转成二叉树看）对于每个节点，转移次数是左右子树大小的乘积
	// 所以每个点对会贡献（且只在 LCA 处贡献）一个转移，所以总的转移次数是 O(n^2)
	//
	// https://leetcode.cn/circle/discuss/t7l62c/ by heltion
	// https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/
	// https://blog.csdn.net/lyd_7_29/article/details/79854245
	// https://codeforces.com/blog/entry/100910
	// https://www.cnblogs.com/shaojia/p/15520224.html
	// https://snuke.hatenablog.com/entry/2019/01/15/211812
	// https://zhuanlan.zhihu.com/p/103813542
	//
	// https://www.luogu.com.cn/problem/P2014 [CTSC1997] 选课
	// - https://www.luogu.com.cn/problem/U53204 数据加强版
	// - 题解 https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/
	// - 题解 https://www.luogu.com/article/u0hf3jll
	// https://www.luogu.com.cn/problem/P1273 有线电视网
	// https://www.luogu.com.cn/problem/P2015 二叉苹果树
	// https://www.luogu.com.cn/problem/P1272 重建道路
	// - https://www.luogu.com.cn/problem/U53878 数据加强版
	// https://www.luogu.com.cn/problem/P4322 分数规划
	// https://codeforces.com/problemset/problem/815/C 2400
	treeKnapsack := func(g [][]int, a []int) []int {
		var dfs func(int, int) ([]int, int)
		dfs = func(v, fa int) ([]int, int) {
			f := make([]int, len(g)+1)
			f[1] = a[v]
			size := 1
			for _, w := range g[v] {
				if w == fa {
					continue
				}
				fw, sz := dfs(w, v)
				for i := size; i > 0; i-- { // 枚举在之前的子树（以及节点 v）中选了 i 个点。由于根节点 v 必选，所以写 i > 0 而不是 i >= 0
					for j, wCj := range fw { // 枚举在 w 子树中选了 j 个点
						f[i+j] = max(f[i+j], f[i]+wCj)
					}
				}
				size += sz
			}
			return f[:size+1], size
		}
		f, _ := dfs(0, -1)
		return f
	}

	// 另一种写法
	treeKnapsack = func(g [][]int, a []int) []int {
		var dfs func(int, int) ([]int, int)
		dfs = func(v, fa int) ([]int, int) {
			f := make([]int, len(g)+1)
			// 先处理 v 的所有子树
			size := 0
			for _, w := range g[v] {
				if w == fa {
					continue
				}
				fw, sz := dfs(w, v)
				for i := size; i >= 0; i-- { // 枚举在之前的子树中选了 i 个点
					for j, wCj := range fw { // 枚举在 w 子树中选了 j 个点
						// +1，留位置给一定要选的节点 v
						f[i+j+1] = max(f[i+j+1], f[i+1]+wCj)
					}
				}
				size += sz
			}
			// 后处理节点 v
			// 这种写法适用于更复杂度的题目
			// 比如把题目变形为，子树选了 k 个点，最终收益为一个复杂的式子，比如 f[k+1] = a[v] XOR (cost[v][k] + f[k] * f[k])，只需改下面的循环
			// 下面的式子是 f[k+1] = a[v] + f[k]
			// 由于上面平移了 1，所以实际是 f[k+1] = a[v] + f[k+1]
			size++
			for i := 1; i <= size; i++ {
				f[i] += a[v] // 节点 v 一定要选
			}
			return f[:size+1], size
		}
		f, _ := dfs(0, -1)
		return f
	}

	// 树上背包 · 其二
	// 类似其一，但物品有体积与价值，返回的数组与背包容量有关
	// 时间复杂度 O(nW)
	// 图解 https://loj.ac/d/3144 https://www.luogu.com.cn/article/kq00ov2b
	//
	// 模板题 https://loj.ac/p/160
	// 模板题 https://www.luogu.com.cn/problem/P1064 NOIP06·提高 金明的预算方案
	// EXTRA: https://www.luogu.com.cn/problem/P12136 蓝桥杯 2025 省赛 C++ B 组
	treeKnapsackWeighted := func(g [][]int, items []struct{ value, weight int }, root, maxW int) []int {
		// 我自创的一种实现。对于随机树（或者高度小的树），消耗的内存更少，跑得也更快
		var dfs func(int, int, []int) ([]int, int)
		dfs = func(v, fa int, pre []int) ([]int, int) {
			size := 1
			lastF := pre
			for _, w := range g[v] {
				if w == fa {
					continue
				}
				f, sz := dfs(w, v, lastF)
				lastF = f
				size += sz
			}
			// 循环结束后，lastF 再加上 p.value 就是「选 v」
			f := slices.Clone(pre) // 不选 v
			p := items[v]
			for j := maxW; j >= p.weight; j-- {
				f[j] = max(f[j], lastF[j-p.weight]+p.value) // 不选 vs 选
			}
			return f, size
		}
		f0 := make([]int, maxW+1) // 至多
		f, _ := dfs(root, -1, f0)
		return f
	}

	// 其他写法
	treeKnapsackWeighted = func(g [][]int, items []struct{ value, weight int }, root, maxW int) []int {
		f := make([][]int, 1, len(g))
		f[0] = make([]int, maxW+1) // 至多
		var dfs func(int, int) int
		dfs = func(v, fa int) int {
			size := 1
			for _, w := range g[v] {
				if w != fa {
					size += dfs(w, v)
				}
			}
			fv := slices.Clone(f[len(f)-size]) // 不选 v
			p := items[v]
			lastF := f[len(f)-1] // 选 v
			for j := maxW; j >= p.weight; j-- {
				fv[j] = max(fv[j], lastF[j-p.weight]+p.value)
			}
			f = append(f, fv)
			return size
		}
		dfs(root, -1)
		return f[len(f)-1] // 根节点的 DP 是最后算出来的
	}

	/* 划分型 DP ① 最优分割
	LC132 https://leetcode.cn/problems/palindrome-partitioning-ii/
	- 至多 k 个 https://codeforces.com/problemset/problem/137/D
	https://codeforces.com/problemset/problem/1005/D 1500
	https://codeforces.com/problemset/problem/1714/D 1600 允许重叠 输出方案
	https://codeforces.com/problemset/problem/825/F 2400 KMP
	https://www.luogu.com.cn/problem/P1874
	https://www.luogu.com.cn/problem/P2627 需要优化
	*/
	splitDP := func(a, vals []int) {
		st := NewST(vals)
		// 左闭右开
		cost := func(l, r int) int {
			return st.Query(l, r)
		}

		n := len(a)
		f := make([]int, n+1)     // f[i] 表示 a[:i] 的最优值
		for i := 1; i <= n; i++ { // 子数组右开端点
			f[i] = math.MaxInt
			for l := i - 1; l >= 0; l-- { // 枚举子数组左闭端点
				f[i] = min(f[i], f[l]+cost(l, i))
			}
		}
	}

	/* 划分型 DP ② 分割段数约束
	将数组分成恰好（或至多）k 个连续子数组，求解与这些子数组有关的最优值
	一般定义 f[i][j] 表示将 a[:j] 分成 i 个连续子数组所得到的最优解
	此时可以枚举最后一个子数组的左端点 L，从 f[i-1][L] 转移到 f[i][j]，并考虑 a[L:j] 对最优解的影响
	时间复杂度（空间优化后）是 O((n-k*sz)k)
	部分题目可以用 WQS 二分（或者四边形不等式）优化
	https://leetcode.cn/problems/sum-of-k-subarrays-with-length-at-least-m/ 式子变形
	https://leetcode.cn/problems/minimum-operations-to-make-elements-within-k-subarrays-equal/
	https://codeforces.com/problemset/problem/1969/C 1700
	https://codeforces.com/problemset/problem/137/D 1900 输出具体方案
	- LC1278 https://leetcode.cn/problems/palindrome-partitioning-iii/
	https://codeforces.com/problemset/problem/643/C 2400 斜率优化
	https://codeforces.com/problemset/problem/797/F 2600
	https://www.luogu.com.cn/problem/P2679 2023.11.30 茶
	EXTRA: 相邻相关 LC3538 https://leetcode.cn/problems/merge-operations-for-minimum-travel-time/
	*/
	splitDPWithLimit := func(a, vals []int, k, sz int) int {
		st := NewST(vals)
		cost := func(l, r int) int {
			return st.Query(l, r)
		}

		// 选恰好 k 个子数组，每个子数组的长度恰好为 sz，代价为 cost(i,j)，左闭右开
		// 如果没有长度约束就视作 sz=1
		n := len(a)
		f := make([][]int, k+1)
		for i := range f {
			f[i] = make([]int, n+1)
		}
		for i := 1; i <= k; i++ {
			f[i][i*sz-1] = 1e18
			// 左右留出足够空间给其他子数组
			for j := i * sz; j <= n-(k-i)*sz; j++ { // 子数组右开端点
				// 不选 a[i] => f[i][j-1]
				// 选 a[i]   => f[i-1][l] + cost(l, j)    子数组为 [l, j)
				l := j - sz
				f[i][j] = min(f[i][j-1], f[i-1][l]+cost(l, j))
			}
		}
		return f[k][n]
	}

	/* 区间 DP
	一般来说转移是合并区间或者分解区间
	套路 https://www.luogu.com.cn/blog/BreakPlus/ou-jian-dp-zong-jie-ti-xie

	求解关于某个序列的最优性质，要求大区间的最优解可以依赖于小区间的最优解
	一般定义 f[i][j] 表示子数组 a[i] 到 a[j] 的最优解
	LC375 https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
	LC312 戳气球 https://leetcode.cn/problems/burst-balloons/
	LC664 打印机 https://leetcode.cn/problems/strange-printer/
	LC678 也有非 DP 做法 https://leetcode.cn/problems/valid-parenthesis-string/
	LC1312 插入形成回文 https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/ 1787
	- https://www.luogu.com.cn/problem/P1435
	LC3040 https://leetcode.cn/problems/maximum-number-of-operations-with-the-same-score-ii/
	LC1130 https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/ 1919
	LC1770 https://leetcode.cn/problems/maximum-score-from-performing-multiplication-operations/ 2068
	LC1547 https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/ 2116
	LC1039 最优三角剖分 https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/ 2130
	- 方案数 不保证凸 https://codeforces.com/problemset/problem/437/E 2500
	LC546 移除盒子 状态定义 https://leetcode.cn/problems/remove-boxes/ 从 CF 难度来看，这题可以评 2900（力扣难度）
	- 原题是紫书例题 9-27 https://www.luogu.com.cn/problem/UVA10559 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1500
	- https://codeforces.com/problemset/problem/1107/E 2400
	LC3018 https://leetcode.cn/problems/maximum-number-of-removal-queries-that-can-be-processed-i/ 会员题
	https://atcoder.jp/contests/abc163/tasks/abc163_e 贪心
	另见 LPS

	最短括号超序列 UVa1626 紫书例题 9-10 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4501
	容斥 https://atcoder.jp/contests/abc106/tasks/abc106_d
	https://codeforces.com/problemset/problem/245/H 1800
	https://codeforces.com/problemset/problem/1509/C 1800
	https://codeforces.com/problemset/problem/149/D 1900
	https://codeforces.com/problemset/problem/607/B 1900 回文消除
	- https://leetcode.cn/problems/palindrome-removal/ LC 抄袭 CF
	- https://codeforces.com/problemset/problem/150/D 2600 回文消除 每个长度有不同的权值
	染色【套路】https://codeforces.com/problemset/problem/1114/D 1900
	同色消除【套路】https://www.luogu.com.cn/problem/P4170
	             https://codeforces.com/problemset/problem/1132/F 2000
	https://codeforces.com/problemset/problem/1025/D 2100 状态设计
	https://codeforces.com/problemset/problem/2074/G 2100
	https://codeforces.com/problemset/problem/1336/C 2200 状态设计
	- https://www.luogu.com.cn/problem/P3205
	https://atcoder.jp/contests/arc183/tasks/arc183_c 2018=CF2237
	https://codeforces.com/problemset/problem/1198/D 2300 二维区间 DP
	https://codeforces.com/problemset/problem/1107/E 2400
	https://codeforces.com/problemset/problem/1863/F 2600
	todo https://atcoder.jp/contests/abc159/tasks/abc159_f
	https://blog.csdn.net/weixin_43914593/article/details/106163859 算法竞赛专题解析（14）：DP应用--区间DP
	*/

	// 最长回文子序列 (LPS)
	// 即 LCS(s, reverse(s))，证明见 https://www.zhihu.com/question/34580085
	// 视频讲解 https://www.bilibili.com/video/BV1Gs4y1E7EU/
	// 回文子串见下面的 isPalindrome 或者 strings.go 的 manacher
	// LC516 模板题 https://leetcode.cn/problems/longest-palindromic-subsequence/
	// LC730 求个数 https://leetcode.cn/problems/count-different-palindromic-subsequences/
	// LC1312 https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/ 1787
	//        - https://www.luogu.com.cn/problem/P1435
	// https://codeforces.com/problemset/problem/335/B 输出具体方案
	// 至多改 k 个字母 https://atcoder.jp/contests/agc021/tasks/agc021_d
	// todo 【需要复习】 树上路径 LPS https://codeforces.com/problemset/problem/1771/D 2100
	longestPalindromeSubsequence := func(s string) int {
		n := len(s)
		f := make([][]int, n)
		for i := range f {
			f[i] = make([]int, n)
		}
		for i := n - 1; i >= 0; i-- {
			f[i][i] = 1
			for j := i + 1; j < n; j++ {
				if s[i] == s[j] {
					f[i][j] = f[i+1][j-1] + 2
				} else {
					f[i][j] = max(f[i+1][j], f[i][j-1])
				}
			}
		}
		return f[0][n-1]
	}

	// 统计区间内回文串个数
	// 返回一个二维数组 f, f[i][j] 表示 s[i:j+1] 内的回文串的个数
	// https://codeforces.com/problemset/problem/245/H
	countPalindromes := func(s string) [][]int {
		n := len(s)
		f := make([][]int, n)
		for i := range f {
			f[i] = make([]int, n)
			f[i][i] = 1
			if i+1 < n && s[i] == s[i+1] {
				f[i][i+1] = 1
			}
		}
		for i := n - 3; i >= 0; i-- {
			for j := i + 2; j < n; j++ {
				if s[i] == s[j] {
					f[i][j] = f[i+1][j-1]
				}
			}
		}
		// 到这里为止，f[i][j] = 1 表示 s[i:j+1] 是回文串
		for i := n - 2; i >= 0; i-- {
			for j := i + 1; j < n; j++ {
				f[i][j] += f[i][j-1] + f[i+1][j] - f[i+1][j-1] // 容斥
			}
		}
		return f
	}

	// 石子合并
	// https://atcoder.jp/contests/dp/tasks/dp_n
	// https://ac.nowcoder.com/acm/contest/1043/A https://ac.nowcoder.com/acm/problem/51170
	// 环形的情况 https://www.luogu.com.cn/problem/P1880
	// 相邻 k 堆的情况（综合①②）LC1000 https://leetcode.cn/problems/minimum-cost-to-merge-stones/ 2423
	mergeStones := func(a []int) int {
		n := len(a)
		sum := make([]int, n+1)
		for i, v := range a {
			sum[i+1] = sum[i] + v
		}
		f := make([][]int, n)
		for i := range f {
			f[i] = make([]int, n)
			for j := range f[i] {
				f[i][j] = 1e9
			}
			f[i][i] = 0
		}
		for sz := 2; sz <= n; sz++ {
			for l := 0; l+sz <= n; l++ {
				r := l + sz - 1
				for i := l; i < r; i++ {
					f[l][r] = min(f[l][r], f[l][i]+f[i+1][r])
				}
				f[l][r] += sum[r+1] - sum[l]
			}
		}
		return f[0][n-1]
	}

	/* 环形 DP
	两种解题策略：
	一种是假设在 0 处断开，求一遍 DP，然后强制让 0 和 n-1 上是连通的，再求一遍 DP，取二者最值
	另一种是倍增链
	休息时间 https://www.luogu.com.cn/problem/P6064 https://www.acwing.com/problem/content/290/
	环路运输 https://www.acwing.com/problem/content/291/
	https://www.luogu.com.cn/problem/P1453
	*/

	/* 状态机 DP
	可以用网格图 DP 形象地理解，一般状态机都是 0->1->2 这种，类似只能向右/右下的网格图 DP
	https://atcoder.jp/contests/dp/tasks/dp_c 入门题
	https://atcoder.jp/contests/abc346/tasks/abc346_d
	https://codeforces.com/problemset/problem/327/A 1200
	https://codeforces.com/problemset/problem/1178/B 1300
	https://codeforces.com/problemset/problem/698/A 1400
	https://codeforces.com/problemset/problem/2033/C 1400
	https://codeforces.com/problemset/problem/855/B 1500
	https://codeforces.com/problemset/problem/2069/C 1500
	- LC1955 https://leetcode.cn/problems/count-number-of-special-subsequences/
	https://codeforces.com/problemset/problem/446/A 1600
	https://codeforces.com/problemset/problem/1826/D 1700 式子变形
	https://codeforces.com/problemset/problem/2029/C 1700
	https://codeforces.com/problemset/problem/404/D 1900
	https://codeforces.com/problemset/problem/1613/D 1900 爽
	https://codeforces.com/problemset/problem/623/B 2300
	https://codeforces.com/problemset/problem/1701/E 2500 LCS 变形题
	*/

	/* 分治 DP
	视频讲解 https://www.bilibili.com/video/BV1ne4y177wN/ 第四题
	https://leetcode.cn/contest/tianchi2022/problems/tRZfIV/
	- https://codeforces.com/contest/1442/problem/D
	*/

	/* 博弈 DP
	另见 games.go
	转移：让「自己与对手的分差」最大
	图上博弈 https://codeforces.com/problemset/problem/917/B
	LC464 https://leetcode.cn/problems/can-i-win/
	LC486 https://leetcode.cn/problems/predict-the-winner/
	LC877 https://leetcode.cn/problems/stone-game/ https://nanti.jisuanke.com/t/48
	LC913 https://leetcode.cn/problems/cat-and-mouse/
	LC1025 https://leetcode.cn/problems/divisor-game/
	LC1140 https://leetcode.cn/problems/stone-game-ii/
	LC1406 https://leetcode.cn/problems/stone-game-iii/
	CF tag https://codeforces.com/problemset?order=BY_RATING_ASC&tags=dp%2Cgames
	【记忆化搜索模板】https://codeforces.com/problemset/problem/1738/C
	https://www.lanqiao.cn/problems/8051/learning/?contest_id=146
	*/

	/* 概率 DP / 期望 DP
	https://oi-wiki.org/dp/probability/
	https://en.wikipedia.org/wiki/Probability
	https://en.wikipedia.org/wiki/Expected_value
	https://en.wikipedia.org/wiki/Variance
	https://en.wikipedia.org/wiki/Optional_stopping_theorem
	todo https://codeforces.com/blog/entry/62690
	     https://codeforces.com/blog/entry/62792
	 https://www.luogu.com.cn/blog/Troverld/gai-shuai-ji-wang-xue-xi-bi-ji
	 一类概率期望问题的杀器：势函数和鞅的停时定理 https://www.cnblogs.com/TinyWong/p/12887591.html https://codeforces.com/blog/entry/87598 最后一题
	 鞅与停时定理学习笔记 https://www.luogu.com.cn/blog/gxy001/yang-yu-ting-shi-ding-li-xue-xi-bi-ji
	todo 生成函数与期望 http://www.matrix67.com/blog/archives/4534
	方差 σ²(x) = sum(x²)/n - (sum(x)/n)²

	Secretary problem 秘书问题、37% 法则、麦穗理论、相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题
	https://en.wikipedia.org/wiki/Secretary_problem
	https://en.wikipedia.org/wiki/Optimal_stopping 最佳停止问题

	期望的可加性
	https://zhidao.baidu.com/question/259203053.html

	马尔可夫链 Markov chain https://en.wikipedia.org/wiki/Markov_chain
	吸收马尔可夫链 Absorbing Markov chain https://en.wikipedia.org/wiki/Absorbing_Markov_chain
	https://www.bilibili.com/video/BV14y4y1S7ve
	切尔诺夫界 Chernoff bound https://en.wikipedia.org/wiki/Chernoff_bound
	https://leetcode.cn/problems/soup-servings/solutions/1982989/shou-lian-su-du-by-hqztrue-afba/

	概率 DP
	https://atcoder.jp/contests/dp/tasks/dp_i 入门题
	- 在本题中，选或不选不是人为决定的，而是由概率决定的
	https://codeforces.com/problemset/problem/16/E 1900
	https://codeforces.com/problemset/problem/540/D 1900
	https://codeforces.com/problemset/problem/678/E 2200
	https://codeforces.com/problemset/problem/2028/E 2300
	https://codeforces.com/problemset/problem/258/D 2600
	LC688 https://leetcode.cn/problems/knight-probability-in-chessboard/
	LC808 https://leetcode.cn/problems/soup-servings/
	LC837 https://leetcode.cn/problems/new-21-game/
	LC1227 数学题 https://leetcode.cn/problems/airplane-seat-assignment-probability/
	LC1230 https://leetcode.cn/problems/toss-strange-coins/
	LC1467 https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/
	剑指 Offer 60 https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/
	https://www.luogu.com.cn/problem/P2719 用组合数学做

	期望 DP
	https://atcoder.jp/contests/abc280/tasks/abc280_e 入门题
	https://atcoder.jp/contests/abc350/tasks/abc350_e
	- 如果状态转移左右两边都包含 f[i]，则需要移项化简
	https://atcoder.jp/contests/dp/tasks/dp_j
	https://www.luogu.com.cn/problem/P1365 有关连续相同字符长度的期望
	https://www.luogu.com.cn/problem/P4316
	- https://atcoder.jp/contests/abc144/tasks/abc144_f 可以删一条边
	https://www.luogu.com.cn/problem/P1850 好题，注意这句话：所有的申请只能在学期开始前一次性提交。我们不能在计算的过程中，根据当前位置，决策是否申请换课
	https://atcoder.jp/contests/abc326/tasks/abc326_e 后缀和优化
	todo https://codeforces.com/contest/1842/problem/G https://codeforces.com/blog/entry/117640
	https://codeforces.com/problemset/problem/2081/A 1800
	https://codeforces.com/problemset/problem/235/B 2000
	https://codeforces.com/problemset/problem/1753/C 2000
	https://codeforces.com/problemset/problem/1778/D 2100
	https://codeforces.com/problemset/problem/908/D 2200
	https://codeforces.com/problemset/problem/1097/D 2200
	https://codeforces.com/problemset/problem/1623/D 2300
	https://codeforces.com/problemset/problem/1824/B2 2300
	https://codeforces.com/problemset/problem/24/D 2400 高斯消元 托马斯算法
	https://codeforces.com/problemset/problem/498/B 2400
	https://codeforces.com/problemset/problem/698/C 2400
	https://codeforces.com/problemset/problem/494/C 2600
	https://codeforces.com/problemset/problem/1172/C2 2600
	https://codeforces.com/problemset/problem/1823/F 2600 树上随机游走
	https://codeforces.com/problemset/problem/1842/G 2800
	https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4dea Kick Start 2020 Round F Yeetzhee
	todo https://leetcode.cn/contest/ubiquant2022/problems/I3Gm2h/
	 https://ac.nowcoder.com/acm/contest/76681/J

	尾和公式
	E(x) = ∑i*P(x=i) = ∑P(x>=i)
	https://codeforces.com/problemset/problem/1623/D 2300
	https://codeforces.com/problemset/problem/1523/E 2600

	题单（待整理）https://www.luogu.com/paste/3cp2ob1v
	*/

	/* 状压 DP
	常用于处理包含排列的问题等
	NOTE: 若问题无法划分成小问题，必须考虑各种可能的情况，则可能是 NP 完全问题

	教你一步步思考状压 DP：从记忆化搜索到递推，附题单
	https://leetcode.cn/problems/beautiful-arrangement/solution/jiao-ni-yi-bu-bu-si-kao-zhuang-ya-dpcong-c6kd/

	状压 DP 本质上就是在集合与集合之间转移，所以一定要能熟练地把集合语言翻译成位运算
	推荐阅读《从集合论到位运算，常见位运算技巧分类总结！》https://leetcode.cn/circle/discuss/CaOJ45/

	浅谈状压 DP https://www.luogu.com.cn/blog/yijan/zhuang-ya-dp
	https://blog.csdn.net/weixin_43914593/article/details/106432695 算法竞赛专题解析（15）：DP应用--状态压缩DP

	题单
	https://www.luogu.com.cn/training/215#problems
	https://ac.nowcoder.com/acm/problem/collection/808
	https://ac.nowcoder.com/acm/problem/collection/810

	https://codeforces.com/problemset/problem/991/D 迷你状压
	https://atcoder.jp/contests/abc142/tasks/abc142_e 基础状压 DP
	https://atcoder.jp/contests/abc359/tasks/abc359_d
	LC1125 状压 0-1 背包 https://leetcode.cn/problems/smallest-sufficient-team/
	todo LCP82 https://leetcode.cn/problems/cnHoX6/
	https://www.luogu.com.cn/problem/P1879
	https://www.luogu.com.cn/problem/P2704 状态设计 三进制状压 DP（也可以算作枚举子集的子集，三进制子集的子集有 6^m 个）
	- 注：一般地，k 进制子集的子集有 [k*(k+1)/2]^m 个。由于各个位互相独立，每一位为 k 个数选 2 个数的「可重组合数」，即 C(k+1,2)
	    - 对于二进制来说，那个 3^m 中的 3 就是空集的子集个数 1 + 一个元素的子集个数 2
	- 注：这样思考可以推广到子集的子集的子集的……的个数，套多少层就是选多少个数
	https://codeforces.com/problemset/problem/16/E 1900 与概率 DP 结合
	https://codeforces.com/problemset/problem/401/D 2000
	https://codeforces.com/problemset/problem/453/B 2000 与质因数分解结合
	https://codeforces.com/problemset/problem/895/C 2000
	https://codeforces.com/problemset/problem/903/F 2200 轮廓线
	https://codeforces.com/problemset/problem/1316/E 2300 与排序贪心结合
	https://codeforces.com/problemset/problem/1955/H 2300
	https://codeforces.com/problemset/problem/698/C 2400 概率
	https://codeforces.com/problemset/problem/744/C 2400 状态设计
	https://codeforces.com/problemset/problem/543/C 2500 状态转移
	https://codeforces.com/problemset/problem/1209/E2 2500 循环移位
	https://codeforces.com/problemset/problem/599/E 2600 树上子集状压 DP
	https://codeforces.com/problemset/problem/662/C 2600 状态设计 也可以 FWT
	- https://atcoder.jp/contests/abc396/tasks/abc396_g
	https://codeforces.com/problemset/problem/1430/G 2600
	https://codeforces.com/problemset/problem/79/D 2800 BFS
	https://atcoder.jp/contests/abc359/tasks/abc359_d
	https://www.luogu.com.cn/problem/P5369 状态设计

	todo 汉密尔顿路径/回路 Hamiltonian path
	https://en.wikipedia.org/wiki/Hamiltonian_path
	https://en.wikipedia.org/wiki/Hamiltonian_path_problem

	DDP / DP of DP
	f 差分后如果只有 0 和 1，可以考虑状压差分数组
	https://atcoder.jp/contests/abc391/tasks/abc391_g LCS
	- https://www.luogu.com.cn/problem/P10614
	- https://www.luogu.com.cn/problem/P4590
	https://www.luogu.com.cn/problem/P4484 LIS

	求最大团/最大独立集的记忆化写法见 graph.go
	*/

	// 注：下面的任意排列 DP，也适用于非全排列（子集排列）的情况，因为在计算过程中，我们也计算出了子集排列的 DP

	// 任意排列 DP - 相邻无关（刷表法）
	// 适用于不需要知道上一个数的场景
	// 时间复杂度通常是 O(n*2^n)
	// 下面的写法常数是 1/2
	// LC526 https://leetcode.cn/problems/beautiful-arrangement/
	//    - https://oeis.org/A320843 Number of permutations sigma of {1,2,...,n} such that sigma(i) divides i or i divides sigma(i) for 1 <= i <= n
	// https://atcoder.jp/contests/dp/tasks/dp_o
	// https://atcoder.jp/contests/abc381/tasks/abc381_f 1739=CF2026 状态设计
	// https://atcoder.jp/contests/abc199/tasks/abc199_e 1814=CF2083
	// https://codeforces.com/problemset/problem/377/C 2200 枚举来源
	// https://codeforces.com/problemset/problem/743/E 2200 状态设计
	// https://codeforces.com/problemset/problem/1215/E 2200
	// https://codeforces.com/problemset/problem/1238/E 2200 式子变形
	// https://codeforces.com/problemset/problem/327/E 2300 卡常优化 另一种做法是折半枚举
	// todo https://codeforces.com/problemset/problem/744/C 2400 状态设计
	// https://codeforces.com/problemset/problem/1598/F 2400 合法括号字符串
	// https://codeforces.com/problemset/problem/1550/E 2500 状态设计
	// https://www.luogu.com.cn/problem/P3694 前缀和
	// LC3530 https://leetcode.cn/problems/maximum-profit-from-valid-topological-order-in-dag/ DAG 排列
	permDP := func(a []int, check func(int, int) bool) int {
		n := len(a)
		f := make([]int, 1<<n)
		// 求最小值的题目
		//for i := 1; i < len(f); i++ { f[i] = 1e18 }
		// 计数题目
		f[0] = 1
		for s, fs := range f { // 前面选的下标集合是 s
			if fs == 0 { // 剪枝：用在计数题目上
				continue
			}
			i := bits.OnesCount(uint(s))
			for cus, lb := len(f)-1^s, 0; cus > 0; cus ^= lb {
				lb = cus & -cus
				ns := s | lb
				// 枚举第 i 个位置填 a[p]
				p := bits.TrailingZeros(uint(lb))
				v := a[p]
				if check(i, v) {
					f[ns] = (f[ns] + fs) % mod
				}
			}
		}
		return f[len(f)-1]
	}

	// 任意排列 DP - 相邻相关（刷表法）
	// 适用于需要知道上一个数的场景
	// 时间复杂度通常是 O(n^2*2^n)
	// 下面的写法常数约为 1/4 https://oeis.org/A001815
	// https://codeforces.com/problemset/problem/1950/G 1900
	// https://codeforces.com/problemset/problem/1185/G1 2100
	// https://codeforces.com/problemset/problem/2051/G 2100
	permDP2 := func(a []int, check func(int, int) bool) int {
		n := len(a)
		f := make([][]int, 1<<n)
		for i := range f {
			f[i] = make([]int, n)
			// 求最小值的题目
			//for j := range f[i] { f[i][j] = 1e18 }
		}
		for j := range f[0] {
			f[1<<j][j] = 1 // 排列的第一个数
		}
		for s, fs := range f {
			for _s := uint(s); _s > 0; _s &= _s - 1 {
				i := bits.TrailingZeros(_s)
				if fs[i] == 0 { // 剪枝：用于计数题目，或子集排列题目
					continue
				}
				pre := a[i] // 枚举上一个选的数
				for cus, lb := len(f)-1^s, 0; cus > 0; cus ^= lb {
					lb = cus & -cus
					ns := s | lb
					j := bits.TrailingZeros(uint(lb))
					cur := a[j] // 枚举当前选的数
					if check(pre, cur) {
						f[ns][j] = (f[ns][j] + fs[i]) % mod
					}
				}
			}
		}
		ans := 0
		for _, fv := range f[len(f)-1] {
			ans = (ans + fv) % mod
		}
		return ans
	}

	// 旅行商问题  travelling salesman problem  TSP
	// 图论中的一个等价形式是：给定一个加权完全图（顶点表示城市，边表示道路，权重是道路的距离），求一权值和最小的哈密尔顿回路。
	// 返回一个 ans 数组，ans[i] 表示从 st 出发，访问完所有位置且最后停在 i 的最短路径（注意可能要特判 i==st 的情况）
	// 做法：定义 f[s][i] 表示已访问的集合为 s，最后一个访问的位置是 i 时的最小花费
	//      则有 f[s|1<<j][j] = min(f[s|1<<j][j], f[s][i]+dist[i][j])
	//      枚举 i 和 j 时可以用 TrailingZeros 来直接枚举每个 1 和 0 的位置
	// https://en.wikipedia.org/wiki/Travelling_salesman_problem
	// https://en.wikipedia.org/wiki/Hamiltonian_path HCP
	//
	// 模板题 https://www.luogu.com.cn/problem/P1171 
	//       https://www.luogu.com.cn/problem/P1433 
	//       回路 https://atcoder.jp/contests/abc180/tasks/abc180_e
	//       https://www.acwing.com/problem/content/93/
	//
	// 额外的起点和终点 https://atcoder.jp/contests/abc301/tasks/abc301_e
	// 略微变形 吃加速药水 https://atcoder.jp/contests/abc274/tasks/abc274_e
	// 恰好访问 m 个点 https://codeforces.com/contest/580/problem/D 1800
	// 变体+打印路径 https://codeforces.com/problemset/problem/8/C 2000
	// 矩阵交换行问题 https://codeforces.com/problemset/problem/1102/F
	// EXTRA: 固定起点终点的问题，视问题情况有两种方法：
	//        添加一个节点 https://stackoverflow.com/questions/14527815/how-to-fix-the-start-and-end-points-in-travelling-salesmen-problem
	//        设置距离 https://stackoverflow.com/questions/36086406/traveling-salesman-tsp-with-set-start-and-end-point
	tsp := func(dist [][]int, st int) []int {
		const inf int = 1e9 // 1e18
		f := make([][]int, 1<<len(dist))
		for i := range f {
			f[i] = make([]int, len(dist))
			for j := range f[i] {
				f[i][j] = inf
			}
		}
		// 如果有多个起点的话就初始化多个 f[1<<st[i]][st[i]] = 0
		// 如果有超级源点 src，那么初始化 f[1<<st[i]][st[i]] = dis[src][st[i]]
		// 如果有超级汇点 dst，最后答案为 min(f[-1][i]+dis[i][dst])
		f[1<<st][st] = 0
		for s, fs := range f {
			// 利用位运算快速求出 s 中 1 的位置 i，以及 s 中 0 的位置 j（通过 s 的补集中的 1 的位置求出）
			for _s := uint(s); _s > 0; _s &= _s - 1 {
				i := bits.TrailingZeros(_s)
				if fs[i] == inf {
					continue
				}
				for cus, lb := len(f)-1^s, 0; cus > 0; cus ^= lb {
					lb = cus & -cus
					ns := s | lb
					j := bits.TrailingZeros(uint(lb))
					f[ns][j] = min(f[ns][j], fs[i]+dist[i][j])
				}
			}
		}
		return f[len(f)-1]
	}

	// 无向图最长简单路径
	// 输入的 g 是邻接矩阵，第二维度压缩成一个 int
	// https://codeforces.com/contest/1950/problem/G
	longestSimplePath := func(g []int) int {
		n := len(g)
		f := make([][]int, 1<<n)
		for i := range f {
			f[i] = make([]int, n)
		}
		for j := range f[0] {
			f[1<<j][j] = 1
		}
		ans := 1
		for s, fs := range f {
			for _s := uint(s); _s > 0; _s &= _s - 1 {
				i := bits.TrailingZeros(_s)
				if fs[i] == 0 {
					continue
				}
				for cus, lb := g[i]&^s, 0; cus > 0; cus ^= lb {
					lb = cus & -cus
					ns := s | lb
					j := bits.TrailingZeros(uint(lb))
					f[ns][j] = max(f[ns][j], fs[i]+1)
					ans = max(ans, f[ns][j])
				}
			}
		}
		return ans
	}

	// 无向图简单环数量
	// https://blog.csdn.net/fangzhenpeng/article/details/49078233
	// https://codeforces.com/problemset/problem/11/D
	countCycle := func(g [][]int, n, m int) int {
		ans := 0
		// 取集合 s 的最小值作为起点
		f := make([][]int, 1<<n)
		for i := range f {
			f[i] = make([]int, n)
		}
		for i := 0; i < n; i++ {
			f[1<<i][i] = 1
		}
		for s := range f {
			for v, fs := range f[s] {
				if fs == 0 {
					continue
				}
				for _, w := range g[v] {
					if 1<<w < s&-s {
						continue
					}
					if 1<<w&s == 0 {
						f[s|1<<w][w] += fs
					} else if 1<<w == s&-s {
						ans += fs
					}
				}
			}
		}
		return ans - m/2
	}

	// 枚举子集的子集
	// 复杂度 O(3^n)，证明：元素个数为 k 的集合有 C(n,k) 个，其子集有 2^k 个，故有 ∑C(n,k)*2^k = (2+1)^n = 3^n
	// 例如：f[set] = max{f[set^sub] + sum of sub} for all valid sub
	//
	// 模板题 https://atcoder.jp/contests/dp/tasks/dp_u
	// https://www.luogu.com.cn/problem/P1896 棋盘放 k 个将，不能互相攻击
	// - [1723. 完成所有工作的最短时间](https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs/) 2284 *子集划分型
	// - [1349. 参加考试的最大学生数](https://leetcode.cn/problems/maximum-students-taking-exam/) 2386
	//    - https://codeforces.com/contest/1926/problem/F
	// - [1681. 最小不兼容性](https://leetcode.cn/problems/minimum-incompatibility/) 2390 有 O(n^2*2^n) 做法
	//    - 相关（不是状压） https://codeforces.com/contest/626/problem/F
	// - [2572. 无平方子集计数](https://leetcode.cn/problems/count-the-number-of-square-free-subsets/) 2420
	//    - 也可以用 01 背包 / 枚举 square-free
	//    - 更快的做法 https://leetcode.cn/problems/count-the-number-of-square-free-subsets/solution/shu-zhi-fan-wei-zai-da-yi-dian-de-hua-ze-56w3/
	//    - 把相同的大质数归类，避免重复选择（分组背包）
	// todo https://codeforces.com/problemset/problem/1556/F 2500
	// 训练指南第一章例题 29，UVa11825 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2925
	//    - 将 n 个集合分成尽量多组，使得对于每组，组内所有集合的并集等于全集
	// 训练指南第一章例题 32，WF10，UVa1099 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=245&page=show_problem&problem=3540
	// https://codeforces.com/problemset/problem/599/E 2600 树上子集状压 DP
	// https://atcoder.jp/contests/arc171/tasks/arc171_d 转换 图染色
	subsubDP := func(a []int) int {
		n := len(a)
		m := 1 << n
		// 预处理每个子集的子集和
		sum := make([]int, m)
		// lcms[0] = 1
		for i, v := range a {
			highBit := 1 << i
			for mask, s := range sum[:highBit] {
				sum[highBit|mask] = s + v // + 可以换成其它运算，例如 gcd lcm 等
			}
		}
		f := make([]int, m)
		for s, fs := range f {
			t := m - 1 ^ s
			// 枚举 s 的补集 t 的非空子集
			for sub := t; sub > 0; sub = (sub - 1) & t {
				ss := s | sub
				f[ss] = max(f[ss], fs+sum[sub])
			}
		}

		// 另一种写法
		for j := 1; j < m; j++ {
			// 枚举 j 的所有非空子集 sub
			for sub := j; sub > 0; sub = (sub - 1) & j {
				f[j] = max(f[j], f[j^sub]+sum[sub])
			}
		}

		return f[m-1]
	}

	// 至多分成 k 组
	// https://atcoder.jp/contests/abc332/tasks/abc332_e
	subsubDP2 := func(a []int, k int) int {
		n := len(a)
		m := 1 << n
		// 预处理每个子集的子集和
		sum := make([]int, m)
		for i, v := range a {
			highBit := 1 << i
			for mask, s := range sum[:highBit] {
				sum[highBit|mask] = s + v
			}
		}
		f := make([]int, m)
		for i := 1; i < m; i++ {
			f[i] = 1e18
		}
		for range k {
			for s := m - 1; s >= 0; s-- {
				t := m - 1 ^ s
				// 枚举补集的非空子集
				for sub := t; sub > 0; sub = (sub - 1) & t {
					f[s|sub] = min(f[s|sub], f[s]+sum[sub])
				}
				f[s] = 1e18
			}
		}
		return f[m-1]
	}

	// 记忆化写法
	subsubDPMemo := func(a []int) int {
		n := len(a)
		m := 1 << n
		// 预处理每个子集的子集和
		sum := make([]int, m)
		for i, v := range a {
			highBit := 1 << i
			for mask, s := range sum[:highBit] {
				sum[highBit|mask] = s + v
			}
		}
		memo := make([][]int, n)
		for i := range memo {
			memo[i] = make([]int, 1<<m)
			for j := range memo[i] {
				memo[i][j] = -1
			}
		}
		const inf int = 1e9 // 1e18
		var dfs func(int, int) int
		dfs = func(i, set int) (res int) {
			if i == n {
				if set > 0 {
					return inf
				}
				return
			}
			dv := &memo[i][set]
			if *dv != -1 {
				return *dv
			}
			defer func() { *dv = res }()
			res = inf

			// 所有子集
			for sub, ok := set, true; ok; ok = sub != set {
				r := dfs(i+1, set^sub)
				res = min(res, r+sum[sub])
				sub = (sub - 1) & set
			}

			// 或者，所有非空子集
			for sub := set; sub > 0; sub = (sub - 1) & set {
				// 同上
			}

			return
		}
		return dfs(0, 1<<m-1)
	}

	// 高维前缀和 SOS DP (Sum over Subsets)
	// 给一个全集 U，对 U 的所有子集 S，计算 S 的所有子集 T 之和（这个「和」不一定是加法，可以是其它的满足合并性质的统计量，例如 max 等）
	// https://codeforces.com/blog/entry/45223
	// 本质理解 https://codeforces.com/blog/entry/72488 Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution
	// Some SOS DP Insights https://codeforces.com/blog/entry/105247
	// 大量习题 https://blog.csdn.net/weixin_38686780/article/details/100109753
	//
	// LC2732 https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/
	//    最简单的 SOSDP，判断是否有两个子集满足 x&y=0 且 idx[x]>=0 且 idx[y]>=0
	// https://codeforces.com/problemset/problem/1234/F
	//    求满足 ai&aj=0 的 ai|aj 的二进制 1 的个数的最大值
	//    由于 ai 的补集一定满足和 ai 的 & = 0
	//    所以转换成求每个 ai 的补集的 SOS，维护子集二进制 1 的个数的最大值
	// https://www.hackerearth.com/zh/problem/algorithm/special-pairs-5-3ee6b3fe-3d8a1606/
	//    求 ai&aj=0 的 (i,j) 对数，0<=ai<=1e6
	//    思路和上面类似，转换成求每个 ai 的补集的 SOS
	//    注：另一种解法是求 FWT(cnt)[0]
	// https://codeforces.com/problemset/problem/1208/F
	//    求 ai|(aj&ak) 的最大值，其中 i<j<k
	//    根据 a|b = (^a)&b + a
	//    问题变成 (^ai)&aj&ak + ai 的最大值
	// 转换成求集合中最大次大 https://atcoder.jp/contests/arc100/tasks/arc100_c
	// 求下标最大次大，且不需要在乎 k 的上限的写法 https://codeforces.com/problemset/problem/1554/B
	// https://codeforces.com/problemset/problem/165/E
	// 容斥 https://codeforces.com/problemset/problem/449/D
	// https://codeforces.com/problemset/problem/800/D
	// https://codeforces.com/problemset/problem/383/E
	// https://www.luogu.com.cn/problem/P6442
	// https://codeforces.com/problemset/problem/1523/D
	// 十进制 https://atcoder.jp/contests/arc136/tasks/arc136_d
	sosDP := func(a []int) []int {
		// 从子集转移的写法
		mx := bits.Len(uint(slices.Max(a)))
		f := make([]int, 1<<mx)
		for _, v := range a {
			f[v]++ // 初始值
		}
		for i := range mx {
			for s := 0; s < 1<<mx; s++ {
				s |= 1 << i // 直接跳到下一个目标位置
				// 将 s 的子集 s^1<<i 的统计量合并到 s 中
				f[s] += f[s^1<<i]
			}
		}

		{
			// 从超集转移的写法
			for i := range mx {
				for s := 1<<mx - 1; s >= 0; s-- {
					if s>>i&1 == 0 {
						f[s] += f[s|1<<i]
					}
				}
			}
		}

		{
			// 维护集合最大和次大的写法
			type pair struct{ fi, se int }
			f := make([]pair, 1<<mx)
			for i := range mx {
				for s := 0; s < 1<<mx; s++ {
					s |= 1 << i
					p, q := f[s], f[s^1<<i]
					if q.se > p.fi {
						f[s] = q
					} else if q.fi > p.fi {
						f[s] = pair{q.fi, p.fi}
					} else if q.fi > p.se {
						f[s].se = q.fi
					}
				}
			}
		}

		return f
	}

	/* 插头 DP（Plug DP）/ 轮廓线 DP（Broken Profile DP）
	轮廓线：已决策格子和未决策格子的分界线
	陈丹琦《基于连通性状态压缩的动态规划问题》
	训练指南 6.1
	https://oi-wiki.org/dp/plug/（花絮 https://zhuanlan.zhihu.com/p/133761303）
	https://cp-algorithms.com/dynamic_programming/profile-dynamics.html
	图解 https://www.luogu.com.cn/blog/GNAQ/solution-p5056
	An Introduction to Plug DP https://codeforces.com/blog/entry/90841
	todo 大量题目 https://www.luogu.com.cn/blog/efforts-will-pay-off/du-liu-dong-gui-cha-tou-dp
	模板题 https://www.luogu.com.cn/problem/P5056
	https://www.luogu.com.cn/problem/P3272
	https://www.luogu.com.cn/problem/P5074
	https://www.luogu.com.cn/problem/P1933
	https://codeforces.com/problemset/problem/903/F 2200
	LCP4 https://leetcode.cn/problems/broken-board-dominoes/
	*/
	plugDP := func(grids [][]byte) int {
		n, m := len(grids), len(grids[0])
		var endX, endY int
		g := make([][]bool, n)
		for i, row := range grids {
			g[i] = make([]bool, m)
			for j, b := range row {
				if b == '.' {
					g[i][j] = true
					endX, endY = i, j
				}
			}
		}

		// 四进制状态
		get := func(s, k int) int { return s >> (k << 1) & 3 }
		set := func(k, v int) int { return 1 << (k << 1) * v }

		ans := 0
		f := map[int]int{0: 1}
		for i, row := range g {
			tmp := f
			f = make(map[int]int, len(tmp))
			for s, dv := range tmp {
				f[s<<2] = dv // 轮廓线移动到当前行
			}
			for j, empty := range row {
				tmp := f
				f = make(map[int]int, len(tmp))
				for s, dv := range tmp {
					switch x, y := get(s, j), get(s, j+1); {
					case !empty: // 障碍格
						if x == 0 && y == 0 { // 空
							f[s] += dv
						}
					case x == 0 && y == 0: // ┌ 单独形成一对括号
						if j+1 < m && row[j+1] && i+1 < n && g[i+1][j] {
							f[s|set(j, 1)|set(j+1, 2)] += dv
						}
					case x == 0 && y > 0:
						if j+1 < m && row[j+1] { // └
							f[s] += dv
						}
						if i+1 < n && g[i+1][j] { // │
							f[s|set(j, y)^set(j+1, y)] += dv
						}
					case x > 0 && y == 0:
						if j+1 < m && row[j+1] { // ─
							f[s^set(j, x)|set(j+1, x)] += dv
						}
						if i+1 < n && g[i+1][j] { // ┐
							f[s] += dv
						}
					case x == 1 && y == 1: // ┘ 消去 x 和 y，并找到和 y 匹配的右括号，将其改成左括号
						// 注：这里和下边的 k 的位置可以事先预处理出来
						for k, c := j+2, 1; ; k++ {
							if t := get(s, k); t == 1 {
								c++
							} else if t == 2 {
								if c--; c == 0 {
									f[s^set(j, x)^set(j+1, y)^set(k, 3)] += dv // 将 2 改成 1 要异或 3
									break
								}
							}
						}
					case x == 2 && y == 2: // ┘ 消去 x 和 y，并找到和 x 匹配的左括号，将其改成右括号
						for k, c := j-1, 1; ; k-- {
							if t := get(s, k); t == 2 {
								c++
							} else if t == 1 {
								if c--; c == 0 {
									f[s^set(j, x)^set(j+1, y)^set(k, 3)] += dv // 将 1 改成 2 要异或 3
									break
								}
							}
						}
					case x == 2 && y == 1: // ┘ 消去右括号和左括号，连接两个插头
						f[s^set(j, x)^set(j+1, y)] += dv
					default: // ┘ x == 1 && y == 2
						// 此时封闭整个路径，这只应当发生在最后一个合法格子上
						if i == endX && j == endY {
							ans += dv
						}
					}
				}
			}
		}
		// 若需要取模则中间记得取模（若结果不大可以仅在循环结束时取模）
		return ans
	}

	/* 数位 DP
	v1.0 模板视频讲解 https://www.bilibili.com/video/BV1rS4y1s721/?t=19m36s
	v2.0 模板视频讲解 https://www.bilibili.com/video/BV1Fg4y1Q7wv/?t=31m28s
	https://zhuanlan.zhihu.com/p/348851463
	https://www.bilibili.com/video/BV1MT4y1376C

	入门题 https://atcoder.jp/contests/abc154/tasks/abc154_e
	      https://atcoder.jp/contests/dp/tasks/dp_s
	      https://codeforces.com/problemset/problem/1036/C
	二进制 1 的个数恰为 k 的数字个数 https://codeforces.com/problemset/problem/431/D https://www.acwing.com/problem/content/1083/
	是 m 的倍数且偶数位为 d 且奇数位不为 d 的数字个数 https://codeforces.com/problemset/problem/628/D
	所有数字均出现偶数次的数字个数 https://codeforces.com/problemset/problem/855/E
	相邻数字约束 SC09 https://www.luogu.com.cn/problem/P2657
	数位统计
	- 入门题 [2719. 统计整数数目](https://leetcode.cn/problems/count-of-integers/)（[题解](https://leetcode.cn/problems/count-of-integers/solution/shu-wei-dp-tong-yong-mo-ban-pythonjavacg-9tuc/)）
	- [788. 旋转数字](https://leetcode.cn/problems/rotated-digits/)（[题解](https://leetcode.cn/problems/rotated-digits/solution/by-endlesscheng-9b96/)）
	- [902. 最大为 N 的数字组合](https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/)（[题解](https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/solution/shu-wei-dp-tong-yong-mo-ban-xiang-xi-zhu-e5dg/)）1990
	    - 贪心：求 <= N 的最大数
	- [233. 数字 1 的个数](https://leetcode.cn/problems/number-of-digit-one/)（[题解](https://leetcode.cn/problems/number-of-digit-one/solution/by-endlesscheng-h9ua/)）
	- [面试题 17.06. 2 出现的次数](https://leetcode.cn/problems/number-of-2s-in-range-lcci/)（[题解](https://leetcode.cn/problems/number-of-2s-in-range-lcci/solution/by-endlesscheng-x4mf/)）
	    - 0~9 的个数 https://www.luogu.com.cn/problem/P2602
	    - http://acm.hdu.edu.cn/showproblem.php?pid=3555
	    - http://acm.hdu.edu.cn/showproblem.php?pid=2089
	- [600. 不含连续 1 的非负整数](https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/)（[题解](https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/solution/by-endlesscheng-1egu/)）
	- [2376. 统计特殊整数](https://leetcode.cn/problems/count-special-integers/)（[题解](https://leetcode.cn/problems/count-special-integers/solution/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/)）2120
	- [1012. 至少有 1 位重复的数字](https://leetcode.cn/problems/numbers-with-repeated-digits/)（[题解](https://leetcode.cn/problems/numbers-with-repeated-digits/solution/by-endlesscheng-c5vg/)）2230
	- [357. 统计各位数字都不同的数字个数](https://leetcode.cn/problems/count-numbers-with-unique-digits/)
	- [3007. 价值和小于等于 K 的最大数字](https://leetcode.cn/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/) 2258
	    - 有更简单的做法，见 https://leetcode.cn/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/solutions/2603673/er-fen-da-an-shu-wei-dpwei-yun-suan-pyth-tkir/
	- [2827. 范围中美丽整数的数目](https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/) 2324
	    - 整除 https://atcoder.jp/contests/abc317/tasks/abc317_f
	    - [SCOI2009] windy 数 https://www.luogu.com.cn/problem/P2657
	- [2999. 统计强大整数的数目](https://leetcode.cn/problems/count-the-number-of-powerful-integers/) 2351
	- [2801. 统计范围内的步进数字数目](https://leetcode.cn/problems/count-stepping-numbers-in-range/) 2367
	- [1397. 找到所有好字符串](https://leetcode.cn/problems/find-all-good-strings/) 2667
		- https://www.luogu.com.cn/problem/P3193
		- https://atcoder.jp/contests/abc295/tasks/abc295_f
		- 与 AC 自动机结合 https://ac.nowcoder.com/acm/problem/20366
	- [1215. 步进数](https://leetcode.cn/problems/stepping-numbers/)（会员题）
	- [1067. 范围内的数字计数](https://leetcode.cn/problems/digit-count-in-range/)（会员题） *LC233
	- [1742. 盒子中小球的最大数量](https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/) *非暴力做法 枚举数位和+DP
	- [2843. 统计对称整数的数目](https://leetcode.cn/problems/count-symmetric-integers/) *非暴力做法
	https://codeforces.com/contest/1710/problem/C
	数位和 https://leetcode.cn/problems/count-largest-group/
	数位和 digsum(n)|n https://www.luogu.com.cn/problem/P4127
	- https://atcoder.jp/contests/abc336/tasks/abc336_e
	- https://ac.nowcoder.com/acm/contest/28262/E
	- D 的倍数 https://atcoder.jp/contests/tdpc/tasks/tdpc_number
	数位和是最后一位的倍数 https://www.lanqiao.cn/problems/5891/learning/?contest_id=145
	数位乘积不超过 k https://atcoder.jp/contests/abc208/tasks/abc208_e
	数位乘积个数 (n*(n+1)/2)^2 = O(n^4) https://oeis.org/A000537
	- 详细公式推导 https://leetcode.cn/problems/count-beautiful-numbers/solutions/3613931/mo-ban-shu-wei-dp-v21pythonjavacgo-by-en-fdzz/
	https://atcoder.jp/contests/abc194/tasks/abc194_f 2197=CF2373 恰好用到了 k 个不同数位
	https://codeforces.com/problemset/problem/55/D 2500 被每个非零数位都整除的数字个数
	https://codeforces.com/problemset/problem/908/G 2800 排序后的数字之和
	https://codeforces.com/gym/104337/problem/B 【妙】数位众数，把 freq 排序作为 key
	todo https://codeforces.com/problemset/problem/1245/F
	【转换】选两个不超过 U 的数，满足异或和为 target https://atcoder.jp/contests/arc133/tasks/arc133_d 2658
	https://www.luogu.com.cn/problem/P6669 两个上界约束
	- https://www.luogu.com.cn/problem/P8688
	- https://codeforces.com/problemset/problem/582/D 3300 模数为 p^a
	https://lightoj.com/problem/investigation
	http://acm.hdu.edu.cn/showproblem.php?pid=4507
	http://acm.hdu.edu.cn/showproblem.php?pid=3886
	http://acm.hdu.edu.cn/showproblem.php?pid=6796
	注：一些第 k 小的题目需要与二分结合，或者用试填法（见后面的 kth666）
	https://atcoder.jp/contests/arc173/tasks/arc173_a 也可以用九进制
	todo 套题 https://www.luogu.com.cn/blog/s-r-f/oi-bi-ji-shuo-wei-dp-ge-ji-dui-shuo-wei-dp-di-yi-dian-li-xie
	todo 套题 https://codeforces.com/blog/entry/53960
	对称
	LC248 https://leetcode.cn/problems/strobogrammatic-number-iii/
	LC1088 https://leetcode.cn/problems/confusing-number-ii/ 2077
	*/

	// 上下界数位 DP（v2.1 模板）
	// 比如统计恰好包含 target 个 0 的数字个数，需要区分【前导零】和【数字中的零】，前导零不能计入，而数字中的零需要计入
	// 由于 limitLow && i < diffLH 等价于 !isNum，所以 isNum 是多余的
	//
	// TIPS：如果题目要求计算 < high 的方案数（high 是个字符串），
	//       可以在递归到 i=n 时，判断 limitHigh 是否为 true，如果是 true 则表示填入的数字等于 high，返回 0
	// 举例 https://atcoder.jp/contests/abc387/tasks/abc387_c
	// 代码 https://atcoder.jp/contests/abc387/submissions/61401082
	digitDP := func(low, high int, target int) int {
		// 如果没有下界，可以初始化 lowS = "0" 或者 "1"
		lowS := strconv.Itoa(low)
		highS := strconv.Itoa(high)
		n := len(highS)
		diffLH := n - len(lowS)
		memo := make([][]int, n)
		for i := range memo {
			memo[i] = make([]int, target+1)
			for j := range memo[i] {
				memo[i][j] = -1
			}
		}

		var dfs func(int, int, bool, bool) int
		dfs = func(i, cnt0 int, limitLow, limitHigh bool) (res int) {
			// 不合法
			if cnt0 > target {
				return 0
			}
			if i == n {
				// 不合法
				if cnt0 < target {
					return 0
				}
				// 合法
				return 1
			}
			if !limitLow && !limitHigh {
				dv := &memo[i][cnt0]
				if *dv >= 0 {
					return *dv
				}
				defer func() { *dv = res }()
			}

			lo := 0
			if limitLow && i >= diffLH {
				lo = int(lowS[i-diffLH] - '0')
			}
			hi := 9 // 十进制
			if limitHigh {
				hi = int(highS[i] - '0')
			}

			d := lo
			// 如果前导零不影响答案，可以去掉这个 if block
			if limitLow && i < diffLH {
				// 不填数字，参数不变
				res = dfs(i+1, cnt0, true, false)
				d = 1
			}
			for ; d <= hi; d++ {
				c0 := cnt0
				if d == 0 {
					c0++
				}
				res += dfs(i+1, c0,
					limitLow && d == lo, limitHigh && d == hi)
				res %= mod
			}
			return
		}
		ans := dfs(0, 0, true, true)
		return ans
	}

	//（旧版写法）做两次记忆化搜索（或者题目只需要考虑上界）
	digitDP2 := func(low, high string, k int) int {
		calc := func(s string) int {
			// 注：如果参数太多可以用 map
			memo := make([][]int, len(s))
			for i := range memo {
				memo[i] = make([]int, k)
				for j := range memo[i] {
					memo[i][j] = -1
				}
			}

			// 第一种写法（前导零不影响答案）
			var f func(int, int, bool) int
			f = func(i, sum int, isLimit bool) (res int) {
				if i == len(s) {
					if sum > 0 {
						return
					}
					return 1
				}
				if !isLimit {
					dv := &memo[i][sum]
					if *dv >= 0 {
						return *dv
					}
					// *dv + sum*int(math.Pow10(len(s)-i))
					defer func() { *dv = res }()
				}

				up := 9 // 25
				if isLimit {
					up = int(s[i] - '0') // 'a'
				}

				for d := range up + 1 {
					res += f(i+1, (sum+d)%k, isLimit && d == up)
				}
				res %= mod
				return
			}
			//res := f(0, 0, true)

			// 第二种写法（前导零影响答案）
			// 对于需要判断/禁止前导零的情况，可以加一个额外的维度 isNum，表示已经填入了数字（没有前导零的合法状态），最后 p=n 的时候可以根据情况返回 1 或者 0
			// 例如 https://codeforces.com/contest/855/submission/125651587
			// 以下代码以 https://www.luogu.com.cn/problem/P2657 为例
			var dfs func(int, int, bool, bool) int
			dfs = func(i int, pre int, isLimit, isNum bool) (res int) {
				if i == len(s) {
					if !isNum {
						return 0
					}
					return 1
				}
				if !isLimit && isNum {
					dv := &memo[i][pre]
					if *dv >= 0 {
						return *dv
					}
					defer func() { *dv = res }()
				}

				up := 9 // 25
				if isLimit {
					up = int(s[i] - '0') // - 'a'
				}

				d := 0
				if !isNum {
					res += dfs(i+1, pre, false, false)
					d = 1
				}
				for ; d <= up; d++ {
					//if ... {
					//	continue
					//}
					res += dfs(i+1, pre+d /* nextD */, isLimit && d == up, true)
					res %= mod
				}
				return
			}
			res := dfs(0, 0, true, false)
			return res
		}
		ansHigh := calc(high) // 上界
		ansLow := calc(low)   // 下界（注意下面单独特判 low）
		ans := ansHigh - ansLow
		ans = (ans%mod + mod) % mod

		// low 是否算上
		lowIsValid := true
		for i := 1; i < len(low); i++ {
			pre, cur := int(low[i-1]), int(low[i])
			if abs(pre-cur) != 1 { // 不合法
				lowIsValid = false
				break
			}
		}
		if lowIsValid {
			ans++
		}
		ans = (ans%mod + mod) % mod
		return ans
	}

	// 若需要计算的不是合法数字个数，而是合法数字之和，则需要在计算时考虑单个数位的贡献
	// 以下代码以 https://codeforces.com/problemset/problem/1073/E 为例
	calcSum := func(s string, k int) int {
		n := len(s)
		type pair struct{ cnt, sum int }
		memo := make([][1 << 10]pair, n)
		for i := range memo {
			for j := range memo[i] {
				memo[i][j] = pair{-1, -1}
			}
		}
		var f func(int, uint16, bool, bool) pair
		f = func(p int, mask uint16, limitUp, fill bool) (res pair) {
			if p == n {
				if !fill {
					return
				}
				return pair{1, 0}
			}
			if !limitUp && fill {
				dv := &memo[p][mask]
				if dv.cnt >= 0 {
					return *dv
				}
				defer func() { *dv = res }()
			}
			up := 9
			if limitUp {
				up = int(s[p] & 15)
			}
			for d := 0; d <= up; d++ {
				tmp := mask
				if fill || d > 0 {
					tmp |= 1 << d
				}
				if bits.OnesCount16(tmp) <= k {
					pr := f(p+1, tmp, limitUp && d == up, fill || d > 0)
					res.cnt = (res.cnt + pr.cnt) % mod
					res.sum = (res.sum + int(math.Pow10(n-1-p))%mod*pr.cnt%mod*int(d) + pr.sum) % mod
				}
			}
			return
		}
		return f(0, 0, true, false).sum
	}

	// 二维数位 DP
	// https://www.luogu.com.cn/problem/P6669
	//  - https://www.luogu.com.cn/problem/P8688 需要优化
	//  - https://codeforces.com/problemset/problem/582/D 3300 模数为 p^a
	digitDP2D := func(n, m, k int) int {
		// 以 https://www.luogu.com.cn/problem/P6669 为例
		// 要求 0 <= i <= n 且 0 <= j <= min(i, m)
		// 统计 k 进制下，至少有一位 j[p] > i[p] 的数字个数
		// 前导零不影响答案
		m = min(m, n)
		a := [][2]int{}
		for ; n > 0; n /= k {
			a = append(a, [2]int{n % k, m % k})
			m /= k
		}
		// 如果 map 慢，可以改成 int 数组 + vis 数组的写法
		// 注：如果想用全局 memo，可以记忆化 p, greater, limI
		type args struct {
			p                    int
			gr, limI, limN, limM bool
		}
		memo := map[args]int{}
		var dfs func(int, bool, bool, bool, bool) int
		dfs = func(p int, greater, limI, limN, limM bool) int {
			if p < 0 {
				if greater {
					return 1
				}
				return 0
			}
			t := args{p, greater, limI, limN, limM}
			if v, ok := memo[t]; ok {
				return v
			}

			hiN := k - 1
			if limN {
				hiN = a[p][0]
			}
			hiM := k - 1
			if limM {
				hiM = a[p][1]
			}

			res := 0
			for i := 0; i <= hiN; i++ {
				// 如果之前出现 j < i 的情况，那么当前位不受到 i 的约束
				for j := 0; (!limI || j <= i) && j <= hiM; j++ {
					res += dfs(p-1, greater || j > i, limI && j == i, limN && i == hiN, limM && j == hiM)
				}
			}
			res %= mod
			memo[t] = res
			return res
		}
		// 因为 a 是从低位到高位，所以入口是 len(a)-1
		ans := dfs(len(a)-1, false, true, true, true)
		return ans
	}

	// 试填法
	// 第 k 个包含 3 个连续的 6 的数 https://www.acwing.com/problem/content/312/
	kth666 := func(k int) (ans []byte) {
		// f[i][3] 表示由 i 位数字构成的魔鬼数的个数
		// f[i][j] (j<3) 表示 i 位数字构成的、开头有连续 j 个 6 的非魔鬼数的个数
		const mx = 30  // 长度上限
		const cont = 3 // 连续 3 个数才算符合要求
		f := [mx][cont + 1]int{}
		f[0][0] = 1
		for i := 1; i < mx; i++ {
			for j := 0; j < cont; j++ {
				f[i][0] += f[i-1][j] * 9 // 开头无 6，直接转移（0-9 中除去 6 共 9 个数）
				f[i][j+1] = f[i-1][j]    // 开头有 j+1 个 6，下一个有 j 个 6
			}
			f[i][cont] += f[i-1][cont] * 10
		}

		const tarDigit byte = '6'
		n := 1
		for f[n][cont] < k {
			n++
		}
		has := 0
		for i := 1; i <= n; i++ {
			for digit := byte('0'); digit <= '9'; digit++ { // 试填当前位
				need := cont
				if has == cont {
					need = 0
				} else if digit == tarDigit {
					need = cont - 1 - has
				}
				sum := 0
				for j := need; j <= cont; j++ {
					sum += f[n-i][j]
				}
				if sum >= k { // 填入
					ans = append(ans, digit)
					if has < cont {
						if digit == tarDigit {
							has++
						} else {
							has = 0
						}
					}
					break
				}
				k -= sum
			}
		}
		return
	}

	/* 倍增
	https://oi-wiki.org/basic/binary-lifting/
	https://atcoder.jp/contests/arc060/tasks/arc060_c 入门题
	- LC3534 https://leetcode.cn/problems/path-existence-queries-in-a-graph-ii/ 重新编号（下标映射）
	https://codeforces.com/problemset/problem/1516/D 2100
	https://codeforces.com/problemset/problem/1175/E 2200
	- 相似题目 https://www.luogu.com.cn/problem/P4155
	https://www.luogu.com.cn/problem/P3509 快速幂倍增
	https://www.luogu.com.cn/problem/P7167 喷泉模型 单调栈 点权
	https://www.luogu.com.cn/problem/P1613 类似 Floyd 枚举中间点
	https://www.luogu.com.cn/problem/P4155 环形
	https://www.luogu.com.cn/problem/P3147 合并数字
	https://www.luogu.com.cn/problem/P5465 [PKUSC2018] 星际穿越
	https://www.luogu.com.cn/problem/P1081 开车旅行
	https://www.acwing.com/problem/content/296/ 计算重复
	*/
	binaryLifting := func(left []int) {
		// 以 https://atcoder.jp/contests/arc060/tasks/arc060_c + https://leetcode.cn/problems/path-existence-queries-in-a-graph-ii/ 为例
		n := len(left)
		const mx = 17 // bits.Len(uint(n))
		pa := make([][mx]int, n)
		for i, l := range left {
			pa[i][0] = l // 从 i 往左，最远可以跳到 l
		}
		for i := range mx - 1 {
			for x := range pa {
				p := pa[x][i]
				pa[x][i+1] = pa[p][i]
			}
		}

		// 从 r 跳到 <= l 的位置，最少要跳多少步
		minJumps := func(l, r int) (res int) {
			if l == r {
				return
			}
			if l > r {
				l, r = r, l
			}
			for k := mx - 1; k >= 0; k-- {
				p := pa[r][k]
				if p > l {
					r = p
					res |= 1 << k
				}
			}
			// 注意循环结束后还要再跳一次
			r = pa[r][0]
			res++
			if r > l {
				return -1
			}
			return
		}

		// 从 i 开始，往左跳 k 步的最远位置
		jumpK := func(i, k int) int {
			for ; k > 0; k &= k - 1 {
				i = pa[i][bits.TrailingZeros(uint(k))]
			}
			return i
		}

		// 计算 nxt 数组迭代 k 次后的数组
		// 思路同快速幂
		// https://www.luogu.com.cn/problem/P3509
		nextK := func(nxt []int, k int) []int {
			res := make([]int, len(nxt))
			for i := range res {
				res[i] = i
			}
			for ; k > 0; k /= 2 {
				if k%2 > 0 {
					for i, j := range res {
						res[i] = nxt[j]
					}
				}
				newNxt := make([]int, len(nxt))
				for i, to := range nxt {
					newNxt[i] = nxt[to]
				}
				nxt = newNxt
			}
			return res
		}

		_ = []any{minJumps, jumpK, nextK}
	}

	// 额外有点权 costs
	binaryLifting2 := func(right, costs []int) {
		// 基于喷泉模型 https://www.luogu.com.cn/problem/P7167
		n := len(costs)
		const mx = 17 // bits.Len(uint(n+1))
		type pair struct{ to, cost int }
		pa := make([][mx]pair, n+1)
		pa[n][0].to = n // 哨兵
		for i := n - 1; i >= 0; i-- {
			pa[i][0] = pair{right[i], costs[i]}
		}

		for i := 0; i < mx-1; i++ {
			for x := range pa {
				p := pa[x][i]
				q := pa[p.to][i]
				pa[x][i+1] = pair{q.to, p.cost + q.cost}
			}
		}

		calcTarget := func(start, rem int) int {
			cur := start
			for k := mx - 1; k >= 0; k-- {
				p := pa[cur][k]
				if rem > p.cost {
					rem -= p.cost
					cur = p.to
				}
			}
			// 注意循环结束后还要再跳一次
			p := pa[cur][0]
			if rem > p.cost {
				cur = p.to
			}
			return cur // 可能等于 n
		}

		_ = calcTarget
	}

	/* 数据结构优化 DP
	https://codeforces.com/problemset?order=BY_RATING_ASC&tags=data+structures%2Cdp
	入门：数组优化 https://codeforces.com/contest/1842/problem/C
	             LC2713 https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/
	线段树 LC2407 https://leetcode.cn/problems/longest-increasing-subsequence-ii/ 2280
	变量优化 O(n) LC2746 https://leetcode.cn/problems/decremental-string-concatenation/
	https://atcoder.jp/contests/dp/tasks/dp_q 入门题 值域树状数组
	https://atcoder.jp/contests/abc339/tasks/abc339_e 入门题 值域线段树
	https://atcoder.jp/contests/dp/tasks/dp_w Lazy 线段树
	https://atcoder.jp/contests/arc073/tasks/arc073_d
	- https://www.luogu.com.cn/problem/T190609?contestId=48376
	- https://www.luogu.com.cn/blog/abruce-home/ti-xie-nao-zhong
	https://codeforces.com/problemset/problem/597/C 1900 长为 k 的上升子序列个数
	https://codeforces.com/problemset/problem/66/E 2000
	https://codeforces.com/problemset/problem/1667/B 2100
	https://codeforces.com/problemset/problem/833/B 2200
	- k=3 https://atcoder.jp/contests/abc397/tasks/abc397_f
	https://codeforces.com/problemset/problem/1295/E 2200
	https://codeforces.com/problemset/problem/1788/E 2200
	https://codeforces.com/problemset/problem/1842/E 2300
	https://codeforces.com/problemset/problem/1609/E 2400 分治 线段树
	https://atcoder.jp/contests/abc353/tasks/abc353_g 线段树 式子变形
	https://atcoder.jp/contests/abc397/tasks/abc397_f 线段树 划分型 DP

	维护最大次大
	LC3122 https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/ 1905
	https://codeforces.com/problemset/problem/264/C 2000

	滑动窗口优化 DP
	https://codeforces.com/problemset/problem/985/E 2100
	- 把 a 从小到大排序后，如果分组方案存在，那么一定有一个分组方案是，同一组的数在 a 中是连续的
	- 证明：因为交换两个不同组的数，一定不会变得更优

	前缀和优化 DP
	优化空间时，可以直接把前缀和保存到 f 数组上，然后倒序遍历，计算实际的 f
	- 例如 https://leetcode.cn/problems/count-the-number-of-inversions/
	LC1977 https://leetcode.cn/problems/number-of-ways-to-separate-numbers/
	- https://codeforces.com/problemset/problem/1552/F 2200 数据加强
	逆序对为 k 时的排列个数
	- https://www.luogu.com.cn/problem/P3800
	- 加强版：前缀约束 LC3193 https://leetcode.cn/problems/count-the-number-of-inversions/
	https://www.luogu.com.cn/problem/P2513
	https://codeforces.com/problemset/problem/46/E 1900 前缀最大值/后缀最大值
	https://codeforces.com/problemset/problem/479/E 1900
	- https://atcoder.jp/contests/abc253/tasks/abc253_e
	https://atcoder.jp/contests/dp/tasks/dp_t 排列问题的状态设计
	- 相似题目 https://leetcode.cn/problems/count-the-number-of-inversions/
	https://atcoder.jp/contests/abc248/tasks/abc248_c
	https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e
	https://codeforces.com/problemset/problem/708/E 3100
	另见本页面的 boundedKnapsackWays（前缀和优化多重背包方案数）

	其他
	https://codeforces.com/problemset/problem/1863/F 2600

	数论分块优化 DP
	https://codeforces.com/problemset/problem/1603/C

	动态 DP
	https://oi-wiki.org/dp/dynamic/
	线段树维护转移矩阵 https://www.cnblogs.com/Miracevin/p/9124511.html
	1. 先不考虑修改，不考虑区间，直接列出整个区间的 DP 转移。
	2. 列出转移矩阵。由于有很多修改操作，我们将数据集中在一起处理，还可以利用矩阵结合律，并且区间比较好提取（找一段矩阵就好了），修改也方便。
	3. 线段树维护矩阵。对于修改，我们就是在矩阵上修改。对于不同的题目，我们要用不同的修改方式和记录手段，但都是用线段树维护对应区间内的矩阵信息。
	   如矩阵乘积，矩阵和等等。线段树的区间操作可以应对区间修改问题。
	todo https://www.cnblogs.com/alex-wei/p/DP_Involution.html
	https://codeforces.com/problemset/problem/1380/F
	https://codeforces.com/problemset/problem/718/C
	https://codeforces.com/problemset/problem/750/E
	https://codeforces.com/problemset/problem/1149/B
	https://codeforces.com/problemset/problem/2042/F 2600
	todo 与树剖结合 https://www.luogu.com.cn/problem/P4719 https://www.luogu.com.cn/problem/P4751
	*/

	// 单调队列优化 DP
	// 见 monotone_queue.go

	// 斜率优化 / 凸包优化 (Convex Hull Trick, CHT)
	// 状态转移方程形如 f[i] = min_{j=0}^{i-1} a[i]*b[j] + k[i]*f[j] + C，包含 i 和 j 的乘积项
	//
	// 理解方法一：点积的几何意义（向量投影长度）
	// 推荐，比斜率、截距好想很多
	// 讲解 https://leetcode.cn/problems/minimum-cost-to-divide-array-into-subarrays/solutions/3633352/hua-fen-xing-dp-shi-zi-bian-xing-pythonj-cwi9/
	// - 注：原题是经典例题 https://www.luogu.com.cn/problem/P2365
	//
	// 思考：三维凸包优化 DP？
	//
	// https://atcoder.jp/contests/dp/tasks/dp_z 入门题 min
	// - https://www.luogu.com.cn/problem/P3195 https://loj.ac/p/10188
	// https://www.luogu.com.cn/problem/P3628 max
	// https://www.luogu.com.cn/problem/P5017
	// https://www.luogu.com.cn/problem/P5785 任务安排
	// - https://www.luogu.com.cn/problem/P2365 IOI02 http://poj.org/problem?id=1180
	// https://www.luogu.com.cn/problem/P2900 https://www.luogu.com.cn/problem/SP15086 单调栈
	// https://codeforces.com/problemset/problem/319/C 2100
	// https://codeforces.com/problemset/problem/311/B 2400 划分型 DP
	// https://codeforces.com/problemset/problem/643/C 2400 划分型 DP + 期望 DP
	// https://codeforces.com/problemset/problem/1083/E 2400 入门题
	// https://codeforces.com/problemset/problem/1575/M 2400 固定变量
	// https://codeforces.com/problemset/problem/1715/E 2400 Dijkstra
	// https://codeforces.com/problemset/problem/660/F 2500
	// https://codeforces.com/problemset/problem/678/F 2500 线段树分治 todo
	// https://codeforces.com/problemset/problem/1866/K 2500 凸包次大值：把从单调栈中淘汰的数据再建一个（更内部的）凸包
	// https://codeforces.com/problemset/problem/631/E 2600 往左还是往右可以变形成同一个式子
	// https://codeforces.com/problemset/problem/932/F 2700 平衡树+启发式合并
	// https://codeforces.com/problemset/problem/1303/G 2700 李超线段树
	// https://codeforces.com/problemset/problem/1366/F 2700 图 DP
	// https://codeforces.com/problemset/problem/2107/F2 2800
	// https://codeforces.com/problemset/problem/1175/G 3000 李超线段树
	// todo
	//  https://www.luogu.com.cn/problem/P2120
	//  https://www.luogu.com.cn/problem/P3648
	//  https://www.luogu.com.cn/problem/P4072
	//  https://www.luogu.com.cn/problem/P4027
	//  https://www.luogu.com.cn/problem/P5504
	//  https://www.luogu.com.cn/problem/P5468 https://www.luogu.com.cn/problem/P6302 https://loj.ac/p/6520
	//  https://www.luogu.com.cn/problem/P1721
	//  https://www.luogu.com.cn/problem/P2305
	// http://poj.org/problem?id=3709
	convexHullTrick := func(a, b, k []int, C int) int {
		// 用点积来理解，用 Andrew 算法计算凸包
		// f[i] = min_{j=0}^{i-1} a[i]*b[j] + k[i]*f[j] + C
		// ！需要保证 b[j] 是递增的（或者 f[j] 是递增的），否则需要用平衡树维护凸包
		// ！如果 b[j] 是递减的，可以把 a[i]*b[j] 改成 (-a[i])*(-b[j])，这样 -b[j] 是递增的
		// 设 v[j] = (b[j], f[j])
		// 设 p = (a[i], k[i])
		// 问题变成求点积 p.dot(v[j]) 的最小值 + C
		// 这可以在下凸包中二分找点积的谷底，即第一个上坡

		f := make([]int, len(a))
		q := []vec{{b[0], f[0]}}      // j=0 单独算
		for i := 1; i < len(a); i++ { // a 一般是个前缀和数组，长为 n+1
			pi := vec{a[i], k[i]} // 和 j 相乘的 i 写这里！没有就是 1！
			// ！如果是转移方程是求 max，把 < 改成 >，即第一个下坡
			j := sort.Search(len(q)-1, func(j int) bool { return pi.dot(q[j]) < pi.dot(q[j+1]) })
			// 如果 a[i] 是递减的，二分可以改成双指针（否则只能二分）
			// 对于求 max 的题目，如果 a[i] 是递增的，二分可以改成双指针（否则只能二分）  >= 改成 <=
			// for len(q) > 1 && pi.dot(q[0]) >= pi.dot(q[1]) { q = q[1:] }; f[i] = pi.dot(q[0]) + C
			f[i] = pi.dot(q[j]) + C

			vj := vec{b[i], f[i]} // 和 j 相关的量写这里！需要保证 b[j] 是递增的！
			// ！如果转移方程是求 max，把 <= 改成 >=，也就是计算上凸包
			// ！如果 x*y 超出 int64，用 big.Int 计算（拒绝浮点数！）
			for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).det(vj.sub(q[len(q)-1])) <= 0 {
				q = q[:len(q)-1]
			}
			q = append(q, vj)
		}
		return f[len(f)-1] // q[len(q)-1].y
	}

	// 平衡树维护凸包
	// 见 geometry.go 中的 dynamicConvexHull

	// 理解方法二：斜率、截距（不推荐）
	// 若将 (b[j],f[j]) 看作二维平面上的点，则 f[i] 就是所有斜率为 a[i] 且过其中一点的直线中，与 y 轴的最小截距
	// 我们可以用一个单调队列来维护 (b[j],f[j]) 的相邻点所构成的下凸包
	// 对于斜率 a[i]，我们需要在队列中寻找一个位置 k，其左侧斜率小于 a[i]，右侧斜率大于 a[i]，此时经过点 (b[k],f[k]) 能取到最小截距
	//
	// 具体到实现，设两转移来源的下标为 j 和 k，若 k < j 且 f[k]-a[i]*b[k] < f[j]-a[i]*b[j]
	// 则有 (f[j]-f[k])/(b[j]-b[k]) > a[i]
	// 据此式，用单调队列来维护斜率（下凸包）
	// 转移前，在单调队列中找到斜率 a[i] 的对应位置，然后代入转移方程，求出 f[i]
	// 转移后，将点 (b[i],f[i]) 加入单调队列中
	//
	// https://oi-wiki.org/dp/opt/slope/
	// https://cp-algorithms.com/geometry/convex_hull_trick.html
	// https://www.bilibili.com/video/BV178411W7Aj/
	// https://www.luogu.com.cn/blog/ChenXingLing/post-xue-xi-bi-ji-dong-tai-gui-hua-xie-shuai-you-hua-dp-chao-yang-x
	// https://www.luogu.com.cn/blog/ningago-lsh/xie-lv-you-hua-dp
	// https://blog.csdn.net/weixin_43914593/article/details/105560357
	// https://zhuanlan.zhihu.com/p/558522044
	// https://zhuanlan.zhihu.com/p/363772434
	// https://codeforces.com/blog/entry/63823
	convexHullTrick2 := func(a, b []int) int {
		n := len(a)
		f := make([]int, n)
		// 计算两点间的斜率，若分子分母均在 32 位整数范围内，可以去掉浮点，改用乘法（或者用 lessPair）
		slope := func(i, j int) float64 {
			if b[i] == b[j] { // 若保证不相等则去掉
				if f[j] > f[i] {
					return 1e99
				}
				return -1e99
			}
			return float64(f[j]-f[i]) / float64(b[j]-b[i])
		}
		q := []int{0}
		for i := 1; i < n; i++ {
			k := a[i]
			// 若斜率 k 随 i 单调递增，则可以直接将单调队列中小于 k 的斜率弹出
			for len(q) > 1 && slope(q[0], q[1]) < float64(k) {
				q = q[1:]
			}
			// ……之后，队首 q[0] 就是最优决策的下标
			j := q[0]
			// ……否则，需要在单调队列中二分得到最优决策的位置
			j = sort.Search(len(q)-1, func(j int) bool { return slope(j, j+1) > float64(k) })

			// 转移
			f[i] = f[j] - a[i]*b[j]

			// 然后，将点 (b[i],f[i]) 加入单调队列中
			for len(q) > 1 && slope(q[len(q)-1], i) < slope(q[len(q)-2], q[len(q)-1]) {
				q = q[:len(q)-1]
			}
			q = append(q, i)
		}
		return f[n-1]
	}

	// WQS 二分 / 凸完全单调性优化 DP / 凸优化 DP / 带权二分 / Alien Trick / Alien DP / Monge グラフ上のd-辺最短路長を計算するアルゴリズム 
	// 原文：《浅析一类二分方法》
	// 把最多选 k 个物品的问题（时间复杂度高）转换成选任意个物品的问题（更容易解决，时间复杂度低）
	// 要求满足性质：k 越大，额外产生的收益是单调递减的
	// 具体请看下面的代码注释
	// https://zhuanlan.zhihu.com/p/340514421
	// https://www.cnblogs.com/alex-wei/p/DP_Involution.html
	// https://www.cnblogs.com/CreeperLKF/p/9045491.html
	// https://taodaling.github.io/blog/2020/07/31/WQS%E4%BA%8C%E5%88%86/
	// https://www.luogu.com.cn/blog/daniu/wqs-er-fen
	// https://www.luogu.com.cn/blog/Flying2018/wqs-er-fen-min-ke-fu-si-ji-hu-xue-xi-bi-ji
	// https://www.luogu.com.cn/blog/juruoforever/wqs-er-fen-qian-xi
	// https://noshi91.github.io/algorithm-encyclopedia/d-edge-shortest-path-monge
	//
	// 题单 https://www.luogu.com.cn/training/3495#problems
	// 种树（打家劫舍）https://www.luogu.com.cn/problem/P1484
	// https://www.luogu.com.cn/problem/P6821
	// - 前缀和处理后就是 LC188 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
	// LC2209 https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/
	// todo https://codeforces.com/problemset/problem/125/E 2400 单度限制最小生成树（恰好）
	//  https://codeforces.com/problemset/problem/321/E 2600
	//  https://codeforces.com/problemset/problem/739/E 3000 也可以费用流
	//  结合四边形不等式 IOI00 邮局 https://www.luogu.com.cn/problem/P4767 
	//  - https://www.luogu.com.cn/problem/P6246
	//  https://www.luogu.com.cn/problem/P5308
	//  IOI16 aliens https://www.luogu.com.cn/problem/P5896
	//  https://www.luogu.com.cn/problem/U72600
	wqs := func(a []int, k int) (ans int) {
		// 代码分为两部分：dpWithFee 和 sort.Search
		// 前者是需要实现的 DP，后者是固定的模板，一般只需要注意二分上界

		// dpWithFee 是一个更容易解决的 DP：每次产生一次「选择」的时候（例如完成一次买卖），额外有手续费 fee，但没有至多 k 次的限制了
		// 返回最大收益，以及在收益最大的前提下，「选择」次数的最大值
		// LC714 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
		dpWithFee := func(fee int) (res, cnt int) {
			f0, f1 := 0, math.MinInt/2
			cnt0, cnt1 := 0, 0
			for _, p := range a {
				if f0-p >= f1 { // 取等号，让交易次数尽量多
					f1 = f0 - p
					cnt1 = cnt0
				}
				if f1+p-fee >= f0 { // 取等号，让交易次数尽量多
					f0 = f1 + p - fee
					cnt0 = cnt1 + 1 // 卖出才算完整交易
				}
			}
			return f0, cnt0
		}

		// 下面是 WQS 二分模板
		// 以 LC188 为例 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
		// 二分交易「手续费」fee，做一个 LC714 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
		// 那么 fee 越小，交易次数越多；fee 越大，交易次数越小
		// 如果交易次数小于 k，说明 fee 取大了，反之 fee 取小了
		// 如果某个 fee 对应着恰好 k 次交易，就得到了正确答案
		//
		// fee 最大为 slices.Max(a)，此时可以保证收益为 0（但仍然可以完成交易，比如卖出价格-买入价格-fee=0）
		// +1 可以保证至少触发一次 ans 赋值
		sort.Search(slices.Max(a)+1, func(fee int) bool {
			res, cnt := dpWithFee(fee)
			if cnt >= k { // 至少 k 次交易
				ans = res + k*fee // 直接算，因为最终一定会二分到恰好 k 次交易
				return false
			}
			if fee == 0 { // 说明无论如何，交易次数都小于 k
				ans = res // fee 为 0 时，res 最大，也就是答案
			}
			return true
		})

		// 下面是另一个例子 https://www.luogu.com.cn/problem/P1484
		// 这题的 dpWithFee 就只需要实现一个打家劫舍的 DP
		dpWithFee = func(fee int) (res, cnt int) {
			var f0, f1, cnt0, cnt1 int
			for _, v := range a {
				v -= fee
				if f1 > f0+v { // 不选
					f0 = f1
					cnt0 = cnt1
				} else { // 选（相等时也选）
					f0, f1 = f1, f0+v
					cnt0, cnt1 = cnt1, cnt0+1
				}
			}
			return f1, cnt1
		}
		// WQS 模板（代码和上面一样）
		// fee 最大为 slices.Max(a)，此时可以保证收益为 0
		sort.Search(slices.Max(a)+1, func(fee int) bool {
			res, cnt := dpWithFee(fee)
			if cnt >= k {
				ans = res + k*fee
				return false
			}
			if fee == 0 {
				ans = res
			}
			return true
		})

		return
	}

	// 四边形不等式优化 Knuth's Optimization / Knuth-Yao Speedup
	// 满足该性质的 DAG 叫做 Monge 图
	// https://oi-wiki.org/dp/opt/quadrangle/
	// https://jeffreyxiao.me/blog/knuths-optimization
	// todo https://blog.csdn.net/weixin_43914593/article/details/105150937 算法竞赛专题解析（10）：DP优化(1)--四边形不等式
	//      决策单调性优化讲解 https://www.luogu.com.cn/blog/83547/zong-dong-tai-gui-hua-di-ben-zhi-kan-si-bian-xing-fou-deng-shi-you-hua
	// 扔蛋问题 LC887 https://leetcode.cn/problems/super-egg-drop/

	// CDQ 分治优化 DP
	// todo https://oi-wiki.org/misc/cdq-divide/
	//  推荐 https://blog.nowcoder.net/n/f44d4aada5a24f619442dd6ddffa7320
	//  推荐 https://zhuanlan.zhihu.com/p/332996578
	//  https://www.bilibili.com/video/BV1mC4y1s7ic
	//  [学习笔记]CDQ分治和整体二分 https://www.luogu.com.cn/blog/Owencodeisking/post-xue-xi-bi-ji-cdq-fen-zhi-hu-zheng-ti-er-fen
	//  https://www.luogu.com.cn/blog/ljc20020730/cdq-fen-zhi-xue-xi-bi-ji
	//  动态逆序对 https://www.luogu.com.cn/problem/P3157 https://www.luogu.com.cn/problem/UVA11990
	//  CDQ 优化 DP https://www.luogu.com.cn/problem/P2487
	//  https://codeforces.com/problemset/problem/848/C
	//  数据结构 https://codeforces.com/problemset/problem/1045/G https://codeforces.com/problemset/problem/762/E

	/* 树形 DP
	思考方向：
	每个节点需要计算的信息，是否只取决于邻居？
	如果不能，如何把子树的信息归纳到邻居上？

	一般是从自底向上计算的，也就是根据子树返回值来计算父节点的值
	也有自顶向下的写法，见后面

	视频讲解
	https://www.bilibili.com/video/BV17o4y187h1/
	https://www.bilibili.com/video/BV1vu4y1f7dn/
	https://www.bilibili.com/video/BV1oF411U7qL/

	https://codeforces.com/blog/entry/20935
	https://codeforces.com/blog/entry/63257
	题单 https://ac.nowcoder.com/acm/problem/collection/807
	题单 https://ac.nowcoder.com/acm/problem/collection/809

	另见树上背包 treeKnapsack

	https://codeforces.com/problemset/problem/1900/C 1300 入门 二叉树
	https://www.luogu.com.cn/problem/P5018 入门 二叉树
	- LC101 https://leetcode.cn/problems/symmetric-tree/
	https://codeforces.com/problemset/problem/982/C 1500
	https://codeforces.com/problemset/problem/369/C 1600
	https://codeforces.com/problemset/problem/1689/C 1600 二叉树
	https://codeforces.com/problemset/problem/743/D 1800
	https://codeforces.com/problemset/problem/1083/A 1800
	https://codeforces.com/problemset/problem/1833/G 1800
	https://codeforces.com/problemset/problem/1739/D 1900 二分答案
	https://codeforces.com/problemset/problem/1926/G 1900
	https://codeforces.com/problemset/problem/855/C 2000
	https://codeforces.com/problemset/problem/461/B 2000 如何定义状态
	https://codeforces.com/problemset/problem/1923/E 2000 两端点颜色相同，中间节点颜色不等于两端点
	- 对于每个点，统计往上走能到哪些同色点（中途不能经过同色点）
	https://codeforces.com/problemset/problem/1988/D 2000
	https://codeforces.com/problemset/problem/2014/F 2000 推荐 经典状态机
	https://codeforces.com/problemset/problem/734/E 2100 巧妙的转换
	https://codeforces.com/problemset/problem/538/E 2200 **如何转移
	https://codeforces.com/problemset/problem/1220/E 2200 可以重复走
	https://codeforces.com/problemset/problem/1249/F 2200 好题
	https://codeforces.com/problemset/problem/1292/C 2300
	https://codeforces.com/problemset/problem/1453/E 2300 好题
	https://codeforces.com/problemset/problem/238/C 做到 O(n) ~2400
	https://codeforces.com/problemset/problem/1059/E 2400 取往上冲的最高的点（子树）
	https://atcoder.jp/contests/dp/tasks/dp_p
	https://atcoder.jp/contests/abc259/tasks/abc259_f
	https://atcoder.jp/contests/abc239/tasks/abc239_e
	https://atcoder.jp/contests/abc207/tasks/abc207_f
	https://www.luogu.com.cn/problem/P3177 [HAOI2015] 树上染色
	https://www.luogu.com.cn/problem/P12136 [蓝桥杯 2025 省 B] 生产车间
	https://ac.nowcoder.com/acm/contest/63585/d
	*/

	// 树的直径（两遍 DFS 求法另见 graph_tree.go 中的 diameter）
	// 模板题 LC1245 https://leetcode.cn/problems/tree-diameter/
	// 模板题 https://www.luogu.com.cn/problem/U81904
	// 带权版本 https://atcoder.jp/contests/abc361/tasks/abc361_e
	// 变形 LC2246 https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/
	// 二叉树的直径 https://leetcode.cn/problems/diameter-of-binary-tree/
	// - 变形 LC2385 https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/
	// https://codeforces.com/problemset/problem/1881/F 1700
	// https://codeforces.com/problemset/problem/1238/F 2200
	// https://codeforces.com/problemset/problem/1042/F 2400 贪心
	// 虚树直径 https://www.luogu.com.cn/problem/P4103
	diameter := func(st int, g [][]int) (diameter int) {
		var dfs func(int, int) int
		dfs = func(v, fa int) (maxL int) {
			for _, w := range g[v] {
				if w != fa {
					subL := dfs(w, v) + 1 // wt
					diameter = max(diameter, maxL+subL)
					maxL = max(maxL, subL)
				}
			}
			return
		}
		dfs(st, -1)
		return
	}

	// 树的直径及其个数
	// http://acm.hdu.edu.cn/showproblem.php?pid=3534
	// https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45988692
	countDiameter := func(st int, g [][]int) (diameter, diameterCnt int) {
		var dfs func(int, int) (int, int)
		dfs = func(v, fa int) (int, int) {
			mxDep, cnt := 0, 1
			for _, w := range g[v] {
				if w != fa {
					d, c := dfs(w, v)
					if l := mxDep + d; l > diameter {
						diameter, diameterCnt = l, cnt*c
					} else if l == diameter {
						diameterCnt += cnt * c
					}
					if d > mxDep {
						mxDep, cnt = d, c
					} else if d == mxDep {
						cnt += c
					}
				}
			}
			return mxDep + 1, cnt
		}
		dfs(st, -1)
		return
	}

	// 变形：两个异色点的最远距离
	// https://www.luogu.com.cn/problem/P10725
	// 带修版本 https://codeforces.com/gym/104373/problem/J https://www.luogu.com.cn/problem/P9665
	// 改成颜色相同呢？见 graph_tree.go 中的 maxDisOfSameColor
	maxDisOfDiffColor := func(a []int, g [][]struct{ to, wt int }) (ans int) {
		var dfs func(int, int) (int, int, int)
		dfs = func(v, fa int) (max1, max2, color1 int) {
			max2 = -1e18
			color1 = a[v]
			for _, e := range g[v] {
				w := e.to
				if w == fa {
					continue
				}
				m1, m2, c1 := dfs(w, v)
				m1 += e.wt
				m2 += e.wt
				if c1 != color1 {
					ans = max(ans, max1+m1)
					if m1 > max1 {
						max2 = max(max1, m2)
						max1, color1 = m1, c1
					} else {
						max2 = max(max2, m1)
					}
				} else {
					ans = max(ans, max1+m2, max2+m1)
					max1 = max(max1, m1)
					max2 = max(max2, m2)
				}
			}
			return
		}
		dfs(0, -1)
		return
	}

	// 统计树上所有简单路径长度及其个数 O(n^3)
	// 返回一个长为 n 的数组 ans，ans[i] 表示长为 i 的简单路径个数
	// O(n^2) 见 https://github.com/hqztrue/LeetCodeSolutions/blob/master/1601-1700/1617.%20Count%20Subtrees%20With%20Max%20Distance%20Between%20Cities.pdf
	// LC1617 https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/
	countPath := func(g [][]int) []int {
		n := len(g)
		// 计算树上任意两点的距离
		dis := make([][]int, n)
		for i := range dis {
			// 计算 i 到其余点的距离
			dis[i] = make([]int, n)
			var dfs func(int, int)
			dfs = func(x, fa int) {
				for _, y := range g[x] {
					if y != fa {
						dis[i][y] = dis[i][x] + 1 // 自顶向下
						dfs(y, x)
					}
				}
			}
			dfs(i, -1)
		}

		ans := make([]int, n)
		ans[0] = n
		for i, di := range dis {
			for j := i + 1; j < n; j++ {
				dj := dis[j]
				dij := di[j]
				var dfs func(int, int) int
				dfs = func(x, fa int) int {
					// 能递归到这，说明 x 可以选
					cnt := 1 // 选 x
					for _, y := range g[x] {
						if y != fa &&
							(di[y] < dij || di[y] == dij && y > j) &&
							(dj[y] < dij || dj[y] == dij && y > i) { // 满足这些条件就可以选
							cnt *= dfs(y, x) // 每棵子树互相独立，采用乘法原理
						}
					}
					if di[x]+dj[x] > dij { // x 是可选点
						cnt++ // 不选 x
					}
					return cnt
				}
				ans[dij] += dfs(i, -1)
			}
		}
		return ans
	}

	// 树的直径及在直径上的节点个数
	// https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45987468
	// 注意这里的 cnt 初始化与 countDiameter 的不同之处
	countVerticesOnDiameter := func(st int, g [][]int) (diameter, verticesCnt int) {
		var f func(int, int) (int, int)
		f = func(v, fa int) (int, int) {
			mxDep, cnt := 0, 0
			for _, w := range g[v] {
				if w != fa {
					d, c := f(w, v)
					if l := mxDep + d; l > diameter {
						diameter, verticesCnt = l, cnt+c+1 // 最长的链 + 当前链 + 当前节点
					} else if l == diameter {
						verticesCnt += c
					}
					if d > mxDep {
						mxDep, cnt = d, c
					} else if d == mxDep {
						cnt += c
					}
				}
			}
			return mxDep + 1, cnt + 1
		}
		f(st, -1)
		return
	}

	// 最大路径和 最大路径点权和
	// 变形 LC2538 https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/
	// https://codeforces.com/problemset/problem/633/F 2600 两条不相交路径的最大点权和
	maxPathSum := func(st int, g [][]int, a []int) (ans int) {
		// 点权
		var f func(int, int) int
		f = func(v, fa int) int {
			val := a[v]
			ans = max(ans, val)
			maxS := val // 从下面到 v 的最大【链】点权和
			for _, w := range g[v] {
				if w != fa {
					s := f(w, v)
					ans = max(ans, maxS+s)
					maxS = max(maxS, s+val)
				}
			}
			return maxS
		}
		f(st, -1)

		{
			// 边权
			type nb struct{ to, wt int }
			var g [][]nb // read...
			var f func(int, int) int
			f = func(v, fa int) int {
				maxS := 0
				for _, e := range g[v] {
					w := e.to
					if w != fa {
						s := f(w, v) + e.wt
						ans = max(ans, maxS+s)
						maxS = max(maxS, s)
					}
				}
				return maxS
			}
			f(st, -1)
		}

		{
			// 点权+边权
			type nb struct{ to, wt int }
			var g [][]nb // read...
			var f func(int, int) int
			f = func(v, fa int) int {
				val := a[v]
				ans = max(ans, val)
				maxS := val
				for _, e := range g[v] {
					w := e.to
					if w != fa {
						s := f(w, v) + e.wt
						ans = max(ans, maxS+s)
						maxS = max(maxS, s+val)
					}
				}
				return maxS
			}
			f(st, -1)
		}

		return
	}

	// 树上最大独立集
	// 返回最大点权和（最大独立集的情形即所有点权均为一）
	// 每个点有选和不选两种决策，接受子树转移时，选的决策只能加上不选子树，而不选的决策可以加上 max{不选子树, 选子树}
	// https://brooksj.com/2019/06/20/%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%94%AF%E9%85%8D%E9%9B%86%EF%BC%8C%E6%9C%80%E5%B0%8F%E7%82%B9%E8%A6%86%E7%9B%96%E9%9B%86%EF%BC%8C%E6%9C%80%E5%A4%A7%E7%82%B9%E7%8B%AC%E7%AB%8B%E9%9B%86/
	// https://stackoverflow.com/questions/13544240/algorithm-to-find-max-independent-set-in-a-tree
	// 经典题：没有上司的舞会 LC337 https://leetcode.cn/problems/house-robber-iii/ https://www.luogu.com.cn/problem/P1352 https://ac.nowcoder.com/acm/problem/51178
	// - EXTRA：可以修改树上的点权 https://www.luogu.com.cn/problem/P4719 https://www.luogu.com.cn/problem/P4751
	// 边独立集 LC2378 https://leetcode.cn/problems/choose-edges-to-maximize-score-in-a-tree/
	// 变形 LC2646 https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/
	// 方案是否唯一 Tehran06，紫书例题 9-13，UVa 1220 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3661
	// 变形：同一层至多选一个节点（蓝桥杯）
	// 相似，但不完全是 https://codeforces.com/problemset/problem/1988/D
	maxIndependentSetOfTree := func(n int, g [][]int, a []int) int { // 无根树
		var f func(int, int) (int, int)
		f = func(v, fa int) (notChosen, chosen int) {
			chosen = a[v] // 1
			for _, w := range g[v] {
				if w != fa {
					nc, c := f(w, v)
					notChosen += max(nc, c)
					chosen += nc
				}
			}
			return
		}
		return max(f(0, -1))
	}

	// 树上最小顶点覆盖（每条边至少有一个端点被覆盖，也就是在已选的点集中）
	// 代码和树上最大独立集类似
	// https://brooksj.com/2019/06/20/%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%94%AF%E9%85%8D%E9%9B%86%EF%BC%8C%E6%9C%80%E5%B0%8F%E7%82%B9%E8%A6%86%E7%9B%96%E9%9B%86%EF%BC%8C%E6%9C%80%E5%A4%A7%E7%82%B9%E7%8B%AC%E7%AB%8B%E9%9B%86/
	// 经典题：战略游戏 https://www.luogu.com.cn/problem/P2016
	// 训练指南第一章例题 30，UVa10859 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1800
	// - 求最小顶点覆盖，以及所有最小顶点覆盖中，两端点都被覆盖的边的最大个数
	// 构造 https://codeforces.com/problemset/problem/959/C
	minVertexCoverOfTree := func(n int, g [][]int, a []int) int { // 无根树
		var f func(int, int) (notChosen, chosen int)
		f = func(v, fa int) (notChosen, chosen int) {
			chosen = a[v] // 1
			for _, w := range g[v] {
				if w != fa {
					nc, c := f(w, v)
					notChosen += c
					chosen += min(nc, c)
				}
			}
			return
		}
		return min(f(0, -1))
	}

	// 树上最小支配集
	// 返回最小点权和（最小支配集的情形即所有点权均为一）
	// 下面的定义省去了（……时的最小支配集的元素个数）   w 为 i 的儿子
	// 视频讲解：https://www.bilibili.com/video/BV1oF411U7qL/
	// f[i][0]：选 i = a[i]+∑min(f[w][0],f[w][1],f[w][2])
	// f[i][1]：不选 i，且 i 被儿子支配 = ∑min(f[w][0],f[w][1]) + max(min{f[w][0]-f[w][1]}, 0)
	// f[i][2]：不选 i，且 i 被父亲支配 = ∑min(f[w][0],f[w][1])
	// https://brooksj.com/2019/06/20/%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%94%AF%E9%85%8D%E9%9B%86%EF%BC%8C%E6%9C%80%E5%B0%8F%E7%82%B9%E8%A6%86%E7%9B%96%E9%9B%86%EF%BC%8C%E6%9C%80%E5%A4%A7%E7%82%B9%E7%8B%AC%E7%AB%8B%E9%9B%86/
	//
	// 监控二叉树 LC968 https://leetcode.cn/problems/binary-tree-cameras/
	// - https://codeforces.com/problemset/problem/1029/E
	// 保安站岗 https://www.luogu.com.cn/problem/P2458
	// 手机网络 https://www.luogu.com.cn/problem/P2899
	// https://ac.nowcoder.com/acm/problem/24953
	// todo EXTRA: 消防局的设立（支配距离为 2） https://www.luogu.com.cn/problem/P2279
	// todo EXTRA: 将军令（支配距离为 k） https://www.luogu.com.cn/problem/P3942
	//                                https://atcoder.jp/contests/arc116/tasks/arc116_e
	minDominatingSetOfTree := func(n int, g [][]int, a []int) int { // 无根树
		const inf int = 1e18
		var f func(int, int) (chosen, bySon, byFa int)
		f = func(v, fa int) (chosen, bySon, byFa int) {
			chosen = a[v] // 1
			extra := inf
			for _, w := range g[v] {
				if w != fa {
					c, bs, bf := f(w, v)
					m := min(c, bs)
					chosen += min(m, bf)
					bySon += m
					byFa += m
					extra = min(extra, c-bs)
				}
			}
			bySon += max(extra, 0)
			return
		}
		chosen, bySon, _ := f(0, -1)
		return min(chosen, bySon)
	}

	// EXTRA: 每个被支配的点，仅被一个点支配
	// Kaoshiung06，紫书例题 9-14，UVa 1218 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3659

	// 树上最大匹配
	// g[v] = ∑{max(f[son],g[son])}
	// f[v] = max{1+g[son]+g[v]−max(f[son],g[son])}
	// https://codeforces.com/blog/entry/2059
	// https://blog.csdn.net/lycheng1215/article/details/78368002
	// https://vijos.org/p/1892
	maxMatchingOfTree := func(n int, g [][]int) int { // 无根树
		cover, nonCover := make([]int, n), make([]int, n)
		var f func(int, int)
		f = func(v, fa int) {
			for _, w := range g[v] {
				if w != fa {
					f(w, v)
					nonCover[v] += max(cover[w], nonCover[w])
				}
			}
			for _, w := range g[v] {
				cover[v] = max(cover[v], 1+nonCover[w]+nonCover[v]-max(cover[w], nonCover[w]))
			}
		}
		f(0, -1)
		return max(cover[0], nonCover[0])
	}

	// 树上完美匹配子集个数
	// https://codeforces.com/problemset/problem/1032/F

	// todo 给一棵树和树上的一些关键节点，选 m 个点，使得关键节点到这些点中距离的最小值的最大值最小，求这个值
	//      https://www.luogu.com.cn/problem/P3523

	// 换根 DP / 二次扫描法
	// 【图解】一张图秒懂换根 DP！（Python/Java/C++/Go/JS）https://leetcode.cn/problems/sum-of-distances-in-tree/solution/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/
	// https://codeforces.com/blog/entry/20935
	// https://ei1333.hateblo.jp/entry/2017/04/10/224413
	//
	// todo 题集 https://atcoder-tags.herokuapp.com/tags/Dynamic-Programming/Every-Direction-DP
	//
	// LC310 也可以用拓扑排序的思想 https://leetcode.cn/problems/minimum-height-trees/
	// - https://codeforces.com/problemset/problem/1881/F
	// LC834 https://leetcode.cn/problems/sum-of-distances-in-tree
	// https://codeforces.com/problemset/problem/763/A 1600（有更巧妙的做法）
	// https://codeforces.com/problemset/problem/219/D 1700
	// - LC2858 https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/
	// - LC2581 https://leetcode.cn/problems/count-number-of-possible-root-nodes/
	// https://codeforces.com/problemset/problem/1822/F 1700
	// https://codeforces.com/problemset/problem/1324/F 1800 类似最大子数组和
	// https://codeforces.com/problemset/problem/109/C 1900 也有组合数学做法
	// https://codeforces.com/problemset/problem/1092/F 1900
	// https://codeforces.com/problemset/problem/1882/D 1900
	// https://codeforces.com/problemset/problem/337/D 2000
	// https://codeforces.com/problemset/problem/791/D 2100
	// https://codeforces.com/problemset/problem/1187/E 2100
	// https://codeforces.com/problemset/problem/543/D 2300 注意不存在逆元的情形
	// https://codeforces.com/problemset/problem/1626/E 2400
	// https://codeforces.com/problemset/problem/1794/E 2400
	// https://codeforces.com/problemset/problem/1691/F 2500 计数
	// https://codeforces.com/problemset/problem/1320/E 3000 虚树
	// https://atcoder.jp/contests/dp/tasks/dp_v
	// https://atcoder.jp/contests/abc222/tasks/abc222_f 还可以用直径做 
	// todo https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_m
	//  https://atcoder.jp/contests/abc337/tasks/abc337_g
	// https://www.luogu.com.cn/problem/P3047 对于每个点 v，计算到点 v 距离为 k 的点权和（k 是定值）
	// https://www.luogu.com.cn/problem/P3478
	// https://www.luogu.com.cn/problem/P2986
	// https://ac.nowcoder.com/acm/contest/59717/F

	// 换根 DP · 其一（简单情况）
	// 第一次 DFS 算出以 0 为根的答案 ans0（一般是自底向上）
	// 第二次 DFS 基于 ans0，算出从节点 x 换到子节点 y 的答案的「变化量」，从而计算出其它节点的答案（一般是自顶向下）
	//
	// 每个点到其余点的距离之和 LC834 https://leetcode.cn/problems/sum-of-distances-in-tree
	// - 【图解】一张图秒懂换根 DP！https://leetcode.cn/problems/sum-of-distances-in-tree/solution/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/
	// - 变形：把距离之和改成每个距离的平方之和、立方之和
	// - 记录子树大小 size[v] 和子树每个节点的深度之和 sum(dep[sub])
	// - https://atcoder.jp/contests/abc348/tasks/abc348_e 点权版本
	// https://atcoder.jp/contests/abc220/tasks/abc220_f
	// https://codeforces.com/problemset/problem/1324/F 1800 类似最大子数组和
	// https://codeforces.com/problemset/problem/109/C 1900 也有组合数学做法
	// https://codeforces.com/problemset/problem/238/C 2100 有 O(n) 做法
	// https://codeforces.com/problemset/problem/791/D 2100 任意两点距离除以 k 的上取整之和
	// https://atcoder.jp/contests/abc160/tasks/abc160_f 2048=CF2260
	// https://codeforces.com/problemset/problem/494/D 2700 式子变形
	reroot1 := func(g [][]int) []int {
		ans := make([]int, len(g))
		size := make([]int, len(g))
		var dfs func(int, int, int)
		dfs = func(v, fa, depth int) {
			ans[0] += depth // 点相关
			size[v] = 1
			for _, w := range g[v] {
				if w != fa {
					dfs(w, v, depth+1)
					// ans[0] += ... // 边相关
					size[v] += size[w]
				}
			}
		}
		dfs(0, -1, 0)

		var reroot func(int, int)
		reroot = func(v, fa int) {
			for _, w := range g[v] {
				if w != fa {
					ans[w] = ans[v] + len(g) - size[w]*2 // 1-e.inv*2
					reroot(w, v)
				}
			}
		}
		reroot(0, -1)
		return ans
	}

	// 换根 DP · 其二（维护最大次大）
	// LC3241 https://leetcode.cn/problems/time-taken-to-mark-all-nodes/
	// https://codeforces.com/problemset/problem/1822/F 1700
	// https://codeforces.com/problemset/problem/1866/K 2500 凸包
	// https://codeforces.com/problemset/problem/633/F 2600 计算最大次大第三大（也可以直接树形 DP，无需换根）
	reroot2 := func(g [][]struct{ to, wt int }) []int {
		nodes := make([]struct{ fi, se, fiW int }, len(g))
		var dfs func(int, int) int
		dfs = func(v, fa int) int {
			p := &nodes[v]
			for _, e := range g[v] {
				w := e.to
				if w == fa {
					continue
				}
				d := dfs(w, v) + e.wt // 从 v 出发，往 w 方向的最大链和
				if d > p.fi {
					p.se = p.fi
					p.fi = d
					p.fiW = w
				} else if d > p.se {
					p.se = d
				}
			}
			return p.fi
		}
		dfs(0, -1)

		ans := make([]int, len(g))
		var reroot func(int, int, int)
		reroot = func(v, fa, up int) {
			p := nodes[v]
			ans[v] = max(up, p.fi) // 从 v 出发的最大链和
			for _, e := range g[v] {
				w := e.to
				if w == fa {
					continue
				}
				down := p.fi
				if w == p.fiW {
					down = p.se // 对于 w 来说，上面要选次大的
				}
				reroot(w, v, max(up, down)+e.wt)
			}
		}
		reroot(0, -1, 0)
		return ans
	}

	// 换根 DP · 其三（前后缀分解写法，适用性最广）
	// 使用时根据题目修改 data unit moveEdge merge
	// https://nyaannyaan.github.io/library/tree/rerooting.hpp.html
	// https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
	// https://atcoder.jp/contests/dp/tasks/dp_v 母题
	// https://codeforces.com/contest/1822/problem/F 1700
	// https://codeforces.com/problemset/problem/543/D 2300
	// https://atcoder.jp/contests/abc160/tasks/abc160_f
	// https://atcoder.jp/contests/abc222/tasks/abc222_f
	rerootPreSuf := func(g [][]int, root int) {
		// type data struct{ x, y int }
		type data int
		const unit data = 0
		// 返回 d 在通过 v-w 边之后的结果    *也可以传入边权
		// swap=true 表示 v-w 是换根时的那条边
		moveEdge := func(d data, v, w int, swap bool) data {
			return d + 1 // add weight from v to w
		}
		// 返回 p 和 q 合并后的结果（p 和 q 已经包含边的信息）
		merge := func(p, q data) data {
			return max(p, q) // p + q
		}

		// 以 root 为根时的子树信息
		subData := make([]data, len(g))
		var dfs func(int, int)
		dfs = func(v, fa int) {
			res := unit
			for _, w := range g[v] {
				if w == fa {
					continue
				}
				dfs(w, v)
				res = merge(res, moveEdge(subData[w], v, w, false)) // v-w 边
			}
			subData[v] = res
		}
		dfs(root, -1)

		ansAtRoot := make([]data, len(g))
		var reroot func(int, int, data)
		reroot = func(v, fa int, movedFaData data) {
			// 必要时特判 fa < 0 的情况
			ansAtRoot[v] = merge(movedFaData, subData[v])

			// suf 是 g[v] 的子树后缀汇总信息（已经包含 v-g[v][i] 边）
			ngv := len(g[v])
			suf := make([]data, ngv+1)
			suf[ngv] = unit
			for i := ngv - 1; i >= 0; i-- {
				w := g[v][i]
				if w != fa {
					suf[i] = merge(suf[i+1], moveEdge(subData[w], v, w, false)) // v-w 边
				} else {
					suf[i] = suf[i+1]
				}
			}

			// pre 是 g[v] 子树前缀汇总信息（已经包含 v-g[v][i] 边）
			pre := unit
			for i, w := range g[v] {
				if w == fa {
					continue
				}
				// mergedData 是除了 subData[w] 以外的子树汇总信息（已经包含 v-g[v][i] 边）
				mergedData := merge(movedFaData, merge(pre, suf[i+1]))
				reroot(w, v, moveEdge(mergedData, w, v, true))      // w-v 边（以 w 为根）
				pre = merge(pre, moveEdge(subData[w], v, w, false)) // v-w 边
			}
		}
		reroot(root, -1, unit)

		for _, res := range ansAtRoot {
			_ = res
			// ...
		}
	}

	// 树上所有路径的位运算与(&)的和
	// 单个点也算路径
	// 解法：对每一位，统计仅含 1 的路径个数
	// a[i] <= 2^20
	// https://ac.nowcoder.com/acm/contest/10167/C
	andPathSum := func(g [][]int, a []int) int {
		const mx = 21
		ans := 0
		for i := 0; i < mx; i++ {
			cntOnePath := 0
			var f func(v, fa int) int
			f = func(v, fa int) int {
				one := a[v] >> i & 1
				cntOnePath += one
				for _, w := range g[v] {
					if w != fa {
						o := f(w, v)
						if one > 0 {
							cntOnePath += one * o
							one += o
						}
					}
				}
				return one
			}
			f(0, -1)
			ans += 1 << i * cntOnePath
		}

		{
			// 另一种做法是对每一位，用并查集求出 1 组成的连通分量，每个连通分量对答案的贡献是 sz*(sz+1)/2
			n := len(a)
			fa := make([]int, n)
			var find func(int) int
			find = func(x int) int {
				if fa[x] != x {
					fa[x] = find(fa[x])
				}
				return fa[x]
			}
			merge := func(from, to int) { fa[find(from)] = find(to) }

			ans := 0
			for i := 0; i < mx; i++ {
				for j := range fa {
					fa[j] = j
				}
				sz := make([]int, n)
				for v, vs := range g {
					for _, w := range vs {
						if a[v]>>i&1 > 0 && a[w]>>i&1 > 0 {
							merge(v, w)
						}
					}
				}
				for j := 0; j < n; j++ {
					sz[find(j)]++
				}
				for j, f := range fa {
					if j == f && a[j]>>i&1 > 0 {
						ans += 1 << i * sz[j] * (sz[j] + 1) / 2
					}
				}
			}
		}
		return ans
	}

	// 树上所有路径的位运算或(|)的和
	// 单个点也算路径
	// 做法和上面类似，求出仅含 0 的路径的个数，然后用路径总数 n*(n+1) 减去该个数就得到了包含至少一个 1 的路径个数
	// 也可以用并查集求出 0 组成的连通分量

	// 树上所有路径的位运算异或(^)的和
	// https://atcoder.jp/contests/abc201/tasks/abc201_e
	// 上面链接是边权，这里改成点权，且路径至少有两个点
	// 解法：由于任意路径异或和可以用从根节点出发的路径异或和表示
	// 对每一位，统计从根节点出发的路径异或和在该位上的 0 的个数和 1 的个数，
	// 只有当 0 与 1 异或时才对答案有贡献，所以贡献即为这两个个数之积
	xorPathSum := func(g [][]int, a []int) int {
		n := len(a)
		const mx = 30
		cnt := [mx]int{}
		xor := 0
		var f func(v, fa int)
		f = func(v, fa int) {
			xor ^= a[v]
			for _, w := range g[v] {
				if w != fa {
					f(w, v)
				}
			}
			for i := 0; i < mx; i++ {
				cnt[i] += xor >> i & 1
			}
			xor ^= a[v]
		}
		f(0, -1)
		ans := 0
		for i, c := range cnt {
			ans += 1 << i * c * (n - c)
		}
		return ans
	}

	// 树上所有路径的位运算异或(^)的异或和
	// 这里的路径至少有两个点
	// 方法是考虑每个点出现在多少条路径上，若数目为奇数则对答案有贡献
	// 路径分两种情况，一种是没有父节点参与的，树形 DP 一下就行了；另一种是父节点参与的，个数就是 子树*(n-子树)
	// https://ac.nowcoder.com/acm/contest/272/B
	xorPathXorSum := func(g [][]int, a []int) int {
		n := len(a)
		ans := 0
		var f func(v, fa int) int
		f = func(v, fa int) int {
			cnt := 0
			sz := 1
			for _, w := range g[v] {
				if w != fa {
					s := f(w, v)
					cnt += sz * s
					sz += s
				}
			}
			cnt += sz * (n - sz)
			// 若一个点也算路径，那就再加一。或者在递归结束后把 ans^=a[0]^...^a[n-1]
			if cnt&1 > 0 {
				ans ^= a[v]
			}
			return sz
		}
		f(0, -1)
		return ans
	}

	_ = []any{
		mapDP,
		maxSubarraySum, maxSubarraySumWithRange, maxTwoSubarraySum,
		maxAlternatingSumDP, maxAlternatingSumGreedy,
		slopeTrick,
		minimumArea,

		lcs, lcsCount,
		lisSlow, lis, lisAll, lisModify, lisRollback, cntLis, lcis, lcisPath, countLIS,
		distinctSubsequence,
		palindromeO1Space, isPalindrome, minPalindromeCut,

		zeroOneKnapsack, zeroOneKnapsackExactlyFull, zeroOneKnapsackAtLeastFillUp, zeroOneWaysToSum, zeroOneKnapsackLexicographicallySmallestResult, zeroOneKnapsackByValue,
		unboundedKnapsack, unboundedWaysToSum,
		boundedKnapsack, boundedKnapsackBinary, boundedKnapsackMonotoneQueue, boundedKnapsackWays, boundedKnapsackWays2,
		groupKnapsack, groupKnapsackFill,
		treeKnapsack, treeKnapsackWeighted,

		// 划分型 DP
		splitDP, splitDPWithLimit,

		longestPalindromeSubsequence, mergeStones, countPalindromes,

		// 期望 DP

		// 状压 DP
		permDP, permDP2, tsp, longestSimplePath, countCycle,
		subsubDP, subsubDP2, subsubDPMemo, sosDP, plugDP,

		// 数位 DP
		digitDP, digitDP2, calcSum, digitDP2D, kth666,

		// 倍增
		binaryLifting, binaryLifting2,

		// 数据结构优化 DP

		// 斜率优化
		convexHullTrick, convexHullTrick2,
		wqs,

		diameter, countDiameter, maxDisOfDiffColor, countPath, countVerticesOnDiameter, maxPathSum,
		maxIndependentSetOfTree, minVertexCoverOfTree, minDominatingSetOfTree, maxMatchingOfTree,
		reroot1, reroot2, rerootPreSuf, // 换根 DP
		andPathSum, xorPathSum, xorPathXorSum,
	}
}