ShanLunjiaJian's Blog

仰天大笑出门去,我辈就是蓬蒿人

Welcome to My Blog!

好耶

Welcome qwq 我是陈语秋,是来自新疆维吾尔自治区 和田市第八十四中学的菜鸡OIer,现在(就是现在,而不是发这篇blog的时间)高二。 博客里有好多奇奇怪怪的东西。感觉不少是没啥用的东西。不过我还挺喜欢写blog的( 背景图知道出处的会注明出处。/fn 主页上不显示所有blog,只有近期的精选内容(不过我懒得取消上古内容的精选了)。如果想要看所有的,可以去All页面翻阅,但...

更新了click test。

好耶

(昨天)添加了hexo的经典点击放烟花特效,并进行了魔改,10s内连点10次可以触发cps测试,每点一下会显示五个当前cps(按近十秒计算)和一个历史最高cps(刷新会没掉),也可以通过console看到。我的个人纪录是12.9。 放一个空白区域。 好像需要写点什么才能不让最后显示一个\。

讲稿索引

/hanx

你去github上也能看到,但是可能比较困难,所以还是挂一个。 微积分和组合计数。用于数学作业。 扫描线方向和dp转移结构,忘了有没有使用过。 数论入门,于2022暑假中忘了哪天使用。 生成函数入门,于2022-10-04使用。 图论杂题选讲,于2022-10-06使用。汪娟锐评我说这么多牛逼题3h讲完太浪费了!

重写平方串,润和琳墩串

/dk

做xix open cup遇到了两个平方串题。再写一写,可能这次会比较深刻吧。 square(tandem repetition, repetition, repeat) 定义一个串是平方串,当且仅当它的前一半和后一半相同。它的前一半称作它的平方根或简称根。 类似地可以定义立方串,四次方串……但是它们意义不是很大。 boi2004 repeats 求一个串的子串的最高次数,...

从后缀尝试到在线线性紧致后缀金番茄

狂笑

部分译自 On-line construction of compact directed acyclic word graphs。外国看起来更习惯把suffix automaton称为directed acyclic word graph dawg,试译 有向无环字典图。但是我觉得sam就很好听啊( deepl有点拖拉机了,所以我用了生草机。然后就把au-tomaton翻译成了au番茄。...

用crt推导单位根反演

/fn

问题是我们有一个gf \(F\),要计算\([z^0]F\bmod{z^n-1}\)。计算\([z^k]\)的话可以先平移。 考虑分解\(z^n-1\)为\(\prod\limits_i(z-\omega_n^i)\),然后crt合并。我们知道\(F\bmod{(z-a)}=F(a)\),所以就要代入各单位根求值,然后crt的结论是答案是它们的线性组合。 为了crt,我们需要构造一个 插...

挑战npc : 一些一般图上的npc问题的在特殊图上的多项式做法

/ll

如果我们知道图论不可做问题在哪些图上可做,我们就可以大胆地把问题转化成图论问题,而不必担心转化出不可做问题。 我们将要讨论的问题包括 : 最小(权)独立集覆盖(染色) : 找到一个独立集覆盖,使得每个独立集中点权的最大值之和最小。 最小(权)团覆盖 : 找到一个团覆盖,使得每个团中点权的最大值之和最小。 最大(权)独立集 : 找到一...

再谈法法塔和单位根反演,然后是法哇塔

/tuu

模拟赛做了个奇怪题,然后就来学法哇塔的本质了。 但是感觉好像不是很知道自己在说什么啊。 循环卷积大概是这么一个东西 \[h_i=\sum_{j,k}[j+k\bmod{n}=i]f_jg_k\] 其中\(n\)是循环卷积的长度。这个东西有个\(j+k\bmod{n}=i\),让人很想给它单位根反演一下。 如果你不知道单位根反演,它是这么一个式子 \[\frac{1}{n}\s...

cf 2200~2600

本来说要一天五场vp,结果没人陪我打/ll 那就换成高强度切题吧。 要的是速度。rush。 打开cf,选rating 2200~2600,通过人数降序。 好像咕了。 86D 21:08开始。 莫队。 13min。 600E 21:22开始。 静态链分治。 20min wa on test 25。¿ 想不到吧,要开long long。21min passed。...

fib数列

/dk

整理了一些fib数列相关的经典问题和trick。 fib数列是\(f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}\)。 (OI中常见的)广义fib数列是\(f_0,f_1,a,b\)是任意值,\(f_i=af_{i-1}+bf_{i-2}\)的数列,不妨称为\(a,b\)-fib数列。\(a,1\)-fib数列是限制\(b=1\)的情况,单独把它提出来是因为它在循环节上有...

icpc及相关赛事题选做

/kk

很久之前就想开这个坑了( 计划写hdu多校,ptz营,以及open cup。这三个感觉上难度是递增的吗( 区域赛啥的先咕了,太多了不知道先做哪些( 很多是胡的,不保证正确性,仅供参考。欢迎您来交流讨论,可以在评论区给我留言/se hdu多校 这些题可以在vj上看到题面,但是并不能提交。讲道理胡题可以锻炼思维的精确度,也就是说你想出来基本是对的?(狡辩 hduoj好像马上就要复活了...

KTT

只有在这里你才会用到伵(

随了一个题(snoi2020 区间和),然后看了一眼题解,感觉像是ktt?就来学了。 EI队长《浅谈函数最值的动态维护》的学习笔记。 引入 问题是,你需要维护平面上的一些函数,每次查询这些函数与一条竖线的最高交点,或者说给每个函数代入\(x\),求其中最大的。 直线的情况是经典的,它就是个上凸壳。有结论说明,如果任意两个函数交点只有常数个,那么\(n\)个函数的上包络线(就是每个点所...

听穿车万曲

/se

收录车万及其相关作品。 按作者分类,每个作者争取按时间排序。 加粗的是特别牛逼的。我尽可能少加粗?(然而完全失败了) 如果原曲不是很牛逼,但是同人很牛逼,那么会只加粗同人。 神了! 应该是最高评价。一切尽在不言中? ZUN/上海爱丽丝幻乐团 一些闲话 听了脸圆之后,我觉得这个应该拿来收录和车万有关的曲子,而不只是车万曲。 旧作有不少收录在 东方幻想的音乐 了。 没有专门...

如果我不知道把一些东西放在哪里,那就放在这里吧

实际上是一些trick

呃。 不知道干什么的时候 (gf)不知道干什么的时候你就求个导。 (任何情况下)不知道干什么的时候你就打个表。 (线性规划)不知道干什么的时候你就对偶一下。 (数数)不知道干什么的时候你就容斥一下。 (数数)不知道干什么的时候你就看看是不是独立的。 (任何情况下)不知道干什么的时候你就枚举一个方向。 (主要是ds)不知道干什么的时候你就把时间维画出来。 (博弈论)不知道...

板子

/fn

有些地方写英语是因为懒得把输入法调回中文( _ general 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using std::vector; usi...

子集反演

奇怪

已经是中年选手了,却没有一个中年选手应有的科技树,这是为什么呢? 实际上我们很久以前就在我的blog见过子集反演这个同志了,那一篇是 一道可能是nowcoder上的题的题解。 但是那个还是太模糊,我们来看一看正统子集题的子集反演。 当然在此之前说明子集反演是什么 : 子集反演用于在 恰好是某个子集 和 在这个子集中钦定/钦定这个子集 之间转换。 现在有满足某种条件的元素集合\(A...

AGC选㗅

fuck

远古ARC(058~103)做完了,咕咕咕结束了,原坑 AGC数数题,但是反正要刷穿不如直接全做了。 打开AGC,从上往下做。简单题可能略过。 考虑了一下,题选做 这个tag的含义可能是记录我思考的过程,也就是一边做题一边写的笔记之类的。 这个咕了。新的atc选做在很后面。 AGC001B : 你发现这是一个类似于辗转相除的过程,所以就除就行了。存在直接用gcd算答案的方法,不过...

松毛虫诗集(

/se

松毛虫,又称smc,printf_jun,2005年生人,山东兰陵人,当代著名诗人。其诗作质朴纯真,贴近OIer生活,承白居易之精髓;不拘格律,有龚诗锋之遗风,故人称”孙诗豪”。曾蝉联SDOI群21天龙王,获得过2006年《时代周刊》年度人物、2008年「感动中国」年度人物特别奖等荣誉。代表作有七绝《无题(何以此词言与我)》,现代诗《无题(无趣的水一天群)》等。 由于毛诗多在水群过程中创作...

微积分和组合计数

¿

看了一眼,感觉以前写的东西都好拉啊?不过也不打算写新的了,因为还是会很拉/cy 参考抄写cmd 《多项式计数杂谈》,MiFaFaOvO 《A problem collection of ode and differential technique》。 众所周知,处理生成函数的时候我们经常遇到导数和积分,常见的是三种情况 : egf平移,例如 UR3 链式反应 ...

dp和容斥

玄幻

一些容斥之后用dp计算的题目整合。 CF Gym 102978H Harsh Comments GP of 998244353! CF上有一场番薯田大赛,大家都在往Announcement下面开喷。一共有\(n+m\)条评论,其中前\(n\)条是你发的,第\(i\)条获得了\(a_i\)个downvote;后\(m\)条是别人发的,第\(i\)条获得了\(b_i\)个downvot...

集合幂级数

草?

我觉得这个东西应该叫SPS Subset Power Series吧……管他的。 这一篇经过了改造,如果你很多年后再来看发现和以前不一样了,那就是改造的成果( 约定 集合幂级数可以看成次数膜\(2\)的多元多项式。 半半在线说的是按照集合大小从小到大给出系数(也就是一次给一整个大小),全半在线说的是按照数值从小到大给出系数。一般情况下半半在线已经足够,但是全半在线也有其用处。 ...

基数堆和Dij

为什么我这么喜欢用/kk当subtitle啊,/kk

最短路算法Dijkstra大家都知道! 今天我们来说一说,怎么用基数堆+Fib堆把Dijkstra优化到\(O(n\sqrt{\log v}+m)\),其中\(v\)是边权。 译自Faster Algorithms for the Shortest Path Problem。 翻译这个的原因是学校要带英文读物,然后我就带了这个论文……下星期可能还会看新的东西/cy 我们要干什么 众...

ARC选㗅

/kk

A Way to Practice Competitive Programming里面说要做一做ARC的EF,所以就来做了( 远古ARC资料太少了,所以我们还是做近代的(058及以后)吧( ARC058E : 还真就不会做/kk 发现\(x+y+z\)小的可怜,只有\(17\),看起来像是状压dp。 想了想怎么直接做,容易想到枚举四个端点然后背包预处理一个方案数,但是你发现这不行...

类楼房重建线段树

有意思

默认\(n,q\leq 10^5\)。 [清华集训2013] 楼房重建 给一个序列\(a\),支持单点修改,查询把所有数从右往左扔进一个单调栈之后,单调栈的大小。 当然一个等价的说法是有多少个数大于它前面的所有数,也就是是严格的前缀\(\max\),不过这里我们用第一种。 使用线段树。考虑如何合并信息。 这题要全局查询,但是我们可以考虑区间查询。 考虑如果左儿子最大值大于等于...

Hello World!

ShanLunjiaJian's new blog!

Hello world! 在github上搞了个blog,之前的文章哪天有兴趣就搬一下,然后以后写blog就是同步发表或者只发在这边了。 upd: 选了几篇比较有代表性的,先搬过来。发布时间都是按当时发的时间写的,所以看到有比这篇更老的是正常现象( 从洛谷blog搬过来的文章,有些洛谷图床上的图片是显示不了的,这个问题我闲着没事会解决一下。