Cannon  有一个 的棋盘，第一行摆了 个炮，第二行摆了 个炮。 依次求发生 个炮吃炮事件的方案数。 有考虑两行之间的顺序和不考虑两行之间的顺序 两个子问题。   一行 个炮操作 次的方案是 。 设 ，问题即求$$ 问题一直接递推，问题二维护一个组合数前缀和即可。 // Author: HolyK // Created: Tue Jul 20 21:51:46 2021 #include <bits/stdc++.h> #define dbg(a...) fprintf(stderr, a) template <class T, class U> inline bo...

Arithmetic Progression  给定每个元素互不相同的序列 ，求排序后能构成等差数列的区间个数。    结论：对于元素互不相同的序列 ，其排序后是公差为 等差数列的充要条件是 且 。 证明： 必要性： 设 且 排序后为等差数列，则 是 的一个排列，所以 。 根据辗转相减法： 。 充分性： 不妨设 ，。 设 ，则 ，所以 ，为等差数列。  于是问题转化为求 的区间个数。  由上面的证明不难发现 ，所以用线段树维护这个值的最小值以及最小值的个数。 每次移动右端点时，极差只需修改一个区间，但每个点的 都可能被修改。 考虑一个点作为左端点的区间 被修改的次数，发现每次修改至少会折半，所...