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} ...

「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 ...

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) ...

poj3146题目大意： 给定一个 $n, p$ 求 $\binom{n}{0 \dots n}$ 有多少数不能被 $p$ 整除。 我们考虑 $Lucas$ 定理。 $\binom{n}{m} = \binom{n / p}{m/ p} \times \binom{n \mod p}{m \mod p}$。 也就是将 $n$ 分解成 $p$ 进制。如果上面的大于下面的就是有值的。 所以直接进行分解之后乘法原理即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <iostream>#include <cstdio>using namespace std;//#define Fread//#define Getmod#ifdef Freadchar buf[1 << 21], *iS, *iT ...

CF1553I Stairs 说实话网上的题解真的少，这个算是当前最详细的吧。请原谅我参考了别人的代码，还跑得巨慢的这一事。 不过还是 $O(n^2)$ 过去了，嘻嘻。 有两个思路，是将贡献不同时间计算的结果。 首先一个合法的序列，肯定是将数值连续的一段拿出来，然后可以分成若干段等长的。这个一开始判断一下即可。 之后我们将分段拿出来不妨将其记录为 $s$ 数组。 一个合法的序列就是不能有任意两个 $s$ 构成单调序列。 但是这个需要复杂度较高的 $dp$，我们考虑通过容斥改成钦定有几个数不合法。 对于一个长度 $> 1$ 的段，其有两种单调性。长度为 $1$ 的段，其只有一种单调性，但是向后转移的时候会产生两种单调性。 $\tt Case\ 1$ 我们将单调性在这个序列转移的时候就计算贡献。 设 $f(i, j, 0/1)$ 表示当前考虑到第 $i$ 个序列，已经钦定了 $j$ 个连续，当前段长度是否是 $1$。注意这个段是表示已经拼接之后的段。$$\begin{aligned}& f(i - 1, j, 0) \to f(i, j + 1, 1) \&am ...