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

CF375D Tree and Queries线段树合并。 需要记录两颗线段树，其中一棵表示当前节点的颜色数量，另外一个表示出现次数为 $i$ 的颜色个数。 前面一棵直接进行线段树合并即可。后面的那棵能线段树合并的条件当且仅当有一种颜色只在一个子树中出现，我们可以直接对于这种情况进行合并。不然我们需要修改颜色，也就是暴力修改。 暴力修改的次数最多是 $O(n)$ 次。复杂度正确。 $Tricks：$ 我们先将可以进行合并的节点进行合并，之后再暴力修改。具体来说就是先统计哪个颜色是不符合标准的，之后将包含这个颜色的节点的所有贡献减去。之后直接线段树合并即可。 我们可以在线段树合并到叶子节点的时候记录同一个颜色在几个子树中出现过。 注意： 在线段树合并结束的时候不要忘记将权值合并。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828 ...