考虑使用点分树维护，每次维护经过点分中心的权值。我们考虑计算每个点到点分中心的最小值和最大值，然后合并两个到点分中心的路径。将这样的最大最小值对按最小值排序后，计算贡献。考虑到后计算到的点最小值一定更大，则只有两种情况。1.最大值比之前的大，则贡献是之前的最小值乘现在的最大值。2.最大值比之前的小，则贡献是之前的最小值乘之前的最大值。因此我们只要按照最大值为下标插入权值即可。因为维护的是过点分中心的路径，要删除掉同一子树内点的贡献。复杂度。 #include <cstdio> #include <algorithm> #include <cstring> #...

其中是完全积性函数,可线性筛。其余部分可以处理。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 5e6 + 100; const int MOD = 998244353; void upd(int &a, int b) { a += b; if (a >= MOD) a -= MOD; } int pri[N], phi[N], mu[N]...

首先，k=1我们发现没有合法的。其次，对于k>=2的情况，我们可以分成若干链进行求解，链长很短。如果没有q的限制，则很显然记录最后一个选不选就行了。由q的限制，则记录最后q个数选的情况。看起来复杂度是2^q的，但是按照不能相邻来剪枝，状态不超过200个。进行dp即可。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 1010; const int MOD = 10086...

先用kmp求出t能出现在s的哪些位置。我们维护这样的三个dp方程：dp1[i]表示 最后一个区间结尾r在i的方案数。dp2[i]表示 最后一个区间结尾r在[0...i]的方案数。dp3[i]表示 最后一个区间开头l在[0...i]的方案数。转移即可，dp2[n]即为答案。复杂度O(n)。 #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int ...

我们发现题目中有若干旋转置换。而对于一共有n条蛇的环而言，本题对应的置换群由一个单位置换和n-1个旋转置换构成。根据burnside引理我们可以对于每个置换求出不变的颜色数进而求出答案。对于单次确定三种蛇使用个数的情况，即代码中的cal(a, b, c)复杂度是O((a+b+c)log(a+b+c))当然，我们能发现gcd只有log个，能够通过反演进一步优化到亚线性。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long lon...

考虑使用min25。令f(p^c)是当p为质数时的答案，根据积性函数的性质，可以进行min25筛。但是选择的质数小于等于m时，f(p^c) != c + 1。处理这些奇异值即可进行min25筛。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 1e6 + 100; const int MOD = 998244353; int Sqr, K, m, tot, id1[N], ...

我们发现，对于一个固定的右端点r而言，合法的左端点l一定是一个连续的区间，从某个数第一次出现k次开始合法，到某个数第一次出现k+1次开始不合法。因为我们对询问按右端点离线，对于每扫描一个右端点时将合法的左区间加入到线段树中，然后统计即可O(nlog(n))。 #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; #define lson rt * 2 #define rson rt * 2 + 1 type...

第一问：根据线性递推序列的特征方程理论，我们可以根据递推方程构造特征多项式，使用特征多项式的根来构造通项方程。而an^2也可以直接对通项平方，我们发现an^2也是由某个特征多项式的根构成。构造这个特征多项式，进而可以构造出线性递推方程。因此我们可以断言，an^2也是线性递推的。对于线性递推方程，我们可以使用BM线性递推黑盒算法求解递推方程的某项。复杂度O(n^2logk),其中n是最少需要传入的项数，k是求k项，复杂度优于矩阵快速幂递推。第二问：结论题，答案是fib(n)*fib(n + 1)。矩阵快速幂求解即可。 #include <bits/stdc++.h> using n...

题目可以简化为ans[i]表示距离为i的点对个数的概率和，求出这个概率和即可。考虑使用点分支分解整棵树，然后在子树中选取深度小的进行启发式合并，这里合并用ntt进行加速。复杂度O(nlognlogn)。 #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int N = 262144 + 100; const int MOD = 998244353...

我们发现可以通过第一个不合法的位置不重不漏的统计所有非法方案。设dp[i]表示处理到sa[i],且sa[1]，sa[2]...sa[i - 1]这些点都是合法的方案数。那么答案就是n! - dp[1] * (n - sa[1])! - dp[2] * (n - sa[2])! - ... - dp[m] * (n - sa[m])!。考虑怎么求这个dp[i]。我们发现处理到sa[i]时，有sa[i]！种不同的不合法方案，但是有些方案会在前面的点不合法，减掉即可。只要dp方程设计的足够优秀，代码就能足够简单。 #include <cstdio> #include <algori...

题目可以转化成1） 找某个坐标左边第一个比他大的数。2） 找某个坐标右边最小的数。 这两个操作分别可以用两颗线段树维护。 1）中维护区间max，如果右区间最大值比要查询的值大，则递归右区间，否则递归左区间。2）中维护区间min，如果据区间最小值比右区间最小值小，递归左区间，否则递归右区间。 复杂度O(nlogn) #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define lson rt * 2 #define rson rt * 2 + 1 ...

没看到题目中条件保证是一颗森林，自行加强题目。这里采用时间线段树+回退并查集来解决。并查集可以O(1)的插入，很难O(1)的支持删除操作，但是可以回退。我们使用时间线段树，将所有操作锁定为插入操作，使用回退并查集维护即可。复杂度O(nlogn)。 #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; #define lson rt * 2 #define rson rt * 2 + 1 #define MP...

每个本质不同子序列的贡献是1。本题的期望可以转化为概率。由于序列自动机就是子序列的最小表示。我们依据序列自动机进行概率转移。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 1e5 + 100; const int M = 26 + 2; const int MOD = 998244353; int n; int nex[N][M]; ll pp[N], qq[N], dp...

迪利克雷卷积的性质告诉我们，积性函数卷积性函数的得到的结果也是积性函数。题目公式中有两个积性函数，因此可以推断出f也是一个积性函数。因此我们只要处理出所有f(p^k) (p是质数)的值即可线性筛，复杂度O(n)。 代码： #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 1e7 + 100; const int MOD = 998244353; ll qpow(ll x, l...