牛客挑战赛32 C 不会推导，贴一个oeis链接https://oeis.org/A001629通过链接我们知道: 这样我们就可以通过矩阵快速幂求解 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll mod = 998244353; template <typename T> void out(T x) { cout << x << endl; } ll fast_pow(...

引子 现有一公式，求 a n s = ∑ i = 1 ...

题意 我们已知n个点，m条边，k个标记。可能存在重边，无自环（就是不存在 a->a，但存在环） 除了k个被标记的点，其他点都有一个糖果，并且这些点是可以任意的选择道路。被标记的点只能随机的被安排道路（只能被安排一次，下次遇到就结束）。先要求从1号屋开始，最多能拿多少糖果 分析 首先我们看到了随机，可想而知是个期望题。由于我们只有一次跳转的机会，这样会发现只有与1号屋相连的（直接或间接）怪兽屋才是有用的。大致就可以理解为，用怪兽屋去分割，对每个联通块进行缩点。然后找与1号屋相连的怪兽屋的最大贡献，当然最后在加上一号屋所在联通块的大小。 ...

一维差分 对于区间[l, r]，我们有 num[l] ++;num[r + 1] --;//差分 for(int i = 1; i <= n; i ++) num[i] += num[i - 1];//做前缀和 题意 有n个灯，m次操作，每次操作有两个参数l,r，其意义是对区间[l, r]内的灯进行一次状态转换（原来是关的，转换后就是开的，初始都是关的），现在问经过m次操作，有多少灯是开的 分析 我们观察到T有1000, 正常差分 O(T * n)，很显然超时 于是我们发现m只有1000, 然后我们对这个操作进行离散化，也就是拆区间(我使用了pair存这个拆过的点) p...

题意 给一个字符串，让我们找每个长度的子串中，是super串的个数。（类似双倍回文） 分析 我们对原串建立一个PAM，这样我们可以统计每种回文串出现次数，在用hash判断是不是super串 最后在统计一下就ok #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 3e5 + 5; const ull base = 131; const ull mod = 1e9 + 7; struct PAM_nod...

个人理解 回文自动机顾名思义，是解决回文串相关问题的。其又称回文树。树上的每个节点对应串中的一个回文串。树根有两个，分别为0和1。0是所有偶回文的树根，1是所有奇回文的树根。在树上父子之间长度差2。类似ac自动机，回文自动机也有相应的fail指针。其指向当前编号的最长回文后缀。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 5e5 + 5; struct PAM_node//回文树上节点 { ...

回文串 形如aaa,aa，aba之类的就是回文串，字符串关于某个位置中心对称。反之，abcd不为回文串 对于字符串str,现有个O(n)范围求出以每个位置为中心的最长回文半径——manacher manacher 正常的求每个位置的最长回文半径，我们用暴力，复杂度是O( n 2 n^{2} n2),但是我们发现，在前面求出的半径可以拿来使用...

留个板子 2019 南昌网络赛B 题意 v个点，e条边（可能重边，无影响），救火英雄在s点，剩下的k个救援队在k个位置，现在要求救火英雄对所有点的最短路的最大值乘1/c与k个救援队对所有点的最短路，取最小值输出（救火英雄要输出没乘1/c之前的） 分析 我们直接跑两边dijstra就行了，第一遍正常跑，以s为源点，第二遍，建立一个超级源点连接k个救援队的位置，权值为0，在跑一边dijstra,最后在比较 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned l...