P3758 [TJOI2017]可乐 首先考虑一个 $Dp$。会想到 $f(t, i, j)$ 表示在时刻 $t$ 走到位置 $(i, j)$ 的方案数。但是因为我们是从 $1$ 开始走。那么完全可以设 $f(t, i)$ 表示从 $1 \to i$ 在时刻 $t$ 的方案数。转移的话就枚举之后可以走到的位置进行转移。 然后处理一下爆炸的情况，可以建立一个新的节点，之后进行转移，然后每个点只能进入不能出来。 我们发现本质上我们的 $t$ 意味着死亡时间最晚是 $t$ 所以之前的状态需要继承。然后要对于新建的节点再来一个自环，进行转移。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>using namespace std;#def ...

P5283 [十二省联考2019]异或粽子 首先把题目转换一下，可以得到以下题面： 有一个长度为 $n$ 的序列 $a$，求两两异或的前 $K$ 大值。 本质和 CF241B Friends 一样。 $Tricks:$ 补全三角形矩阵，答案 $\div 2$。 考虑建立可持久化 $Trie$。之后考虑两种情况。 如果 $K$ 和 $n$ 是同阶的，我们可以得到一个 $K \log K$ 的算法。 我们维护一个大根堆，常规维护一下第 $K$ 小。之后考虑每一个位置的贡献。我们不妨考虑每一个位置作为右边位置的贡献。那么就是求左边异或第 $K$ 小。 对于每一个位置都这样做。可以保证有答案。 当取出一个元素的时候，更新答案，然后使用当前元素计算比其小 $1$ 个 $rank$ 的答案，放入堆。 可以得到复杂度是 $O((n + k) \log (nk))$。 $n$ 是插入的复杂度， $k$ 是堆的复杂度。 如果 $n$ 比较小，然后 $k$ 是 $n^2$ 级别的呢？ 我们考虑对于所有的数都插入到 $Trie$ 里面。 发现如果可以得到第 $K$ 大的值，那么计算比其小的值可 ...

恰好和至多的转换：$$\begin{aligned}&g(m) = \sum_{i = 0}^m \binom{m}{i} f(i) \\&f(m) = \sum_{i = 0} ^ m \binom{m}{i} (-1) ^ {m - i} g(i)\end{aligned}$$ $g$ 是至多有几个满足条件，$f$ 是恰好。 这个容斥可以理解成，至多的上限越高那么其方案数肯定是越多的，那么肯定是从多的开始容斥，所以容斥系数是 $(-1)^{m - i}$。 恰好和至少的转换：$$\begin{aligned}&g(m) = \sum_{i = m} ^ n \binom{i}{n} f(i) \\&f(m) = \sum_{i = m} ^ n (-1) ^ {i - m}\binom{i}{m} g(i)\end{aligned}$$ 然后这里我们的 $g$ 是钦定多少一个一定满足条件，$f$ 是恰好。 不要理解成后缀和的意思，因为这个是在集合中计数。 $\tt P ...

CF295D Greg and Caves 首先说一下这题很值得做。 $Update \times n\ on \ 2021.6.30$。 首先题目我们就直接分成两个三角形来写。 之后发现，其实上一行的具体位置不用知道，因为我们枚举当前的长度是必须 $\ge$ 上一次的长度的，然后其所有可能的位置也是很好算的。 我们就开始 $Dp$，设 $f(i,j)$ 表示从上到下计算到第 $i$ 行，当前行的长度 $\le j$ 的方案数。 很显然，我们考虑每一次找一个长度为 $j$ 的方案数。 $$f(i,j) = \sum_{c = 2} ^ m f(i - 1, c) \times (j - c + 1) + 1$$ 注意外面的 $ + 1$ 表示在这边重新开一行。 然后我们考虑计算答案，发现直接通过枚举中间的断点然后两个 $f$ 拼起来是错的。因为存在这样的情况。 那么我们不妨钦定一下中间这一段的长度，之后让两边严格小于即可，同时保证这个长度为 $1$，方案数就是 $f(i, c) - f(i -1, c)$。 然后我们直接暴力枚举计算即可。 $$\begin ...

统计本质不同的子串个数 小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。 现在小Hi想知道一部作品中出现了多少不同的旋律 $O(n)$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <cstring>#include <cstdio>#include <algorithm>#include <iostream>/** @ legendgod* 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了*/using namespace std;template <typename T>void r1(T &x) { x = 0; char c(getchar()); int f(1); for ...

$$\Large\color{blue} Jhb\color{red}\text{的多项式浅谈}$$ 这个的后半部分似乎可以当做金策大佬论文的人话解读。 推销一下窝的博客,本文所有的代码都在窝的博客上。 多项式主要的用途是用来优化式子，因为笔者也刚刚入门多项式，可能谈到的内容也十分浅，有错请直接开 D。 我们从大整数乘法入手，我们经常写的算法是通过枚举两个整数的每一位，通过位权来更新答案，这里显然是 $O(n^2)$ 。还有一种是分治乘法，还是通过位权，原理是 ：$$(Ax^m + B)(Cx^m + D) =ACx^{2m} + ((A + B)(C +D) - AC - BD))x^m + BD$$我们直接分治可以算出答案复杂度 $O(n^{2})$ 复杂度比较优秀？其实这种想法和之后的 MTT 优化是相同的。其中 n 表示位数。 复杂度怎么算？ $T(n) = 4T(\frac{n}{2}) + O(n)$ $T(n) = O(n^2)$ 之后我们考虑优化 $ACx^m + ((A - B)(D - C) + AC + BD) \time ...

P2882 [USACO07MAR]Face The Right Way说实话这一题写了半个上午，主要是位运算的问题 首先要明白的是 1^1 = 0 1^0 = 1 1^0 = 1 0^0 = 0 由此可以看出如果一个一位数（二进制） 异或0 就是它 本身 由此可以看出如果一个一位数（二进制） 异或1 就是它 相反数 本题的牛只有两个状态，而且每次旋转的长度是固定(枚举k)的所以枚举n和k是无法省略的第三层循环可以差分优化 具体做法 建立数组b[ ],表示当前（差分）位置的方向情况 转向两次等于没转用now代表当前的牛是否转向 我们只要判断（now ^ v[ i ]）是否等于0 若等于0，则进行操作 一次操作是长度为k的区间，起点为i 根据差分,影响到的点为 i,i+k 将b[ i ] 和 b[i + k]进行转向操作（^1）,m++即可 注意判断是否出界 1if(i + k - 1 > n) {失败} Code123456789101112131415161718192 ...

题目见P3834 首先，看到数据ai如此之大，却要用线段树做，那么就必须用离散化 以下为模板 12345678910n = r1;for(i = 1;i <= n; i++){ v[i] = r1; b[i] = v[i];}sort(b+1,b+n+1);int len = unique(b+1,b+n+1)-(b+1);for(i = 1;i <= n;i++) { int x = lower_bound(b+1,b+len+1,v[i]) - b;} 再放一张关于主席树的图 也就是相当于将不需要改动的节点不用重新建树，只要用原来的树就行 如果要查询区间内有没有在某个位置放数，只需 1tree[r].sum - tree[l-1].sum 以下是本题目的代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 ...