插板
Catalan 数
应用一般有两种模型：
- 折线型。
- 二叉树型。
?
CF1696E Placing Jinas
诈骗题。“最小值”纯诈骗，实际上操作次数和操作顺序没半毛钱关系。
每个点上的操作次数就是从 $(0, 0)$ 到这个点的路径条数，这是容易理解的，一条路径带来一个玩偶。那么点 $(i, j)$ 的操作次数就是 $(i + j, i)$。
考虑统计答案：第 $i$ 列的答案为 $\sum\limits_{j = i}^{i + a_i - 1} \dbinom{j}{i}$，可以证明上式等于 $\dbinom{i + a_i}{i + 1}$，证明如下：
代码略。
CF571A Lengthening Sticks
浪费我一整天时间，差评。
你好，我不是数学大神，我不会正着做。那就反着做啊！
首先总方案数可以当成把 $l$ 个相同物体分成四组（$a,b,c$ 三组，剩下一组是不用的），可以空，显然插板得到总方案数为 $\dbinom{l + 3}{3} = (l + 3) ^ { \underline{3} }$。
然后考虑不合法的方案，即 $a^{\prime} + b^{\prime} \le c^{\prime}$ 这类。下面我们按照 $a^{\prime} + b^{\prime} \le c^{\prime}$ 的情况讨论。
为方便讨论，下文我们记 $A = a + b - c$。
首先，若 $A > 0$，那么我们要把 $c$ 至少填到 $a + b$ 再说。
考虑枚举给 $c$ 加上 $i \hspace{1mm} (\max(0, A) \le i \le L)$ 个长度，那么 $a + b$ 最多就要加上 $B = \min(L - i, -A + i)$ 个单位长度，总共有 $\dfrac{(B + 1) \times (B + 2)}{2}$ 种方案数。
这么做是 $O(L)$ 的，考虑优化。
不想写了，挂 tj 吧。最后做到了 $O(1)$。
const int maxn = 2e6 + 7;int a, b, c, l;inline int Calc(int A, int L) {if(A > L) return 0;int Lim = (L - A) >> 1; int ret = (Lim + 3) * (Lim + 2) * (Lim + 1) / 3;if(!((L + A) & 1)) ret -= (Lim + 1) * (Lim + 2) / 2; if(A < 0) ret -= (2 - A) * (1 - A) * (-A) / 6;return ret;
}signed main() {
// freopen("saki.in", "r", stdin);
// freopen("saki.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> a >> b >> c >> l;if(a - b - c >= l || b - a - c >= l || c - a - b >= l) { cout << 0; return 0; }cout << (l + 3) * (l + 2) * (l + 1) / 6 - Calc(a + b - c, l) - Calc(a + c - b, l) - Calc(b + c - a, l); return 0;
}
CF1929F Sasha and the Wedding Binary Search Tree
棒棒糖题，这道题，$800$ 吧。
这不二叉搜索树吗，你中序遍历一遍不就有序了？找到一串连续的 $-1$ 两边的位置 $i$ 和 $j$，显然这就转化成了一个 $x_1 + x_2 + \cdots + x_{j - i} = a[j] - a[i]$ 的非负整数解问题，插板解决。
注意开头结尾的特殊处理，具体见代码。
const int maxn = 5e5 + 7;int _;
int n, c;
int inv[maxn];
int ls[maxn], rs[maxn], val[maxn], a[maxn], tot;inline void dfs(int u) {if(u <= 0) return ;if(ls[u] > 0) dfs(ls[u]);a[++tot] = val[u];if(rs[u] > 0) dfs(rs[u]);
}inline int C(int n, int m) {int ret = 1;F(i, n - m + 1, n) (ret *= i) %= mod;F(i, 1, m) (ret *= inv[i]) %= mod;return ret;
}signed main() {
// freopen("saki.in", "r", stdin);
// freopen("saki.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);inv[0] = inv[1] = 1;F(i, 2, maxn - 1) inv[i] = (mod - mod / i) * inv[mod % i] % mod;cin >> _;while(_--) {cin >> n; cin >> a[n + 1]; // a[n + 1] 的值就是可以取到的最大值。F(i, 1, n) cin >> ls[i] >> rs[i] >> val[i];tot = 0; dfs(1);int lst = 1, pos = 0, ans = 1; // 开头最小值可以从 1 开始取。F(i, 1, n + 1) {if(a[i] != -1) {if(pos != i - 1) (ans *= C(a[i] - lst + i - pos - 1, i - pos - 1)) %= mod; lst = a[i], pos = i;}}cout << ans << '\n';}return 0;
}
CF1227F2 Wrong Answer on test 233 (Hard Version)
这题啊，exciting！
首先我们知道，对于一个答案 $a_i$，它的得分情况仅有 $0 \rightarrow 0,0 \rightarrow 1,1 \rightarrow 0,1 \rightarrow 1$ 四种，并且我们可以发现，对于每一个 $a_i \ne h_i$ 且 $a_i = h_{(i mod n) + 1}$ 即 $0 \rightarrow 1$ 的情况，我们都可以构造有且仅有一个 $a_i = h_i$ 且 $a_i \ne h_{(i mod n) + 1}$ 即 $1 \rightarrow 0$ 与其唯一对应，将其扩展到全局，我们可以得知，$a^{\prime} > a$ 与 $a^{\prime} < a$ 的方案数相同，这使得我们只需要关注总方案数与 $a^{\prime} = a$ 的方案数。
总方案数显然是 $k^n$ 的，我们考虑 $a^{\prime} = a$ 的方案数怎么求。首先我们找到所有 $a_i \ne a_{(i \mod n) + 1}$ 的位置数 $a$，枚举我们有 $k \hspace{1mm} (0 \le k \le \lfloor \dfrac{a}{2} \rfloor)$ 个 $0 \rightarrow 1$ 的位置，同样我们就有 $k$ 个 $1 \rightarrow 0$ 的位置，其他 $a_i \ne a_{(i \mod n) + 1}$ 的位置有 $k - 2$ 种选择，剩下的位置随便放即可，因为只有可能是 $0 \rightarrow 0,1 \rightarrow 1$。
const int maxn = 5e5 + 7;int n, k;
int a[maxn], jc[maxn], inv[maxn], inj[maxn];inline int kasumi(int a, int b) {int ret = 1;for(; b; b >>= 1) {if(b & 1) (ret *= a) %= mod;(a *= a) %= mod;} return ret;
}inline int C(int n, int m) { return jc[n] * inj[m] % mod * inj[n - m] % mod; }signed main() {
// freopen("saki.in", "r", stdin);
// freopen("saki.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);jc[0] = jc[1] = inv[0] = inv[1] = inj[0] = inj[1] = 1;F(i, 2, maxn - 1) {jc[i] = jc[i - 1] * i % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;inj[i] = inj[i - 1] * inv[i] % mod;}cin >> n >> k;F(i, 1, n) cin >> a[i];int cnt1 = 0, cnt2 = 0;F(i, 1, n) cnt1 += (a[i] == a[i % n + 1]), cnt2 += (a[i] != a[i % n + 1]);int del = 0;F(i, 0, (cnt2 >> 1)) (del += C(cnt2, i) * C(cnt2 - i, i) % mod * kasumi(k - 2, cnt2 - i - i) % mod * kasumi(k, cnt1) % mod) %= mod;cout << ((kasumi(k, n) + mod - del) * kasumi(2, mod - 2) % mod);return 0;
}
P7118 Galgame
旮旯隔膜好玩！！！
首先我们考虑节点数小于 $n$ 的情况，这一部分显然是 $\sum\limits_{i = 1}^{n - 1} H_i$，其中 $H_i$ 表示卡特兰数。
我们再递归下去逐一考虑。记以 $i$ 为根的子树中不有趣的情况有 $f_i$ 种。考察左右子树节点数各相同，不有趣的情况：显然只要左子树不有趣，那么右子树再请什么高人都没救了，而如果左子树有趣，右子树一定得不有趣。所以这一块情况总数为 $f_{ls_u} \times H_{siz_{rs_u}} + f_{rs_u}$。
再考虑左右子树节点数各不相同的情况，显然是 $\sum\limits_{i = 0}^{siz_{ls_u} - 1} H_i \times H_{n - i - 1}$ 的。
但是这么做是 $O(n^2)$ 的，怎么优化呢？
我们发现复杂度瓶颈就在这个 $siz_{ls_u}$ 上，当它太大时就容易爆炸，而这时 $siz_{rs_u}$ 偏偏又更小，所以当 $siz_{ls_u} > siz_{rs_u}$ 时，直接通过总方案数减去不合法的方案数求解，即 $H_{siz_u} - \sum\limits_{i = 0}^{siz_{rs_u}} H_i \times H_{n - i - 1}$。
参照树上启发式合并，这样的时间复杂度是 $O(n \log n)$ 的。
const int maxn = 2e6 + 7;int n, k;
int ls[maxn], rs[maxn], siz[maxn];
int f[maxn], jc[maxn], inv[maxn], inj[maxn];inline int kasumi(int a, int b) {int ret = 1;for(; b; b >>= 1) {if(b & 1) (ret *= a) %= mod;(a *= a) %= mod;} return ret;
}inline int C(int n, int m) { return ( n < m ? 0 : jc[n] * inj[m] % mod * inj[n - m] % mod ); }
inline int Cat(int n) { return (C(n << 1, n) + mod - C(n << 1, n + 1)) % mod; }inline void dfs1(int u) {siz[u] = 1;if(ls[u]) { dfs1(ls[u]); siz[u] += siz[ls[u]]; }if(rs[u]) { dfs1(rs[u]); siz[u] += siz[rs[u]]; }
}inline void dfs2(int u) {if(!ls[u] && !rs[u]) return ;if(ls[u]) dfs2(ls[u]); if(rs[u]) dfs2(rs[u]);f[u] = (f[ls[u]] * Cat(siz[rs[u]]) % mod + f[rs[u]]) % mod;if(siz[ls[u]] <= siz[rs[u]])F(i, 0, siz[ls[u]] - 1) (f[u] += Cat(i) * Cat(siz[u] - i - 1) % mod) %= mod;else {(f[u] += Cat(siz[u])) %= mod;F(i, siz[ls[u]], siz[u] - 1) (f[u] += mod - Cat(i) * Cat(siz[u] - i - 1) % mod) %= mod;}
}signed main() {
// freopen("saki.in", "r", stdin);
// freopen("saki.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);jc[0] = jc[1] = inv[0] = inv[1] = inj[0] = inj[1] = 1;F(i, 2, maxn - 1) {jc[i] = jc[i - 1] * i % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;inj[i] = inj[i - 1] * inv[i] % mod;}cin >> n;F(i, 1, n) cin >> ls[i] >> rs[i];dfs1(1); dfs2(1);int ans = f[1];F(i, 1, siz[1] - 1) (ans += Cat(i)) %= mod;cout << ans;return 0;
}
AT_tenka1_2014_final_d 高橋君
以下为推柿子过程。
记 $f(n, m)$ 为 $\sum\limits_{i = 0} ^ {m} \dbinom{n}{i}$，我们有：
$$
f(n, m + 1) = \sum\limits_{i = 0}^{m + 1} \dbinom{n}{i} = f(n, m) + \dbinom{n}{m + 1} \
f(n, m - 1) = \sum\limits_{i = 0}^{m - 1} \dbinom{n}{i} = f(n, m) - \dbinom{n}{m} \
f(n + 1, m) = \sum\limits_{i = 0}^{m} \dbinom{n + 1}{i} \
= \sum\limits_{i = 1}^{m} \left (\dbinom{n}{i} + \dbinom{n}{i - 1} \right ) + \dbinom{n + 1}{0} \
= \sum\limits_{i = 0}^{m} \dbinom{n}{i} - 1 + \sum\limits_{i = 0}^{m} \dbinom{n}{i} - \dbinom{n}{m} + 1 \
= 2 \times \sum\limits_{i = 0}^{m} \dbinom{n}{i} - \dbinom{n}{m} \
= 2 \times f(n, m) - \dbinom{n}{m} \
\therefore 2 \times f(n - 1, m) - \dbinom{n - 1}{m} = f(n, m) \
\therefore f(n - 1, m) = \dfrac {f(n, m) + \dbinom{n - 1}{m}}{2}
$$
所以，我们可以在 $O(1)$ 的时间复杂度内移动 $n, m$，这使得我们可以运用莫队算法——一种处理点在二维平面中运动的 $O(n \sqrt n)$ 算法。
const int maxn = 2e5 + 7;int jc[maxn], inv[maxn], inj[maxn];
inline int C(int n, int m) { return ( n < m ? 0 : jc[n] * inj[m] % mod * inj[n - m] % mod ); }int q, B;
struct query { int l, r, id; bool operator < (const query &x) const {return (l / B == x.l / B ? (r == x.r ? 0 : ((l / B) & 1) ^ (r < x.r)) : l < x.l);}
} Q[maxn]; int ret = 1, L, R;
int ans[maxn];inline void LL() { (ret += C(L - 1, R)) %= mod; (ret *= inv[2]) %= mod; L--; }
inline void RL() { (ret += ret + mod - C(L, R)) %= mod; L++; }
inline void LR() { (ret += mod - C(L, R)) %= mod; R--; }
inline void RR() { (ret += C(L, R + 1)) %= mod; R++; }signed main() {
// freopen("saki.in", "r", stdin);
// freopen("saki.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);jc[0] = jc[1] = inv[0] = inv[1] = inj[0] = inj[1] = 1;F(i, 2, maxn - 1) {jc[i] = jc[i - 1] * i % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;inj[i] = inj[i - 1] * inv[i] % mod;}cin >> q; B = sqrt(q);F(i, 1, q) { cin >> Q[i].l >> Q[i].r; Q[i].id = i; }sort(Q + 1, Q + 1 + q);L = 0, R = 0;F(i, 1, q) {while(L > Q[i].l) LL();while(R < Q[i].r) RR();while(L < Q[i].l) RL();while(R > Q[i].r) LR();ans[Q[i].id] = ret;}F(i, 1, q) cout << ans[i] << '\n';return 0;
}
