对于约瑟夫问题，假设一开始有 nnn 个人，每个 kkk 个人图图掉一个，我们两种常见的暴力做法是数组模拟和链表模拟，时间复杂度前者是 O(nlog⁡kn)O(n\log_k n)O(nlogk​n)，后者可以达到 O(nk)O(nk)O(nk)。 具体数学对 k=2k=2k=2 的情况给出了一种构造，就是位移，将二进制数的第一位移到最后，形成的新二进制数就是最后剩下人的编号，时间复杂度 O...

如何处理带限制的 Pólya 定理？（每种颜色 cic_ici​ 的数目固定为 SciS_{c_i}Sci​​） 如果每个环的大小一致为 sss，我们可以采取这样的方法： 若存在 Sc≢0(mods)S_c \not\equiv 0 \pmod sSc​​≡0(mods)，那么说明无法分配，方案数为 000。 若不存在上述问题，就是多重集的排列数问题，方案数为： (∑Sci/sS...

矩阵 系数矩阵和增广矩阵 将方程中未知数的系数形成的阵列称为方程组的系数矩阵，在系数矩阵的右端添加一列方程组的右端项，形成的矩阵称为方程组的增广矩阵。 矩阵的初等行运算 交换两行。 以非零实数乘以某行。 将某行替换为它与其他行的倍数之和。 严格三角形方程组 若方程组中，对于 k=1,2,⋯ ,nk =1,2, \cdots,nk=1,2,⋯,n，第 kkk 个方程的前 k−1k-1k−...

No 9 运用 反向归纳法 证明： P(n):x1⋯xn≤(x1+⋯xnn)n\begin{aligned}P(n):x_1 \cdots x_n \le (\frac{x_1+\cdots x_n}{n})^n\end{aligned} P(n):x1​⋯xn​≤(nx1​+⋯xn​​)n​ 首先证明简单情形： 当 n=2n=2n=2 时，(x1+x2)2−4x1x2=(x1−x2)2≥...

P3041 [USACO12JAN]视频游戏的连击Video Game Combos 可以想到，用 dp(i,j)dp(i,j)dp(i,j) 代表输入字符串长度为 iii ，匹配到节点 jjj 时可以达到的最大分数。 我们有 dp(i,ch(j,k))=min⁡{dp(i−1,j)}dp(i,ch(j,k))=\min\lbrace dp(i-1,j)\rbracedp(i,ch(j,k)...

首先，观察到 n≤12n \le 12n≤12 ，可以想到状压，我们用 f(u,sta)f(u,sta)f(u,sta) 表示可不可能走到 AC 自动机上节点 iii ，并且状态为 stastasta 的字符串已经是现在串的字串。并且，通过 BFS ，我们可以保证串的长度最短。 关键在于如何找出方案，我们记录 pre(u,sta)pre(u,sta)pre(u,sta) 二元组，代表 f(u...

传送门 我们有一个搞笑的做法： dp[i][sta]dp[i][sta]dp[i][sta]，其中stastasta表示后MMM为stastasta的方案数，然后转移也非常简单，每次转移完更新stastasta为[\frac{sta}{10}] \t\dfrac10+a[i]即可。 显然这样会炸。 考虑如何压缩后一维的状态。 还是考虑InsertInsertInsert函数，对于一个给定的j...

传送门 考虑一下最长公共子序列的求法： dp[i][j]=max⁡{dp[i−1][j−1](a[i]==b[j])dp[i][j−1]dp[i−1][j] dp[i][j]=\max\left\{ \begin{aligned} &dp[i-1][j-1](a[i]==b[j])\\&dp[i][j-1]\\&dp[i-1][j] \end{aligned} \ri...

传送门 考虑预处理出szszsz数组，表示子树的大小，处理出来val[u]val[u]val[u]数组，表示uuu的子树里面的所有奶牛到uuu集合的不方便度。 于是dpdpdp就十分简单，初始化dp[1]=val[1]dp[1]=val[1]dp[1]=val[1]，然后考虑集合地点从uuu变到vvv，vvv子树里面的所有奶牛都会少走www路程，而剩下奶牛都会都走www路程。 1234567...

传送门 这个题目背景真的是太孙了，必须吐槽！ ProProPro 给一棵树，每个点有一个权值，要求修改一些权值，使： 一个点的权值必须是其所有儿子的权值之和 一个点的儿子权值必须相同 求最少的被修改的数目 SolSolSol 其实此题充满套路的气息，首先，如果一个节点的权值确定，整个树都会确定。 假设节点uuu的权值是val[u]val[u]val[u]，孩子数量是son[u]son...