题目列表

补集计数：全部三点组减去共线三点组；斜向用「两点间内点数 = gcd(dx,dy)−1」，再借 Σφ(t)=g 交换求和，把 O(mn) 的 gcd 求和降到 O(min(m,n))。

利用 Lucas 定理按 p 进制将组合数前缀和拆分为整块与散块，递归计算 S(n, k) mod 2333

隔板法把单调不降序列计数化为多重组合数，再用 hockey-stick 恒等式把按长度求和折叠成单个组合数，最后用 Lucas 定理按 10^6+3 进制拆位求值。

L 形棋盘拆成上下两个左对齐矩形，按上矩形的车数 i 分类：上矩形 C(b,i)·P(a,i)，下矩形可用列数被扣成 a+c-i，贡献 C(d,k-i)·P(a+c-i,k-i)，求和即答案。

Lucas 定理求组合数取模：预处理阶乘与逆元，把 C(n,m) mod p 按 p 进制拆成各位小组合数的乘积，用费马小定理求逆元。

指数 P=Σ_{k|N}C(N,k) 用费马小定理降幂；因 999911658=2×3×4679×35617，四路 Lucas 分求组合数后由中国剩余定理合并成指数。

通过快速幂求出常数项 g(x) = x^x mod 1000，再利用隔板法将求正整数解组数转化为组合数 C(g(x)-1, k-1) 的高精度计算。

拆点把 1~9 的边权摊平成 9N 个无权状态，再用邻接矩阵快速幂统计恰好 T 步的走法数。

把「号码后缀与不吉利数字的最长公共前缀长度」当作状态，用 KMP 失配链建出转移矩阵，再做矩阵快速幂，在 O(m^3 log n) 内计数不含给定子串的 n 位数字串。

利用 Lucas 定理将大组合数按质数模数 p 分解为 p 进制位，结合快速幂与逆元计算 C(n, m) mod p。

分解 A 得 σ(A^B)=∏(1+p+…+p^{eB})，等比和用倍增递推求，只靠乘加不碰逆元，避开 p≡1 (mod 9901) 时 p-1 不可逆的陷阱。

把递推写成矩阵 M=[[1,1],[1,0]]，f_n 是 M^(n-1) 的左上角；对指数做二进制拆分，用矩阵快速幂把 O(n) 降到 O(log n)。

用恒等式 S_n = f_{n+2} - 1 把前缀和化为单项，再用 2×2 转移矩阵的快速幂在 O(log n) 次矩阵乘法内求出 f_{n+2} mod m。

通过构建 2x2 状态转移矩阵并应用矩阵快速幂，在 O(log n) 时间内求斐波那契数列第 n 项模 10000 的值。

跳 k 次后位置为 (x+kd) mod n，问题化为同余方程 kd ≡ y-x (mod n)：gcd(d,n) 不整除差值即无解，约简后求模逆元得到最小非负解。

把 k 位系统的循环步数写成线性同余方程 Ct ≡ B-A (mod 2^k)，用扩展欧几里得判无解并求最小非负解。

从小到大枚举山洞数 M，利用扩展欧几里得算法求解线性同余方程，检验任意两野人是否在共同有生之年相遇。

逐条合并同余式：代入得线性同余方程 m₁k ≡ a₂-a₁ (mod m₂)，gcd 不整除差值即无解，约去公因子后求模逆元得到最小非负 k，模数合并为 lcm。

p 为质数时三问分治：快速幂求 y^z，费马小定理求逆元解线性同余方程，BSGS 分表 O(√p) 求最小离散对数。

把猪数与猪圈的关系写成同余方程组，逐条合并剩余类：由 x=v+mt 解出 t≡(b-v)·m⁻¹ (mod a)，用 pow(m,-1,a) 求逆元，模数累积成 ∏aᵢ。

把约数和公式 σ(n)=∏(1+p+…+p^a) 视为对 S 的编号段分解，DFS 按质数递增枚举质数幂，指数为 1 的大质数因子靠 rest-1 的素性判定收尾。

把 t 次跳跃后相遇写成同余方程 (m-n)t≡y-x(mod L)，用扩展欧几里得求特解，再按周期 L/gcd 归一化出最小非负解；gcd 不整除差值则无解。

用 Stein 二进制 GCD 把大数取模换成移位与减法，在 10^10000 量级上高效求最大公约数。

由 lcm(x,b0)=b1 得 x 必整除 b1，枚举 b1 的约数并验证 gcd 与 lcm 两个条件即可计数。

将整数分解质因数，根据算术基本定理转化为质因子多重集的全排列计数问题。

冲突边只存在于质数与它的倍数之间，质数涂 1、合数涂 2 即为最优，答案用一次埃氏筛求出。

把方程变形为 (x−n!)(y−n!)=(n!)²，答案即 (n!)² 的约数个数：线性筛最小质因子分解 1..n 累加指数后连乘 ∏(2e+1)。

通过质因子指数单调不增性质剪枝，用 DFS 搜索不超过 n 的约数最多且数值最小的反素数。

L,R 可达 2^31 而区间长度只有 10^6，先筛出 [2,√R] 的小质数，再用它们对长度 10^6 的区间做分段筛，一次线性扫描取相邻质数的最小/最大差。

值域统计 cnt 后让每个出现过的数字向自己的倍数广播，答案为 Σ_{d|A_i} cnt[d] − 1。

正难则反：答案 = m^n − m(m−1)^(n−1)，补集逐位独立相乘，两次模快速幂 O(log n) 出解。

以「上一个新厂位置 j」为决策写出一维 DP，前缀和展开后转移变成直线族在 pos_i 处取最小值；斜率与查询点双单调，单调队列维护下凸壳把 O(n^2) 降到 O(n)。

把建仓划分写成连续分段的线性 DP，用前缀和把转移拆成「只与 i 有关」加「若干直线在 X_i 处的最小值」，再用单调队列维护下凸壳做斜率优化，时间 O(n)。

连续分段 DP 展开后每个切点 j 变成一条直线 l_j(u)=S_j·u+Y_j，a<0 与 x_i≥1 使查询点与斜率双单调，单调队列维护上包络把 O(n²) 降到 O(n)。

平方代价分段 DP 的斜率优化：把转移来源看成点 (S[j], dp[j]+S[j]²)，单调队列维护下凸壳，队头即最优决策，O(N) 完成转移。

把启动费重记账为『批开始时对其后所有任务计费』消掉批数，DP 变成斜率单调直线族的最小值查询，下凸壳二分 O(N log N)。

分批任务调度的费用 DP 用斜率优化到 O(n)：换记账次序后转移化为单调队列维护下凸壳，用斜率单调的直线切凸壳取最优切点。

猫只依赖出发下限 a=T-s[H]，排序后每位饲养员接一段连续的猫；DP 转移整理成直线族，双单调性下用单调队列维护下凸壳，O(P·M) 求最小等待和。

把分段 DP 的转移展开成直线族，用 T[i]=S[i]+i 带来的斜率与查询双单调性，在单调队列上维护下凸壳，O(N) 求出最小装箱费用。

交换求和次序把启动费一次记在批上，分批 DP 的转移只依赖前缀和，O(N^2) 求出最小总费用。

多重背包恰好凑 k 的最少硬币数：按面值分阶段松弛，同余类内换元成滑动窗口最小值，单调队列 O(nk) 完成每种面值的批量更新。

二分最长空题段长度 L，用单调队列维护平移窗口的最小值，在 O(n) 内判定可行性，总复杂度 O(n log n)。

二维滑动窗口最值：每行先用单调队列压出横向窗口 min/max，再对行窗口表每列滑一次得到每个 n×n 方格的最值，O(ab) 求最小差值。

以第 i-W-1 天的 DP 快照为前驱，把买卖转移拆成滑动窗口最大值，单调队列摊还 O(1)，总复杂度 O(T·MaxP)。

间隔约束的一维 DP：dp[i] 表示第 i 座必点火时前缀的最小代价，转移是长度 m 滑动窗口求最小值，用单调队列把 O(nm) 降到 O(n)。

把油量减距离转成环形差额序列，顺、逆时针各自用前缀最小值与倒序滚动两段合并 O(n) 判定每个起点，任一方向可行即输出 TAK。

把每个小朋友只依赖的连续 5 个围栏压成 32 种窗口状态，滑动时右移补位并在窗口起点结算得分，最后枚举初窗口的 32 种取值破环取最大。

把限长子段和写成前缀和之差，单调队列维护窗口内最小前缀和，O(n) 求最大连续和。

前缀和加单调队列优化的一维 DP：转移拆成只含 j 的 dp[j-1]-S_j 与只含 i 的 S_i，在长度 K 的滑动窗口上均摊 O(1) 求最大值。

按位差分统计区间数码个数。

逐行状态压缩 DP：枚举每行无左右相邻的国王摆放状态，行间用三方向位运算判相容，按已放国王数计数方案总数。

按行逐行做状态压缩 DP：每行种植方案压成无相邻 1 的位掩码，转移只保留与上一行按位与为 0 的掩码，滚动计数并对 10^8 取模。

NOI2001 炮兵阵地：逐行状态压缩 DP，单行内保证炮兵间距大于 2，行间同时检查前两行的同列冲突，山地不可部署。

数位统计：答案用 F(b)−F(a−1) 差分，F(n) 按「第 i 位首次小于上界」分段，未受限的低位用可重组合 C(r+9−l, r) 一次算完。

前缀相减把双侧区间变成 [0, x] 计数，再按位记忆化 (pos, 余数, 是否贴上界)：只记数字和 mod N 的余数，代价与位数和 N 同阶而与区间长度无关。

通过区间前缀和差分将问题转化为求不超过 n 的合法数，借助数位 DP 与记忆化搜索按位统计相邻数位差绝对值不小于 2 的正整数方案数。

数位 DP 维护满足条件的数字个数、一次方和与平方和，通过完全平方公式展开实现状态转移。

树形 DP：答案与根无关，任取度数大于 1 的节点为根，状态记录根到该点路径上最后一个有色节点的颜色（黑/白/尚无），自底向上在给该点着色与沿用上方颜色之间取最小值。

把「K 个互不相等的 B 的幂之和」等价转化为 B 进制只含 0/1 且恰有 K 个 1 的数，前缀相减后从高位卡上界，每遇到松绑就用组合数一次收账。

树的最小权支配集：设 dp0/dp1/dp2 分别表示结点自己设看守、被儿子看到、只能指望父亲看到三种状态，自底向上树形 DP 求最小经费。