\(\quad\)区间 \(\rm DP.\)
\(\quad\)设 \(dp_{i,j}\) 表示消除 \([l,r]\) 需要的最少步数。有两种转移 ：
- 若左右端点相等，那么直接继承 \([l+1,r-1]\) 的答案。
- 若左右端点不相等，那么枚举断点，继承左右区间答案相加。
\(\quad\)需要注意的是，区间端点相等也需要枚举断点更新答案。
\(\quad\)预处理区间长度为 \(1\) 和 \(2\) 的情况，时间复杂度 \(\Theta(n^3).\)
\(\quad\)树形 \(\rm DP\)，换根 \(\rm DP.\)
\(\quad\)首先发现绝对值不好处理，于是分两次计算，一次给白点赋值为 \(1\)，黑点为 \(-1\)，另一次相反。于是问题就转化成求一颗子树，最大化点权和。
\(\quad\)设 \(g_u\) 表示以 \(u\) 为根在 \(u\) 的子树内，强制选 \(u\) 最大的点权和，\(f_u\) 表示强制选 \(u\) 的最大点权和。\(g\) 的转移方程非常好推，于是考虑用换根 \(\rm DP\) 计算 \(f\)，首先把以 \(u\) 为根的子树在 \(f_{fa_u}\) 里的贡献减去，再考虑加不加上这个值。
\(\quad\)时间复杂度 \(\Theta(n).\)
\(\quad\)状压 \(\rm DP\)，虚树。
\(\quad\)考虑到只需要确定每个叶结点的相对大小就可以用贪心求出它们的编号，于是考虑状压。
\(\quad\)首先预处理 \(f_S\) 表示将 \(S\) 中的点到 \(1\) 的路径全部染色以后有颜色的结点个数，这个用树剖或虚树维护一下就可以算了。设 \(dp_S\) 表示只考虑 \(S\) 中的点的最大乘积，枚举不在 \(S\) 中的点 \(u\) 转移，可以发现 \(u\) 的点权是 \(n-f_{S\cup u}+1.\)
\(\quad\)需要注意的是，答案可能较大，比较大小的时候转换成对数即可。
\(\quad\)时间复杂度 \(\Theta(n\log n+leaf2^{leaf}).\)
\(\quad\)分类转移的普通 \(\rm DP.\)
\(\quad\)数位 \(\rm DP.\)
\(\quad\)数位 \(\rm DP.\)
\(\quad\)区间 \(\rm DP.\)
\(\quad\)设 考虑从大到小往外填数，\(dp_{l,r}\) 表示已经填完了 \([i,j]\) 的方案数。我们发现因为是从大到小，所以不需要管单峰的条件，并且发现只有三种填数方法，即两个都放在左边，右边或两边各放一个，判断一下放下去后合不合法即可。
\(\quad\)时间复杂度 \(\Theta(n^2+k).\)
\(\quad\)划分数。
\(\quad\)一开始发现是个完全背包，物品重量是 \(2^x.\)
\(\quad\)时间复杂度 \(\Theta(n\log n).\)
\(\quad\)后来发现还有一个更优的做法。考虑划分数的一般做法，每次可以添加一个 \(1\)，还可以使所有数 \(+1\)，但这个题不一样，我们不能让所有数 \(+1\)，而是只能让所有数 \(\times 2\)，转移方程 ：
\(\quad\)时间复杂度 \(\Theta(n).\)
\(\quad\)计数 \(\rm DP.\)
\(\quad\)易知若将每个 \(a_i\) 看成一个二进制位的集合 \(S_i\)，那么会给答案 \(f_{S_i‘}\) 都加上 \(1\)，其中 \(S_i‘\in S_i.\)
\(\quad\)如果直接按照 \(S\) 从大到小枚举并更新答案可能会算重，考虑会算重的原因，比如 \((111)_2\) 会使 \((110)_2\) 和 \((011)_2\) 都 \(+1\)，而 \((010)_2\) 既可以被 \((110)_2\) 更新又可以被 \((011)_2\) 更新，所以被更新了 \(2\) 次，而被更新两次的原因就是 \((111)_2\) 在同一时间既更新了第 \(1\) 位又更新了第 \(3\) 位。
\(\quad\)于是考虑从大到小枚举 \(k\)，如果 \(S\) 第 \(k\) 位是 \(1\)，那么可以将其减去，即 f[S - (1 << k)] += f[S].
\(\quad\)时间复杂度 \(\Theta(n\log n).\)
\(\large\rm *×\#10~最长递增子序列的数量\)
\(\quad\)树状数组优化 \(\rm DP.\)
\(\quad\)设 \(g_i\) 表示到 \(i\) 位置的最长递增子序列长度，可以 \(\Theta(n\log n)\) 计算。
\(\quad\)一个显然的暴力是这样的，设 \(f_i\) 表示以 \(i\) 结尾的最长上升子序列的数量，它可以从满足 \(j<i~\&~g_j=g_i-1\) 的点转移。
\(\quad\)时间复杂度 \(\Theta(n^2).\)
\(\quad\)考虑将 \(g\) 排序，对 \(g\) 相同的点一起转移。枚举当前 \(g\) 相同的这一段的所有点 \(j\)，维护一颗线段树，每次给线段树 \([j+1,n]\) 这一段加上 \(f_j\)，最后将所有点的值加到下一段 \(g\) 相同的点上去。
\(\quad\)时间复杂度 \(\Theta(n\log n).\)
\(\quad\)前缀和优化计数 \(\rm DP.\)
\(\quad\)首先预处理所有位置，若 \(p_i\) 需要大于 \(p_{i-1}\)，则 \(v_i=1\)，若 \(p_i\) 需要小于 \(p_{i-1}\)，则 \(v_i=-1\)，否则 \(v_i=0.\)
\(\quad\)设 \(dp_{i,j}\) 表示当前考虑到 \(i\)，第 \(i\) 位为 \(j\) 的方案数，我们发现如果当前已经构造了一个 \(1\sim k\) 的全排列，那么在第 \(k\) 为插入 \(x\)，可以使前面所有 \(\geqslant x\) 的数 \(+1\)，这样又形成了一个新的 \(1\sim k+1\) 的排列，且前面的数相对大小不变，所以有转移方程 ：
\(\quad\)显然可以前缀和优化，时间复杂度 \(\Theta(n^2).\)
\(\quad\)根号分治，\(0/1\) 背包。
\(\quad\)设 \(f_i\) 表示仅使用小于 \(\sqrt{n}\) 的数组成 \(i\) 的方案数，这个使用 \(0/1\) 背包转移即可。
\(\quad\)设 \(g_{i,j}\) 表示使用 \(j\) 个大于等于 \(\sqrt{n}\) 的数构成 \(i\) 的方案数，考虑到不能有相同的数，所以加入一个 \(\sqrt{n}\) 的同时也需要给前面所有数 \(+1\)，所以转移方程为 :
\(\quad\)最后把他们拼接起来，式子为 ：
\(\quad\)时间复杂度 \(\Theta(n\sqrt{n}).\)
\(\quad \rm PS:\)需要注意的是，统计答案时数和块数需要从 \(0\) 开始枚举，因为可能仅由大于 \(\sqrt{n}\) 的数或小于 \(\sqrt{n}\) 的数组成。
\(\quad\)根号分治，完全背包。
\(\quad\)与上面的思路相同，但由于每个数可以重复用，所以 \(f\) 的转移用完全背包，\(g\) 可以选择添加一个数或给所有数 \(+1\)，转移式为 ：
\(\quad\)时间复杂度 \(\Theta(n\sqrt{n}).\)
\(\quad\rm PS：\)需要注意的是，我们枚举的数是 \(\lfloor \sqrt{n}\rfloor\)，所以可能需要 \(>\sqrt{n}\) 个块。
\(\quad \rm STL\) 辅助 \(\rm DP.\)
\(\quad\)考虑设 \(f_{i,j}\) 表示当前考虑到第 \(i\) 个数，乘积为 \(j\) 的方案数。转移按照 \(0/1\) 背包，可以证明状态数不超过 \(k\) 的约数个数，所以直接用 \(\rm map\) 存就好了。
\(\quad\)时间复杂度 \(\Theta(nd(n)\log n).\)
\(\quad \rm dfs.\)
\(\quad\)考虑枚举其中一棵树的一条边，将分割开的两棵树的点分别暴力在另一棵树上标记为黑色或者白色。可以发现，如果在另一棵树上枚举边，那么分隔开的两棵树中的黑点、白点就是四种不同的交集。另外还可以发现，若确定第二棵树上某一颗子树的黑点个数，另一颗的黑点个数也可以确定，故直接 \(\rm dfs\)，递归的时候记录一下答案。
\(\quad\)时间复杂度 \(\Theta(n^2).\)
\(\quad\)实际上不是个 \(\rm DP~?\)
\(\quad\)我们发现一个事实，不论球的状态如何，只要有 \(k\) 个球经过一个状态为 \(1\) 的盒子，那就会有 \(\lfloor\frac{k}{2}\rfloor\) 个球往下走，其它的球往上走，反之，球的数量相反。
\(\quad\)我们又发现，一个盒子的球的来源只有可能是左边或上面，于是直接记录一下每个盒子会有多少个球就好了。
\(\quad\)时间复杂度 \(\Theta(n^2).\)
\(\large\rm *×\#17~Chandrima~and~XOR\)
\(\quad\)分析性质神仙题。
\(\quad\)设 \(f_i\) 表示 \(S\) 中在 \([2^{i-1},2^i-1]\) 中的数量，显然有转移方程 ：
\(\quad\)又有 ：
\(\quad\)两式相减，可得 ：
\(\quad\)又有 \(f_1=f_2=1\)，可以知道 \(f\) 是 \(\rm Fibonacci\) 数列。
\(\quad\)设 \(F_i=\sum_{j=1}^if_j\)，可以发现 \([1,2^i-1]\) 符合要求的数就是 \(F_i.\)
\(\quad\)若当前询问的是 \(x\)，则减去最大的小于 \(x\) 的 \(F_i\)，将答案亦或上 \(2^i\)，然后将 \(x-F_i-1\) 递归即可。
\(\quad\)时间复杂度 \(\Theta(n\log w\log\log w).\)
\(\quad\)四边形不等式优化区间 \(\rm DP.\)
\(\quad\)首先拆环成链，设 \(f_{l,r}\) 表示将 \([l,r]\) 合并需要的最小代价，显然有 ：
\(\quad\)其中 \(w_{l,r}=\sum_{i=l}^ra_i\)，这样转移时间复杂度 \(\Theta(n^3).\)
\(\quad\)我们发现 \(w\) 满足四边形恒等式和包含单调性，所以 \(f\) 满足四边形不等式，进而 \(f_{l,r}\) 的决策点 \(p_{l,r}\) 满足对于任意 \(p_{l,r-1}\leqslant p_{l,r}\leqslant p_{l+1,r}\)，这样可以优化到 \(\Theta(n^2).\)
\(\quad\)矩阵加速状压 \(\rm DP.\)
\(\quad\)设 \(f_{i,S}\) 表示当前已经考虑到了第 \(i\) 行，这一行有 \(S\) 中的格子已经被覆盖的方案数。
\(\quad\)考虑枚举这一行有哪些格子存在以这个格子为左端点的横木板来转移。设 \(S‘=2^m-1-S\)，即将 \(S\) 取反，枚举 \(S‘\) 的子集 \(T\) 作为增加木板的集合。可以发现，\(S\cup T\) 必须是一个可以用竖木板覆盖的集合，这个可以 \(\Theta(m)\) 判断。如果集合 \(S\cup T\) 合法，那么 \(S\) 可以向 \(T\) 转移。
\(\quad\)可以发现，阶段仅由 \(i\) 划分，于是可以将 \(S\) 向 \(T\) 的转移全部处理出来，用矩阵快速幂加速递推。
\(\quad\)时间复杂度 \(\Theta(2^{3m}\log n).\)
\(\large\rm *\#03~最长递增子序列~V2\)
\(\quad\)单调栈。
\(\quad\)设 \(f_i\) 表示从前往后以 \(i\) 结尾的最长上升子序列，\(g_i\) 表示从后往前以 \(i\) 结尾的最长下降子序列。
\(\quad\)容易发现，如果一个点 \(i\) 满足 \(f_i+g_i=MaxL+1\)，其中 \(MaxL\) 为最长上升子序列的长度，那么这个点可能在最长上升子序列中。若这个点的 \(f_i\) 独一无二，那么它一定在最长上升子序列中，否则就可能被另一个数替代。
\(\quad\)时间复杂度 \(\Theta(n\log n).\)
\(\quad\)数位 \(\rm DP.\)
\(\quad\)计数 \(\rm DP.\)
\(\quad\)首先考虑第 \(1\) 问。
\(\quad\)将交换次数替换成逆序对数，设 \(f_{i,j}\) 表示一个长度为 \(i\) 的排列有 \(j\) 对逆序对的方案数。我们发现添加一个数最多能使逆序对数增加原来数的个数，故有转移方程 ：
\(\quad\)前缀和优化一下即可。
\(\quad\)然后考虑第 \(2\) 问。
\(\quad\)我们考虑一个排列最少需要交换多少次才能得到，显然为其置换环上元素个数。
\(\quad\)设 \(f_{i,j}\) 表示长度为 \(i\) 的排列，需要交换 \(j\) 次的方案数。显然有 ：
\(\quad\)其含义为，新加进来的这个数可以直接单独成环，不增加交换次数，或加入之前一个环的任意一个位置，有 \(i-1\) 种选择。
\(\quad\)单调队列思想优化 \(\rm DP.\)
\(\quad\)考虑分情况讨论，如果这个交换在 \([l,r]\) 以内或以外，对答案没有影响，直接做一遍最大子段和即可。如果这个交换在 \([1,l-1]\) 和 \([l,r]\) 之间，那么容易发现我们肯定将 \([1,l-1]\) 中的最大值和 \([l,r]\) 之间的最小值交换。如果这个交换在 \([l,r]\) 和 \([r+1,n]\) 之间，那么将前面那个做法反着跑一边即可。
\(\quad\)考虑第二种情况怎么做。记 \(\max/\min(l,r)\) 表示 \([l,r]\) 内的最大\(/\)小值，\(sum_i\) 表示 \(\sum_{j=1}^ia_j\)，容易知道答案为 :
\(\quad\)考虑枚举 \(l\)，那么 \(-sum_{l-1}+\max(1,l-1)\) 是一个定值，我们只需要最大化 \(sum_r-\min(l,r).\)
\(\quad\)考虑从右往左枚举 \(l\)，我们发现 \(sum_r\) 的值是不变的，而 \(\min(l,r)\) 可能同时可以更新为一个更小的值，所以我们知道，一些新加进来的数可能 \(sum\) 较大，但由于 \(\min\) 不够小而不能成为最优的 \(r.\) 但在之后的更新中，它们有可能因为 \(\min\) 的变小而成为新的答案。
\(\quad\)我们考虑前面的一个 \(r‘\) 为什么没有将现在的答案 \(r\) 取而代之，因为它的 \(sum\) 虽然大，但 \(\min\) 较小。而所有 \(r‘\) 都不能比 \(r\) 更优，说明他们的 \(\min\) 都是不够小的，所以它们唯一的机会就是等待当前的 \(a_l\) 成为最小值。于是我们发现它们能够更新时最小值只可能是当前的 \(a_l\)，故只需要取 \(sum_{\max}-a_l\) 与 \(sum_r-\min(l,r)\) 对比即可，若前者更大，则取而代之。
\(\quad\)时间复杂度 \(\Theta(n).\)
\(\quad\)分治 \(\rm FFT\) 优化 \(\rm DP.\)
\(\quad\)发现一个美妙序列满足对于所有的点，前缀最大值大于后缀最小值。
\(\quad\)进而，我们发现存在某个前缀最大值小于后缀最小值当且仅当存在一个 \(i\)，这个序列的前 \(i\) 个元素是 \([1,i]\) 的排列，容易得到转移方程 ：
\(\quad\)我们发现这个式子是卷积形式，于是可以使用分治 \(\rm FFT\) 优化（可是我不会 \(\rm QAQ\)）。
\(\quad\)时间复杂度 \(\Theta(nlog n).\)
\(\quad\)分类讨论的树形 \(\rm DP.\)
\(\quad\)我们发现对于一颗子树，里面的逃犯肯定不能跑出来，所以我们在计算当前点答案的时候只关心这颗子树是否存在罪犯能跑到子树的根，以及是否存在一条从子树的根到叶子结点的路径。由于两者同时存在就一定不合法，所以只有三种情况，分别记为 ：
- \(0:\) 不存在逃犯可以到子树的根，不存在从根到叶子的路径。
- \(1:\) 不存在逃犯可以到子树的根，存在一条从根到叶子的路径。
- \(2:\) 存在逃犯可以到子树的根，不存在一条从根到叶子的路径。
\(\quad\)记三种状态的子树数量分别为 \(S0,S1\) 和 \(S2\)，转移分四种情况 ：
- 如果当前点有逃犯，那么到叶子的路径肯定都要封死，所以将该节点的状态设为 \(2\)，\(Ans\) 增加 \(S1.\)
- 如果当前点没有逃犯，并且 \(S1>0,S2>0\)，那么这个点必须设置一个警察，否则逃犯就有可能从一棵子树跑到另一颗子树逃走，所以 \(Ans\) 增加 \(1\)，将该点状态设为 \(0.\)
- 如果当前点没有逃犯，\(S1\) 和 \(S2\) 有一个大于 \(0\)，我们有一个贪心的想法，那就是在尽可能上面的地方放置警察，因为这样可以阻拦更多的子树，所以这种情况下我们不放置警察，而是将该点状态设为 \(S\) 大于 \(0\) 的那个状态。
- 如果当前点没有逃犯，\(S1\) 和 \(S2\) 都为 \(0\)，如果这个点是叶子结点，显然其状态为 \(1\)，如果不是，则其状态为 \(0.\)
\(\quad\)有一些细节 ：
- 我们发现一开始所有点到叶子的路径都是畅通的，而且没有罪犯，所以所有点的状态都是 \(1.\)
- 如果存在叶子结点有罪犯，那么一定不可能守住，答案为 \(-1.\)
\(\quad\)时间复杂度 \(\Theta(n).\)
\(\quad\)雷哥性质题，状压 \(\rm DP.\)
\(\quad\)首先特判 \(n=1\) 的情况，可以发现其为 \(2^{m-1}\)，用数学归纳法可证。具体来说，走完前面 \(m-1\) 个点的方案数为 \(2^{m-2}\)，可以先连完前面 \(m-1\) 个点再连最后一个点，也可以先连完最后 \(m-1\) 个点再连第一个点，两者方案数都是 \(2^{m-2}\)，故总方案数为 \(2^{m-1}.\)
\(\quad\)可以发现，任选 \(3\) 个点共线的概率不是很大，所以答案是接近 \((nm)!\) 的，可以发现这样分析点数最多 \(20\) 左右，于是考虑状压。
\(\quad\)设 \(f_{i,j,S}\) 表示当前在 \((i,j)\)，已经经过的点集为 \(S\)，每次只需要枚举一个不在 \(S\) 中的点，然后判断 \((i,j)\) 和它连线上的点是否都在 \(S\) 中即可。
\(\quad\)时间复杂度 \(\Theta(2^{nm}(nm)^2).\)
\(\quad\)直接跑过去可能需要卡常，但是我们可以打表。
\(\quad\)根号分治，背包 \(\rm DP.\)
\(\quad\)首先可以发现性质，所有大于等于 \(\sqrt{n}\) 的数都不可能取完，所以可以把他们的数量看作 \(\infty.\)
\(\quad\)然后按照划分数常见套路，可以将数分为大于等于 \(\sqrt{n}\) 和小于 \(\sqrt{n}\) 两部分。
- 对于大于等于 \(\sqrt{n}\) 的数，我们可以设 \(g_{i,j}\) 表示将 \(i\) 划分成 \(j\) 个数的方案数，有转移方程 :
- 对小于 \(\sqrt{n}\) 的数，我们可以用多重背包做，方程 ：
\(\quad\)可以发现物品价值是一段 \([j-num_iw_i,j]\) 内，满足 \(t\equiv j\pmod {w_i}.\) 可以发现，如果维护一些桶，每个桶中存余数相同的 \(t\) 的 \(f_{i-1,t}\) 之和，那么在 \(j\) 改变的时候，相当于一段区间在移动，只需要在左端点和右端点移动的时候将元素从桶中拿出或放入桶中即可。
\(\quad\)合并的时候直接枚举大于等于 \(\sqrt{n}\) 的数的出现次数即可。
\(\quad\)时间复杂度 \(\Theta(n\sqrt{n}).\)
\(\quad\)数位 \(\rm DP.\)
\(\quad\)分类讨论的计数 \(\rm DP.\)
\(\quad\)设 \(f_{i,j,k}\) 表示考虑前 \(i\) 行，第 \(i\) 行有 \(j\) 列为 \(1\)，\(k\) 列为 \(2\) 的方案数。
\(\quad\)我们发现当前行只能填最多两个数对于一个状态 \((i,j,k)\) 有以下转移方式 ：
- 若不填数
- 只有一种转移，即 \((i,j,k)\to (i+1,j,k)\)，方案数为 \(1.\)
- 若填一个数
- 可以填在没有填数的列上，即 \((i,j,k)\to (i+1,j+1,k)\)，方案数为 \(i+1-j-k.\)
- 可以填在只填了一个数的列上，即 \((i,j,k)\to (i+1,j-1,k+1)\)，方案数为 \(j.\)
- 若填两个数
- 可以填在没有填数的列上，即 \((i,j,k)\to (i+1,j,k+1)\)，方案数为 \(i+1-j-k.\)
- 可以分别填在没有填数的列上，即 \((i,j,k)\to (i+1,j+2,k)\)，方案数 \(\tbinom{i+1-j-k}{2}.\)
- 可以分别填在只填了一个数的列上，即 \((i,j,k)\to (i+1,j-2,k+2)\)，方案数为 \(\tbinom{j}{2}.\)
- 可以一个填在没有填数的列上，一个填在只填了一个数的列上，即 \((i,j,k)\to (i+1,j,k+1)\)，方案数 \((i+1-j-k)\times j.\)
\(\quad\)时间复杂度 \(\Theta(n^3).\)
\(\quad\)容斥，计数 \(\rm DP.\)
\(\quad\)考虑容斥，显然合法方案数等于总方案数减去经过黑点的方案数。
\(\quad\)我们发现如果将所有以某个点为第一次碰到黑点的地方的路径方案数加起来，那么可以不重不漏地统计所有不合法方案。
\(\quad\)设 \(f_i\) 表示到第 \(i\) 个点并且在第 \(i\) 个点第一次碰到黑点方案数。我们发现从 \((1,1)\) 到 \((x_i,y_i)\) 的方案可以直接算，但是如果在之前就碰到黑点了，那么这个方案是不合法的，于是要枚举所有能到 \(i\) 的不合法结点 \(j\)，将先到 \(j\) 再到 \(i\) 的方案减去，这个也是可以直接算的。故转移方程如下 ：
\(\quad\)最后的答案为 ：
\(\quad\)时间复杂度 \(\Theta(n^2).\)
\(\quad\)容斥。
\(\quad\)考虑设 \(L_i\) 表示以 \(i\) 结尾的最长全 \(1\) 串，\(R_i\) 表示以 \(i\) 开头的最长全 \(1\) 串。
\(\quad\)枚举左区间的右端点 \(b\) 和右区间的左端点 \(c.\) 我们发现最后答案一定是两段全 \(1\) 串拼起来。考虑容斥，用所有的方案减去不合法的方案（两边选择长度加起来不超过 \(k\)）即可。
\(\quad\)另外发现，左右两边可能单独即可组成一个合法字符串，这个需要预处理然后特判一下。
\(\quad\)时间复杂度 \(\Theta(n^2).\)
\(\quad\)结论题，计数 \(\rm DP.\)
\(\quad\)首先有如下结论 ：
\(\quad\)兰道定理 ：一张图为竞赛图当且仅当其出度序列 \(d\) 满足 \(\forall S,\sum\limits_{i\in S}d_i\geqslant \dfrac{|S|(|S|-1)}{2}.\)
\(\quad\)由此可推知，将 \(d\) 从小到大排序后，一定满足 \(\forall k,\sum_{i=1}^kd_i\geqslant \frac{k(k-1)}{2}\)，并且 \(\sum_{i=1}^n=\frac{n(n-1)}{2}.\)
\(\quad\)设 \(f_{i,j,k}\) 表示考虑到从小到大第 \(i\) 个数，前 \(i\) 个数的值小于 \(j\)，前 \(i\) 个数的和为 \(k\) 的方案数。
\(\quad\)转移的时候枚举 \(t\) 表示 \(j\) 有多少个，记 \(cnt_i\) 表示不小于 \(i\) 的已经确定的度数的数量，我们发现还未被确定的 \(n-i-cnt_j+cnt_{j+1}\) 个数可以被确定的 \(n-cnt_j\) 个数里选，那么有转移式 ：
\(\quad\)我们发现一个状态不合法就不能转移，而不合法的状态是 \(k+tj>\frac{n(n-1)}{2}\) 或 \(k+tj<\frac{(i+t)(i+t-1)}{2}.\) 需要注意的是，\(t\) 的枚举范围为 \([cnt_j-cnt_{j+1},n-cnt_{j+1}-i].\)
\(\quad\)时间复杂度 \(\Theta(Tn^5).\)
\(\quad\)神仙题。
\(\quad\)一个自然的思路就是把最终要求的数拆成形如 \(11111111111+1111111+11111+11+1\) 的若干段之和，共有长度为 \(0\) 到 \(n\) 共 \(n+1\) 种长度为全 \(1\) 段可选，我们需要从中可重地选出 \(9\) 个，使其和为 \(k\) 的倍数。
\(\quad\)观察发现我们其实不关心它的具体长度，只关心它对 \(k\) 取模的值。于是记 \(g_i\) 表示对 \(k\) 取模得到 \(i\) 的全 \(1\) 段种数，现在假设其已经求出，那么可以设 \(f_{i,j,k}\) 表示当前考虑到对 \(k\) 取模等于 \(i\) 的段，已经选了 \(j\) 个，此时构成的数对 \(k\) 取模的值为 \(s\) 的方案数。可以枚举 \(i+1\) 选多少个来转移 ：
\(\quad\)转移系数为从 \(g_{i+1}\) 个同类的全 \(1\) 段中选出 \(p\) 个的方案数，相当于将 \(p\) 个球放进 \(g_{i+1}\) 个盒子，方案数可以使用隔板法求得。注意到组合数中的 \(g\) 很大，但 \(p\) 很小，所以可以暴力预处理。
\(\quad\)时间复杂度 \(\Theta(k^2|\Sigma|^2).\)
\(\quad\)现在考虑如何计算 \(g.\) 设 \(h_i\) 表示长度为 \(i\) 的全 \(1\) 段构成的数在模 \(k\) 意义下的值，显然有 \(h_1=1,h_i\equiv h_{i-1}\times 10+1\pmod k.\) 我们发现 \(k\) 每次会走到一个新的小于 \(k\) 的非负整数，所以在 \(k\) 次以内必然出现循环节，将在循环内的段和不足一次循环的段分开考虑，这样很容易就可以处理出 \(g\) 的值。
\(\quad\)时间复杂度 \(\Theta(k).\)
\(\quad\)需要注意的是，由于题目所求数不允许有前导零，所以还需要枚举长度为 \(n\) 的全 \(1\) 段选多少个。所以最终答案为 :
\(\quad\)时间复杂度 \(\Theta(k^2|\Sigma|^2).\)
\(\quad\)数位 \(\rm DP.\)
\(\quad\)考虑枚举所求矩形的左上角和一条边的长度，我们可以预处理从每个点开始向下的最长长度，那么我们可以对所有长度取 \(\min\) 以确定以现在枚举的这条线段为上边，最长可以向下延申多少。我们发现这样做可以直接确定矩形的上边，又确定了最长的高，也就是说所有 \(L\times i,i\in [1,h]\) 的矩形全部多了一个，这个可以使用差分来维护。
\(\quad\)时间复杂度 \(\Theta(n^3).\)
\(\quad\)首先设 \(w_{n,m}\) 表示长宽分别为 \(n,m\) 的矩形没有限制的覆盖方案数。这个可以用状压 \(\rm DP\) 求出，设 \(dp_{i,S}\) 表示当前已考虑到第 \(i\) 列，这一列的覆盖状态为 \(S\)，然后枚举横着的木条转移，时间复杂度 \(\Theta(2^nn^2).\)
\(\quad\)考虑暴力容斥，枚举 \(S\) 和 \(T\) 表示行和列钦定一些位置，使这些位置不存在跨过线的骨牌，其它块随便填的方案数，设其为 \(g_{S,T}.\) 设 \(f_{S,T}\) 表示有且仅有 \(S\) 和 \(T\) 中的位置不合法的方案数，显然有 ：
\(\quad\)反演可得答案即为 :
\(\quad\)考虑枚举 \(S\) 后如何快速计算 \(T\) 的贡献之和。设 \(p_{i}\) 表示在 \(S\) 中位置不合法的情况下，宽为 \(i\) 的矩形的方案数，其值为 \(\prod h_{i,j}\)，其中 \(j\) 为 \(S\) 中相邻两位置的距离。同时，考虑枚举有几条横线不合法，设 \(q_{i,j}\) 表示当前已经枚举到第 \(i\) 行，之前已经有 \(j\) 条横线不合法的方案数，转移式为 ：
\(\quad\)而最后的答案即为 ：
\(\quad\)观察发现 \(q\) 的容斥系数只跟奇偶性有关，并且每转移一次就会取反，故不需要枚举当前的转移次数，设 \(q_i\) 表示当前考虑到第 \(i\) 行，有 ：
\(\quad\)最后的答案即为 ：
\(\quad\)时间复杂度 \(\Theta(n^22^n).\)
\(\quad\)矩阵加速插头 \(\rm DP.\)
\(\quad\)插头 \(\rm DP.\)
\(\quad\)状压 \(\rm DP.\)
\(\quad\)已初步完成，插头 \(\rm DP\)，数位 \(\rm DP\) 和大部分题目的代码咕咕咕中 \(......\)