CF1548C The Three Little Pigs 算基础的生成函数题了吧。 反正当时隔壁老哥在打 VP 的时候，推了半天 $C$ 没有推出来。被我一眼秒了 $\dots$ 就是答案肯定是 $\sum_{i = 0} ^ {n} \binom{3i}{x}$。 发现这个东西就是个二项式定理。 那么如果写成生成函数就是 $[z^x] (1 + x) ^ {3i}$ 设 $F(x) = \sum_{i = 0} ^{n} (1 + x) ^ {3i}$ 求通项可以得到。$$F(x) = \frac{(1 + x) ^{3n + 3} - (1 + x) ^ 3}{(1 + x)^3 - 1}$$上面那个二项式定理展开可以 $O(1)$ 计算每一项。 之后下面那个直接暴力除法就好了。 大神可以跳过这一段 下面那个柿子展开是 $x^3 + 3x^2 + 3x$。 我们考虑对于一个最高次是 $y$ 的多项式，我们除法第一遍做的商肯定是 $y - 3$。 那么得到 $x^y + 3x^{y - 1} + 3x^{y - 2}$。之后这个是要减掉的。 那么本质上就是后面的两项都要被减 ...

CF1528F 其实不难，但是又有懂得都懂的感觉。 某谷的翻译真的鬼畜。 题目大意： 一个合法的序列 $A$ 是 $\forall j \le n, \sum_{i = 1} ^ n [a_i \ge j] \le n - j + 1$。 给了一个限制 $B$ 序列，要求 $a_{b_1} = a_{b_2} = \dots = a_{b_k}$ 求这样 $(A, B)$ 的数量和。 首先考虑 $A, B$ 看起来很独立，我们考虑分开计算。 对于 $A$ 的限制我们不妨改变一下。 看成有 $n$ 个人，每个人都选择了一个位置 $a_i$。每个人依次坐其选定的位置，如果这个位置有人了那么就向右坐一个位置。如果 $n + 1$ 这个位置没有人，就是合法的。 我们考虑总方案是 $(n + 1) ^ n$ 然后对于一个合法位置其经过变换可以得到 $n$ 个不合法的位置。 那么合法的方案就是 $(n + 1) ^ {n - 1}$。 然后考虑 $B$ 的计数，因为只要满足 $a_{b_1} = a_{b_2} = \dots = a_{b_k}$ 的限制即可。我们可以任意钦定。 然后我 ...

CF 1466H 话说某谷的翻译直接讲了第一步 $\dots$ 题目大意： 总共有 $n$ 个人，每个人有一个长度为 $n$ 的排列，其中越靠前的数，其越喜欢。 对于一个序列 $A$，一开始分配的方案是 $i$ 号人分配到 $A_i$。 称一个序列 $A$ 是合法的，当且仅当不存在两个或者多个人交换 $A_i$ 使得有人得到更加喜欢的数。 给定一个数组 $A_i$ 求出有多少个排列，满足 $A$ 是合法的。 排列指的是每个人都喜欢序列。 发现如果一个序列不合法肯定存在一个置换使得有人可以更优。 置换本质就是环，我们考虑建图，对于一个 $j$ 在 $A_j$ 前面的点向其连接黑色的边。当然我们有 $j \to A_j$ 这个是白色边。如果存在一个环其中有黑色边就不合法。 我们只考虑确定的位置就是 $j \to A_j$ 的边。 如果点 $i$ 连接入了 $x$ 条黑边那么方案数就是 $g(x) = x! \times (n - x - 1) !$ 。 这个本质就是一个 $n$ 个点有标号的 $DAG$ 计数问题。 设 $dp(i)$ 就是答案。 我们枚举一下总共有多少个点是没有出 ...

P6031 CF1278F Cards 加强版题目大意： 有 $m$ 张牌，其中有一张是王牌。将这些牌均匀随机打乱 $n$ 次，设有 $x$ 次第一张为王牌，求 $x^k$ 的期望值。 答案对 $998244353$ 取模。 首先 $x^k$ 不好处理。考虑将其消除掉，会想到使用斯特林数转下降幂之后使用组合数消除掉。 我们考虑枚举几次是王牌。$$Ans = \sum_{i = 0} ^ n \frac{1}{m^i} (\frac{m - 1}{m})^{n - i} \binom{n}{i} i^k$$不妨设 $p = \frac{1}{m}$。 可以得到 $p^n \sum_{i = 0}^n (\frac{1 - p}{p})^{n - i} \binom{n}{i} i^k$。$$\begin{aligned}&p^n \sum_{i = 0}^n (\frac{1 - p}{p})^{n - i } \binom{n}{i} i^k\&p^n \sum_{i = 0}^ n(\frac{1 - p}{p})^{n - i} \binom{n}{i} \sum ...

「HEOI2015」最短不公共子串题目大意： 给两个小写字母串 $A, B$ 请你计算： $A$ 的一个最短的子串，它不是 $B$ 的子串。 $A$ 的一个最短的子串，它不是 $B$ 的子序列。 $A$ 的一个最短的子序列，它不是 $B$ 的子串。 $A$ 的一个最短的子序列，它不是 $B$ 的子序列。 简单题。看了一下网上的题解有用 $dp$ 的。但是既然是最小长度可以考虑使用广度优先搜索。 首先这个可以保证找到的第一个就是最优解。其次因为我们两个自动机都是按照深度向下排序的，那么本质上就是先遍历完深度浅的再遍历深度深的。 我们直接对于每个串建立两个自动机，之后暴力跑即可。 因为作者的写法习惯，所以后缀自动机的超级原点是 $1$ 号节点。为了判断的方便，我们考虑让后缀自动机的 $f(i, c)$ 表示从 $i + 1$ 开始的第一个为 $c$ 的位置。 这样超级原点也是 $1$，方便处理。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 ...

CF1392I Kevin and Grid 做这题的时候感觉网上的讲解很不清楚。但是写完了之后发现其实我也讲不出什么东西 $\dots$ 本质上这是一个联通块计数的问题。 我们考虑这个数据范围肯定不是给 $dp, dfs$ 的。 考虑是一个网格图，有一定的性质。考虑一下欧拉定理。 设联通块的个数是 $k$。 那么 $V - E + F = k + 1$。 我们就可以通过这些求出联通块的个数。 但是不同的联通块会产生不同的贡献。我们在加上的联通块数量的贡献之后还需要加上包含在内部的贡献。 不妨设 $\ge x​$ 的点构成的联通块是 $A​$，另一个是 $B​$。 我们考虑网格图那么面（除了最外面的）肯定是四联通。或者是中间包含了一个 $A$ 的联通块。 那么本质上 $F_B - \text{B 中的 4 联通块} - 1$ 就是 $A$ 中包含的联通块。 设 $A$ 中的 $4$ 联通块是 $D_A$，$B$ 中的是 $D_B$。 那么最终的答案就是。$$\begin{aligned}&V_A - E_A + F_A - V_B + E_B - F_B + In_A - ...

Hdu 2815 题解 Mod Tree详解见我的博客123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include <bits/stdc++.h>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT;#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : * ...

$\tt Bsgs$ 例题 如果您已经会 $bsgs$ 不妨来看看文末的注意。 求 $a^x \equiv b \pmod p$ 的一个最小正整数解。 $\tt p$ 是素数。 考虑进行分块，设 $m = \lfloor\sqrt p \rfloor$，那么让 $x$ 进行一下拆分得到。 $x = i\times m - j$。 之后对于两部分分别进行计算，放到哈希表中查询即可。 具体来说： 我们先将 $b \times a^j$ 存到 $\tt Hash$ 表中，然后去枚举每一个 $(a^{m})^i$ 去暴力匹配一下即可。 注意： 枚举 $i$ 要从 $0$ 开始到 $i$，为了计算是 $0$ 的情况。 特判 $m = 1, b = 1$ 直接返回 $0$ 即可。 123456789101112131415161718192021222324252627int ksm(int x,int mi,int p) { int res(1); if(mi == 0) return res % p; while(mi) { if(mi ...