题意
(n) 根木棍，长度为 (1,2,...,n)。用其中三条边构成一个三角形，求方案数。
题解
容易观察到答案的递推公式：
- (f_i = 0)（当 (i = 1)）
- (f_i = f_{i-1} + k imes (k-1))（当 (i = 2k)）
- (f_i = f_{i-1} + k imes k)（当 (i = 2k+1)）
题意
你有一个 (n imes m) 的网格图，现在你要将 (k) 个人放在网格中，满足：
-
网格图的四个边都至少有一个人。
-
每个格子上不能有两个人。
-
每个人必须都有位置。
答案对 (10^6+7) 取模。
题解
简单容斥。
定义 (A,B,C,D)为 第一行 / 最后一行 / 第一列 / 最后一列 没有人的方案，则答案为（(C_{n imes m}^{k}) - (A cap B cap C cap D)）。
题意
给定数列 (a(|a|=n))，依次计算相邻两数之和得到一个新数列，重复操作，直到数列仅剩一个数。
求这个数除以给定值 (m) 的余数与哪些数无关。
题解
容易观察到原数列中每个数被加的次数是杨辉三角的第 (n) 列。
将 (m) 分解质因数，依次维护 (C_{n}^{x}) 是否被 (m) 整除即可。可以使用公式：(C_{n}^{i}=C_{n}^{i-1} imes dfrac{(n - i+1)}{i})。
题意
给你两个 (6)行 (5) 列的矩阵，要求你从这之中找出密码，找密码的规则：密码中左数第 (i) 个字母，必须在两个矩阵左数第 (i) 列中均出现。密码长度为 (5)。
题解
求出字典序最小的密码，依次迭代即可。与组合数无关。
题意
求长为 (n) 的 (01) 序列中有多少个满足：至少有 (3) 个连续的 (1)。
题解
设 (f_i) 表示长为 (i) 时的方案数，分类讨论：
- 除去新加入的第 (i) 个，序列中已经有 (3) 个连续的 (1) 的方案数：(f_{i-1} imes 2)
- 除去新加入的第 (i) 个，序列中没有 (3) 个连续的 (1) 的方案数：(2^{i-1} - f_{i-4})
那么，(f_i = f_{i-1} imes 2 + 2^{i-1} - f_{i-4})。边界：(f_3 = 1)。
题意
有 (n) 根长度为 (1) 到 (n) 的棍子排列在一起，求从左边看能看见 (l) 根，从右边看能看见 (r) 根的方案数。
题解
考虑每次放入高度最小的杆子。
设 (f_{i,l,r})，状态意义如题意，则 (f_{i,l,r}) 可以从以下几种状态转移而来：
-
(f_{i-1,l,r} imes (i-2)) —— 只要不放在左侧和右侧，就看不见这根杆子
-
(f_{i-1,l-1,r}) (f_{i-1,l,r-1}) —— 放在左侧 / 右侧
待补。
题意
求有 (n) 个节点且满足深度相同的节点子树大小相同的树的数量。
题解
定义 (f_i)，状态意义如题意。
考虑新加入一个根，剩下的 (i-1) 个节点由若干个相同形态的子树构成，则有：
题意
求 (n) 个节点的环上没有公共点的边集个数。
题解
对于一条 (n) 个节点的链上的方案数 (f_n)，考虑最后一条边，如果选择它，那么这条边的两个顶点都不能选，有 (f_{n-2}) 种方案；如果不选择它，和 (n-1) 个节点时一样，有 (f_{n-1}) 种方案。
于是我们得到 (f) 的转移方程：
即 Fibonacci 数列。
在计算答案时，使用相同的套路，分类讨论是否选择环上的一条边 (x)。如果选择了 (x)，则有 (f_{n-2}) 种方案。如果不选择，那么相当于组成了一条长度为 (n) 的链，方案为 (f_{n})。
当然，OEIS 可以发现答案为 Lucas 数列，但和题目无关，不再阐述。
题意
求所有的对 ((n,k))，使得 (C_{n}^{k} = m)。
题解
只考虑 (n geq 2 imes k)，因为 (C_{n}^{k} = C_{n}^{n-k})，(n < 2 imes k) 的情况可以顺便求出。
考虑枚举 (k)，二分 (n)。(C_{2 imes k}^{k}) 增长速度极快，所以可以通过非常短的时间计算出答案。
题意
求满足以下条件，长为 (n) 的 (01) 串的数量：
- 第一位为 (1)
- 该串对应的十进制数被 (k) 整除
- (0) 和 (1) 的数量相等
题解
数位 DP。
设 (F_{i,j,mod}) 表示有 (i) 个 (0) (j) 个 (1) 目前 (mod k = mod) 的方案数。
显然每一步仅两种决策，记忆化搜索转移即可。由于先枚举的是高位，所以设这一步选择的是 (x(x in {0,1}))，那么下一步到达的状态应该是 (F_{i+[x=0],j+[x=1],mod imes 2 + x})。