题目链接 https://www.luogu.org/problemnew/show/P2312 分析 这道题很毒啊,这么大的数。 但是如果多项式$\sum_{i=0}^N a[i]X^i=0$则$\sum_{i=0}^N a[i]X^i \mod P=0$ 于是我们可以暴力膜一模，然后在$[1,m]$中枚举就好了。但是呢，万一这个多项式的值是$P$的倍数,也会变成0，所以保险起见搞几个又大又质的

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=5017 分析 老师讲课谈到了这道题，课上想出了个连边建图然后乱搞的操作，被老师钦定的递推方法枪毙了；晚上回去做了做，好像复杂度是不对。还是学习了下此题递推方法，感觉考场上写这个的是抱着得部分分的心理A了这道题(话说洛谷没有SNOI2017的题目 我们用$l[i],r[i]$表示$i$最左和

题目链接 https://www.luogu.org/problemnew/show/P3950 分析 大佬都用LCT，我太弱只会树链剖分 一个很裸的维护边权树链剖分题.按照套路,对于一条边$(dep(u)<dep(v))$,让它边权加1就在$v$点处+1，将边的问题转化为点的问题 然后对于C，U操作，线段树单点修改，Q操作区间查询 注意 询问$u,v(dep(u)>dep(v))$点

题目链接 https://www.luogu.org/problemnew/show/UVA11987 分析 分析下操作发现就是加了个删除操作的并查集,怎么做删除操作呢. 我们用一个$id[]$记录每个数字在并查集中的编号,$tot=n$,一开始$id[i]=i$,当将$p$从原集合中删除时,让原来的$id[p]$变成一个虚点,$id[p]=++tot$,这样就完成了删除操作，当然我们查找祖先时需

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4887 分析 话说这道题经常见到类似模型来计数算期望,概率啊,然而我太蒻了都不会做,今天看到这题的第一个题解感觉真妙啊 我们构建邻接矩阵$A$,$a[i][j]=1$表示i到j状态有连接的边。 如果有一条边连接$u,v$则$a[u][v]=1$且$a[v][u]=1$ $a[i][i]=1

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4241 分析 这题就是求区间权值乘以权值出现次数的最大值,一看莫队法块可搞,但仔细想想,莫队的加入很容易,但是删除需要维护许多东西,非常麻烦,于是就有dalao想出了一个新科技—回滚莫队.回滚莫队能使操作全部变成加入或全部变成删除.这道题我们需要全部变成加入. 怎么做呢？我们对询问进行处理

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2659 分析 难得做到此类打表题目,不觉回想到NOIp2017考场上的SB经历 这道题看到这么吓人的算式,当然是要…. 咳咳,像我这种菜鸡当然是先要打个表 好象没什么规律,但我们可以找找特殊项 比如(3,3)和(5,5),(7,7),大胆猜想若两数相同对于奇质数$x$，$ans=(x*x-

前言 在OI学习过程中,我们常常会发现一些题目(尤其数据结构题)中,一些数据的范围很大,但是涉及的数值的个数却很少,同时我们想用一个数组的下标与这些数据建立一一对应关系,这时我们就需要离散化 大致思路 对于一个大小为$N$不含重复数字的数组$a[N] (a[i]<=10^9)$,我们可以将$a[]$中的N个整数与$1$ ~ $N$这$N$构成一一映射关系,也就是说把$a[i]$用一个$1$~

前言 图论中联通性相关问题往往会牵扯到无向图的割点与桥或是下一篇博客会讲的强连通分量,强有力的$Tarjan$算法能在$O(n)$的时间找到割点与桥 定义 若您是第一次了解$Tarjan$算法，建议您反复阅读定义,借助图像来理解 桥与割边 对于无向连通图中点集的一个节点$x$,删去节点$x$及其关联的边之后,存在一对不联通的点对$(a,b)$,则称$x$是这个无向图的割点 对于无向联通图中边集的一