2019-04-12 17:16:12    189    1    0
博客每周歌曲 No.7 天空之梦 —— 《跳舞的线》 “一旦你尝试过天空的味道,你就会永远向上仰望。” ——莱昂纳多·达·芬奇 这种执着不是外物所能改变的啊…… 天空之梦
2019-03-27 19:43:08    583    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
解题记录 Atcoder    2019-03-22 19:24:21    428    0    0
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 题解:按照题意模拟就
多项式插值    2019-03-21 11:14:30    516    0    0
一、拉格朗日插值 所有数列都有规律——拉格朗日 比起牛顿插值,拉格朗日插值的名号要响亮的多。 而这个插值的想法和做法也十分简单: 设有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&#
解题记录 FFT|NTT 树链剖分 虚树 组合数    2019-03-18 12:09:49    452    0    3
题目描述 给你一棵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
解题记录 LOJ FFT|NTT 动态规划    2019-03-16 07:59:01    369    0    0
传送门 题解: 考虑怎么做这道题。 首先发现性质: 改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
解题记录 HDU 容斥 莫比乌斯函数    2019-03-15 15:47:54    251    0    0
GTW likes tree Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 191 Accepted Submission(s): 38 Problem Description GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi. Dis(x,y) is defined as
解题记录 LOJ 字典树    2019-03-14 15:26:58    256    0    0
题目链接 题解:发现只需要分两段维护就可以了。 上一次排过序的前缀部分用字典树维护,并且对每一位记录nowxor" role="presentation">nowxornowxornow_xor表示按照当前的顺序,第i" role="presentation">iii位是否被翻转。后面的部分用一个前缀和维护。 这样的话,异或的时候维护偏移值,每一次排序我们就把后面的部分全部插入字典树,并且更新now&#x005F;xor" role="presentation">now_xornow_xornow\_xor。 #include<cstdio&g
解题记录 LOJ 树链剖分 FFT|NTT 动态规划    2019-03-14 11:31:06    339    0    0
题目链接:传送门 题解:不难发现,我们有一个优秀的N2N^2的dpdp做法,记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个,当前根选没选。 我们要知道分治NTTNTT的复杂度:对于kk个总度数∑deg=k\sum deg=k的多项式来说,计算它们乘积的复杂度可以做到:O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此,我们采用重链剖分,先转移所有轻链。 不难发现, g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
解题记录 杂OJ 动态规划    2019-03-12 16:02:51    287    0    0
All submissions for this problem are available. WARNING: This problem has large input / output files. Use of faster I/O methods is recommended. Chef has a sequence of N positive integers { a1, a2, a3, ... aN }. The Sous Chef wants to choose another sequence of N non-negative integers { b1, b2, b