题解
字典树质因数分解枚举
[AGC003D] Anticube
题面
给定 $n$ 个数 $s_i$ ，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。 $n\le 10^5$ ， $s_i\le 10^{10}$ 。
题解
爆草评测机做法。对于每个数，把指数化简，模三等于 1 或 2 才是有价值的，就是一个至多长 15 的链（16 个质数乘在一起一定大过 $10^{10}$ ）。把这些链放在 Trie …
Jayun 发布于 2023-11-07 19:09:30
00
贪心线性动态规划（线性 DP）
题意
有 500,100,50,10,5,1 这些面额的纸币，有 $X$ 块钱，使用最少的纸币数表示的。
然后有一些物品，每种只有一个，有费用。每次你可以选择一些没买过的买，付一定的钱，用最小的纸币数会找你钱。
要求最大化最后 1 元纸币的数量。
$n\leq10^5,X\leq10^{14}$ 。
口胡
有性质是一次只会买一个。
然后有 $\mathcal{O}(n^2)$ 的背包做法 …
Jayun 发布于 2023-11-07 07:30:52
00
双指针计数枚举
Present
题面
给出一个长度为 $n$ 的数列 $a$ 。其中第 $i$ 项为 $a_i$ 。
请你求出 $\bigoplus_{i=1}^{n}\bigoplus_{j=i+1}^{n}(a_i+a_j)$ 。其中 $\oplus$ 表示按位异或操作。
$2 \leq n \leq 4 \times 10^5$ ， $1 \leq a_i \leq 10^7$ 。
题解 …
Jayun 发布于 2023-11-06 22:06:25
00
状态压缩动态规划（状压 DP）底层优化（卡常数）扫描线枚举
[POI2018] Różnorodność
题目描述
给定一个 $n$ 行 $m$ 列的矩阵，请对于每个长宽均为 $k$ 的连续子正方形，统计里面出现过的数值的种类数。
$n,m\le3000$ ， $k\le \min(n,m)$ 。
题解
用一个 $n\times k$ 大窗口从左往右滑动，这样相当于把二维化成一维。这样一列增一列减地转移。
再考虑大窗口内的 $k\tim …
Jayun 发布于 2023-11-06 21:34:22
00
构造
题面
小氟发现，这张图正好有 $n+1$ 条从 1 到 114 的路径，并且在这些路径的边权和中， $[0,n]$ 的每一个整数正好出现了一次。
小氟想问你，这张图可能是什么样的？请你给出一种方案。
所有的点编号和边权皆为非负整数，点的编号要在 $[1,n]$ 范围内。
$n\leq32500$ ，方案中点数 $<18$ ，边数 $<48$ ，边权 $\le n$ 。 …
Jayun 发布于 2023-11-06 16:38:17
00
状态压缩动态规划（状压 DP）
RBS
题面
定义括号序列为只包括 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 $1$ 和 $+$ ，将其转化为合法的代数式，例如：
$\texttt{()()}$ 和 $\texttt{(())}$ 是匹配的
$\texttt{)(}$ 和 $\texttt{(}$ 和 $\text …
Jayun 发布于 2023-11-06 16:32:22
00
贪心二叉堆
DZY Loves Modification
题面
给出一个 $n\times m$ 的矩阵，并进行 $k$ 次操作，每次操作将矩阵的一行或一列的所有元素的值减 $p$ ，得到的分数为这次修改之前这一列 / 一行的元素和，求分数最大值。
$n,m\le 10^3$ , $a_{i,j}\le10^3$ , $k\le 10^6$ , $p\le 100$
题解
以减去一 …
Jayun 发布于 2023-11-06 16:25:44
00
枚举容斥原理
题意
定义 $f(i)$ 为非 $i$ 因子的最小正整数，现给出正整数 $n$ ，求 $\sum_{i=1}^nf(i)$ 对 $10^9+7$ 取模后的值。
$n\leq10^{16}$ 。
题解
傻逼题。枚举每个 $f(i)$ 的贡献即可。要容斥掉已经统计的部分。复杂度大概 $\mathcal{O}(1)$ 。
代码
const int N = 1, mod = 1e …
Jayun 发布于 2023-11-06 16:17:57
00
容斥原理
题意
小 Ω 在小学数学课上学到了“幂次”的概念： $\forall a, b \in \N^+$ ，定义 $a^b$ 为 $b$ 个 $a$ 相乘。
她很好奇有多少正整数可以被表示为上述 $a^b$ 的形式？由于所有正整数 $m \in N^+$ 总是可以被表示为 $m^1$ 的形式，因此她要求上述的表示中，必须有 $b \geq k$ ，其中 $k$ 是她事先选取 …
Jayun 发布于 2023-11-05 20:19:08
00
斯特林数组合意义树形动态规划（树形 DP）排列组合
题意
给出一棵树和一个常数 $m$ ，对于每一个 $i~(1\leq i\leq n)$ ，求 $\sum_{j=1}^n\text{dist}(i,j)^m$ 。
题解
关于斯特林数有性质 $x^n=\sum_{i=1}^n\frac{x!}{(x-i)!}\begin{Bmatrix}n\\i\end{Bmatrix}$ ，组合意义相当于枚举非空盒。
则原题有，
$$\sum_{k=1 …
Jayun 发布于 2023-11-04 22:46:52
00