任意模数多项式乘法 NTT 因为任意模数多项式乘法的系数可能超过了 所以一般的 就做不了。所以对于 的做法是找到 个模数，最后使用 合并一下，但是这里的合并中的答案可能超过 的值域，所以要用快速乘实现。 FFT 任意模数多项式乘法用 实现的问题主要是因为精度问题，这里使用了 次变化的 实现，采用了 作为底，那么一个多项式，我们根据 。那么 。就拆分成了系数比较小的四个多项式。最后合并一下就好了。 代码 这里只给出了 的代码实现。 #include<bits/stdc++.h> using namespace std; const int N = 4e5 +...

2020牛客NOIP赛前集训营-普及组（第六场） A 七七七七 分析 由于每次的答案的增长是以指数增长的，所以直接枚举日期的复杂度为 。那就直接暴力枚举就可以了。总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() {int x;scanf("%d",&x);return x;} int main() { int n = read(); int sum = 0; for(int i = 1,c = 1;;i = i * 7,c++) { sum +...

2020牛客NOIP赛前集训营-普及组（第五场） A T1 购物 分析 由于是买 送一，所以我们考虑买 只需要 次花钱的购买。那么可以把 个物品分成很多段，每段的长度为 ，然后处理一下边角就好了。 代码 #include<bits/stdc++.h> using namespace std; int read() {int x;scanf("%d",&x);return x;} int solve(int a,int b,int c) { return (a / (b + 1) * b + (a % (b + 1))) * c; } int main() ...

分析 可以观察到，如果一个数的最小位数没法精准划分，那么再多的大位也不可能表达出这个数字。所以我们考虑从低位到高位依次贪心。 对一位的答案可以贪心考虑。如果 ，那么在同一位上的我们显然是考虑 是要比 更优的，那么当我们可以得到一个值 而且可以得到 那么我们是可以确定这一位的。 那么由小到大依次考虑就可以了，而且多余的答案不能去掉，因为要考虑进位。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 10; #define pii pair&lt...

K阶前缀和 这是我们对前缀和的定义。而 阶前缀和就是把这个过程进行 次。那么考虑卷积。 其实可以看作 而 。 是一个所有项都为 的函数。那么 。由于卷积是有结合率的，所有 阶前缀和等同于 。而对于 的计算，可以采用多项式快速幂，但没必要。我们有生成函数 ，那么 的生成函数为 而 。这个可以通过数学归纳法证明。最后就做一次卷积就可以了。 K阶差分 那么 也可以卷积 其中 。那么 的生成函数为 。 那么进行 次操作之后 的生成函数为 那么 。卷积一下就做完了。 分析 不管是差分还是前缀和其实我们都可以 就可以了，更加无脑一点，时间复杂度也是 ...

写在前面的 一起对于简单点分治的题都是用 解决的，结果遇到点分树，哦吼，做不来了。这才打算学一下点分治，我检讨。 点分治 引入 给你 个询问，询问一个树上是否有长度为 的路径。要求在 时间复杂度内解决。 如果学习过 的同学，这个就是个模板。但是这里还是考虑使用点分治解决。其实这两个算法我觉得思想也是非常一致的。 无序列表内容 我们对于一个节点可以把路径分成两种 经过该节点的 没有经过该节点 那么我们考虑分治。选择一个节点作为根，那么路径要么以这个节点为 ，要么根本不经过它。而这个只处理以这个为 的路径。那么剩下的路径与这个节点就没有关系，就可以去除这个节点了。例如这张...

2020牛客NOIP赛前集训营-提高组（第五场） A 三元组计数 分析 我们对于三元组的考虑，有一个套路，枚举二元组然后再考虑贡献。那么我们先找到有多少个二元组 满足 。那么这个根据调和级数可以得到 。那么我们就可以直接枚举每个元素的倍数就好了。最后再考虑每个二元组的贡献就好了。总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 100; int read() { int x = 0,f = 0;char ch = getc...

写在前面的 这是我不想做第二次的题目。 分析 我们什么都不说了，直接定义状态 表示 节点是否作为蓝线的中点的最优解。那么我们通过分析，一条蓝边一定是 的路径。所以先考虑 的暴力树形 。 和 ，然后 就写好了。 #include<bits/stdc++.h> int read() {int x;scanf("%d",&x);return x;} using namespace std; const int N = 12010,inf = 0x3f3f3f3f; #define pii pair<int,int> vector&...

说在前面的 我希望以后的每日一题也是以小专题出现的，我觉得这样的练习效果才好。而且题有点少，并且有很多重复。例如 解决异或和，权值 ，合并 没有出现，有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。 异或 异或是一种位运算。满足 。这个比较好理解，大概就是两个数异或，那么在一位上相同的的数变为 ，反之变为 。 性质 那么异或又满足什么性质呢，个人认为下面的式子非常简单，如果有问题可以私聊。 交换率 结合率 01 Trie 算是 的一种变形。关于 的讲解，为了方便大家，我直接把以前的博客搬过来 这里 ，自我感觉还是不错的。 例题 牛客的例题只有由高到低建...

写在前面的，一道非常好的题，思路很顺滑（是这样用的吧），考察的数据结构也很巧妙。 分析 首先从小到大把边加进来，那么，一个连通块是满足条件的当且仅当在加完某条边之后这个连通块是一个团。所以我们就有了个，指数级别的 。那么如何去掉连通块的问题。其实我们如果按照边的长度排序。构建一棵重构树。那么我们发现，一个连通块一定是一个节点的子树。那么我们可以定义状态 为以 为根节点，分成 组的总方案。那么转移为 。根据树形背包的时间复杂度分析可以知道，总转移是 的，(好像可以用 优化转移，不是时间瓶颈不分析) 。那么最后答案为 。总的复杂度为 。 在重构时，记录边的数量，看看是否已经构...

推式子 那么就转化为一个卷积形式 。那么 。用 优化一下，就变为 了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 8e5 + 100,mod = 167772161; int read() {int x;scanf("%d",&x);return x;} int ksm(int a,int b) { int x = 1;for(;b;b>>=1,a=a*1ll*a%mod){ if(b&1) x=x*1ll*a%mod;...

分析 我们如何处理 。我们其实需要一点小技巧。我们发现， 如果出现在 中。那么一定有一个位置 满足 是 的后缀。 是 的一个前缀。那么我们就可以枚举每一个位置，看能够作为前缀的串的个数和作为后缀串的个数。最后答案为 。而求后缀，我们可以用 ，而求前缀有个小技巧，反转 后再插入 就是求前缀了。那么总的复杂度为 。一开始脑袋智商不在线，写了一个 的树状数组维护标记。也过了。代码都放下。 代码 #include<bits/stdc++.h> using namespace std; const int N = 6e5 + 100; struct AcAm{ ...

分析 非常好的一道题，用到的 也是在 中非常有意思的，考察了多方面的知识。我把考察的知识写在了下面。 一个串出现的次数等同于 。就是在 指针构成的反树链上的权值。 基本的差分和数据结构。 由于我们有了性质一，那么我们对于一个串的插入其实就是子树 ，删除反之。而对于子树操作可以用树链剖分也可以用树状数组维护差分维护一下 区间。那么总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 100; bool vis[N]; int pos[N]; struct Bit...

分析 我们把数字考虑为字符串，那么现在我们就是要求出有多少方案满足 没有出现在 串中。 关于这道题，因为我们要对子串考虑，比较自然考虑到 树和 。由于 并不能很好处理失配的问题，那么考虑 自动机。我们定义 其中 表示，该节点为一个 的结尾，那么当我们转移到这个点的时候是非法的。但是在 自动机上不知每个串的插入的地方是非法的，如果串 是 的子串，而且 ，那么 。而 指针指向的就是一个串的最长后缀，所以我们才考虑到 。 那么现在我们处理了子串的合法性，定义 为已经考虑长度为 ，当前节点为 的合法答案，那么 ，现在考虑我们构成的串 在数值上要小于等于 ...