Monthly Archives: 十月 2018

初涉Lucas

Cptraser/ 十月 28, 2018/ 2018.10/ 0 comments

Luogu模板题     #include <cstdio> using namespace std; int N,M,P,T; long long Inv[100005],Fac[100005]; long long Lucas(int x,int y){ if(x<y)r

Read More

[组合数学+快速幂]BZOJ2467生成树

Cptraser/ 十月 28, 2018/ 2018.10/ 1 comments

[中山市选2010]生成树 题面传送门 显然对于任意一个五边形可以删去条边中的任意一条边,每删去一条边,就会产生基环外向树上的一棵树,但是对于最后一个五边形,我们需要删去两条边,其中一条一定要是环上的边。 故答案为:     Code: #include <cstdio> #def

Read More

浅谈倍增Floyd

Cptraser/ 十月 27, 2018/ 2018.10/ 0 comments

浅谈倍增Floyd Floyd: Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 考虑这样一道题:求()经过边数为的最短路径。 倍增,记表示

Read More

[询问分块+主席树+离散化]BZOJ3720Gty的妹子树

Cptraser/ 十月 27, 2018/ 2018.10/ 0 comments

BZOJ3720 Gty的妹子树 题面传送门 大码力题,打的心累。 看过题面以后,你就可以开始长征了。 首先是没有加点和修改的情况,单纯的查询可以用序+主席树+离散化实现。 但如果加上修改和加点的话…… 我们就对其分块! 对修改和加点分块,每经过一块就重构一次主席树。 然后枚举这块里的修改

Read More

数论分块与莫比乌斯反演2

Cptraser/ 十月 26, 2018/ 2018.10/ 0 comments

数论分块与莫比乌斯反演(二) 相关链接:数论分块与莫比乌斯反演(一) 题目传送门 设为的约数个数,给定,求 关于有以下定理     Tips:证明考虑指数互质,然后感性理解 然后原式就转化成了:     我们考虑先枚举和:     接着推(日常展开):

Read More

[莫队+前缀异或和+奇偶块排序]BZOJ5301异或序列

Cptraser/ 十月 25, 2018/ 2018.10/ 0 comments

[CQOI2018]异或序列 题目传送门 前缀异或和,大力莫队。 奇偶排序: 这样能快是因为指针移到右边后不用再跳回左边,而跳回左边后处理下一个块又要跳回右边,这样能减少一半操作,理论上能快一倍 Code: #include <cmath> #include <cstdio> #inclu

Read More

[矩阵快速幂+递推]BZOJ4887可乐

Cptraser/ 十月 25, 2018/ 2018.10/ 0 comments

[TJOI2017]可乐 题目传送门 由题意可得DP方程: 表示第秒时机器人在点状态为自爆/未自爆。 表示与相连的边,这里是从走到点。 留在原地 这一秒自爆 之前自爆的状态 大力矩乘。 转移矩阵: Code: #include <cstdio> #define Mod 2017 using names

Read More

[矩阵快速幂+递推][Cqoi2018]交错序列

Cptraser/ 十月 24, 2018/ 2018.10/ 0 comments

[矩阵快速幂+递推][Cqoi2018]交错序列 题目传送门 二项式定理 设表示长度为,结尾是序列中之和。 构造转移矩阵即可。 Tips:这道题需要卡常,开 以后矩乘做完遍以后再膜。 #include <cstdio> #include <algorithm> using namespac

Read More

NOIP赛前整理~KMP

Cptraser/ 十月 24, 2018/ 2018.10/ 0 comments

KMP~从入门到放弃 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个nex

Read More