传送门
题意：计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和
以前雅礼集训的时候就听说过这题，好像是洲阁筛板子？
但是如今世道不同了，Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛！
当p∈Prime,f(pc)=3c+1" role="present
传送门
题意：计算σ0(ik)\sigma_0(i^k)的前缀和
一道牛逼题目，Min_25Min\_25筛写的很简短。
当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1
且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1
又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1)
直接Min_25Min\_25筛就行了，复杂度O(1011)O(10^{11})能过。
#include<cstdio>#include<algorithm>#
2020-09-14 13:41:50
889
0
0
以前一直以为自己写的点分治找对了重心。结果前几天自己写代码的时候，发现重心父亲一端子树的重心有问题。因为代码里传的子树大小是错误的，传的是当前根下父亲的子树大小而不是真正的大小。
当时感性想了一下发现卡不掉，最多也就是常数差别。今天发现原来这个问题已经有严格证明，所以可以放心这么“错误”地写点分啦~
>证明点我<
2020-08-09 10:24:22
681
1
1
从基础做起，把常见模板捡起来
FFT|NTT 2020/8/24
并查集
SPFA 2020/8/23
dijkstra 2020/8/23
树链剖分
Dinic 2020/8/21
SAM 2020/8/25
SA
点分治
Splay
LCT
非旋Treap
AC
MST
可并堆
费用流
CDQ
计算几何
2019-04-12 17:16:12
506
1
0
博客每周歌曲 No.7
天空之梦 —— 《跳舞的线》
“一旦你尝试过天空的味道，你就会永远向上仰望。” ——莱昂纳多·达·芬奇
天空之梦
2019-03-27 19:43:08
859
0
1
有一些出场率比较高的板子，现在还不能完全确定打对的，尽快填了吧。
Link-Cut-Tree
非旋转Treap
2-SAT
费用流
exgcd/excrt
BSGS
后缀自动机 (MRT)
Min-25筛
上下界网络流
AC自动机
边/点双连通分量 (MRT)
凸包
半平面交
Manacher (MRT)
回文自动机 (MRT)
二次剩余((c+i)(p+1)/2,(c2−a)(p−1)/2≠1(c+i)^{(p+1)/2},(c^2-a)^{(p-1)/2}\neq 1)/原根(原根太简单，好写好懂，不打了)
辛普森积分(已经弃坑)
kosaraju
A - Colorful Subsequence
简化版题意：输入一个字符串，输出每种字母的个数+1" role="presentation" style="position: relative;">+1+1+1的乘积的结果−1" role="presentation" style="position: relative;">−1−1-1。 |S|≤105" role="presentation" style="position: relative;">|S|≤105|S|≤105|S| \le 10^5
题解：按照题意模拟就
一、拉格朗日插值
所有数列都有规律——拉格朗日
比起牛顿插值，拉格朗日插值的名号要响亮的多。
而这个插值的想法和做法也十分简单：
设有n" role="presentation">nnn个点(xi,yi)" role="presentation">(xi,yi)(xi,yi)(x_i,y_i)，拉格朗日告诉我们一定有一个最多n−1" role="presentation">n−1n−1n-1次的多项式穿过这些点。
∑pyp∏i≠px−xixp&#
题目描述
给你一棵n个点的树，每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是：把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来，求：有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
传送门
题解：
考虑怎么做这道题。
首先发现性质：
改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
Rockdu's Blog