Category Archives: 2018.10

[数论+Phi]BZOJ2186沙拉公主的困惑

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

[SDOI2008]沙拉公主的困惑 题面传送门 上PoPoQQQ大爷的题解 若一个数与互质,那么也一定与互质,也一定与m!互质. 由于一定是的倍数,于是我们每存在到一个与互质,我们就一定能找到个与互质的数 而以内与互质的数的数量恰好是 所以答案等于:     考虑的展开式:   &n

Read More

[双连通分量+树上倍增+并查集+Kruskal]51nod1743雪之国度

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

[51nod1743]雪之国度 雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。 雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为。 如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于,这条道

Read More

[KMP+数位DP+矩阵快速幂]BZOJ1009GT考试

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

[HNOI2008]GT考试 神奇的KMP矩乘,从普及组A到提高组… 题面传送门 我们表示长串匹配到,短串匹配到的吉利的方案数。 设表示失配的方案数。 考虑转移: ,表示失配后短串匹配到哪个位置。 ?好像我们会!!! 可以先构造,原式写为: 可以看成矩乘:     然后上快速幂。

Read More

[启发式分治/线段树]BZOJ4059Non-boring Sequences

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

[Cerc2018]Non-boring Sequences 这是一道神奇的启发式分治题… 题目大意: 一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。 Solution: 对于当前分治的子区

Read More

初涉Kruskal重构树

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

初涉Kruskal重构树 一种贼牛逼的思路,本来NOI之后就想学的,但一直到现在才学习… 考虑下面这个问题:给定一个无向连通图,求路径上的最小值。 我会树连剖分!! 可以用重构树解决,代码复杂度和常数大大下降。 (从小到大)将边权看成一个新点,将它与路径两点集合以父子关系连边。 这是核心过程:(新建节

Read More

[BFS/DFS+最小生成树]BZOJ2753滑雪与时间胶囊

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

[SCOI2012]滑雪与时间胶囊 题面传送门 第一问很好做,就好了,DFS会爆栈,顺便处理能用的边。 以所到点的高度为第一关键字,边权为第二关键字排序,做。 这样做可以满足达到所有可到点的同时边权和最小。 #include <cstdio> #include <cctype> #incl

Read More

初涉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