ShanLunjiaJian's Blog

Welcome to My Blog!

好耶

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

Posted by ShanLunjiaJian's Blog on February 8, 2021

2023省队胡策 shanlunjiajian场

/tiao

A. sort 原题 International Collegiate Programming Contest, Japan Domestic D. Audience Queue 。考虑归并排序大概是说找到每一段的所有前缀 $\max$，把它们排序，剩下的数跟着前面的前缀 $\max$ 移动。也就是说 $t$ 的所有前缀 $\max$ 就是这里找到的所有前缀 $\max$。那么我们...

Posted by ShanLunjiaJian's Blog on June 10, 2023

数论从入门到不进省队

/dk

标题是因为我认识的两个数论大师，数学皇冠上的明珠 wky 和 donghanwen1225 都没进队。本文不主要讨论筛子相关内容。开根开根好像比$\ln$简单。最简单的情况是求解$x^k=a\pmod{p}$，$k,p$都是素数，且$k\not\mid p-1$。我们直接在膜$p-1$下求$k$的逆，然后计算$a^\frac{1}{k}$即可。注意到$ab$次根等于$...

Posted by ShanLunjiaJian's Blog on May 25, 2023

八轮省集

/cf

D1 127题。 A. dare bzoj3305。对于所有长$2n$的合法括号序列，求每个右括号左边的前缀和的乘积的和。$n\leq 10^7$。 $dp(i,j)=dp(i-1,j-1)+(j+1)dp(i-1,j+1),dp(0,0)=1$，答案就是$dp(2n,0)$。也就是$F_i=zF_{i-1}+F_{i-1}^\prime$考虑两边乘$e^\frac{z^...

Posted by ShanLunjiaJian's Blog on May 24, 2023

dfa技术

/cf

觉得需要搞一篇啊! dfa是啥大家都知道 dfa最小化 dfa应该如何最小化呢。我们都知道，肯定是把状态划分成若干等价类，每个等价类合并成一个，要求每个等价类中的点的后继们对应等价。考虑我们一开始让接受状态都合并成一个，拒绝状态都合并成一个，然后开始分裂，如果两个状态的同一转移指向不同的等价类，那么它们肯定也不在同一个等价类，需要把它们分裂一下。这称为moore算法。 ...

Posted by ShanLunjiaJian's Blog on May 21, 2023

七轮省集

/cf

D1 A. stones 这是一个典题。但是不知道在哪/kx B. tree 树，有一个函数序列$f(u)=v$，其中$v$是$u$向某个给定点移动一步得到的点，每次求区间复合的点值。$n\leq 10^5$，5s。分块先。零散部分容易线性。同时移动所有答案，考虑复合一个函数会发生什么。可能会有两个答案相撞，这玩意看起来就很有均摊。缩起直链用块状链表维护即可。复杂度$O(n\...

Posted by ShanLunjiaJian's Blog on April 17, 2023

雪灾与外卖

妈的，忍不了，一拳把差评点爆！

劲爆题。uoj 差评榜 rk3！我找到的所有题解都好像说了什么又好像什么也没说，所以打算自己胡乱写一个。可能是错的，欢迎交流讨论。注意匹配和增广的区别。我们把链横着放，餐馆放在上面，送餐员放在下面。先在左边加一个$c,w=\infty$的餐馆保证每个送餐员都能匹配。先考虑$c=1$怎么做。加入一个送餐员的时候，可能的增广路就是从他走到前面的一个餐馆，而如果选择最短增广...

Posted by ShanLunjiaJian's Blog on April 10, 2023

我挑选的经典题题单

/kk

可能不会经常更新。容斥 xxi open cup gp of tokyo H. Harsh Comments agc041 F. Histogram Rooks ($O(n^2)$) 氪金手游排列 (https://www.zhihu.com/question/393998538) 草，这个怎么没了?就是下面那个题$m=1$的case。 sd省队胡策21 qwaszx 顺...

Posted by ShanLunjiaJian's Blog on March 29, 2023

树分治的remake

/tuu

大家都会wctt!好的这篇结束了（一个cluster是一个边的连通块(把所有边的所有端点拿出来之后连通)，它有不超过两个点和树的其它部分相连，这些点称为boundary node 界点。因为界点只有不超过两个，每个cluster可以看成一个叶子或者一条边，cluster之间形成了一个收缩的树结构，不妨称为收缩树。所以把一个界点的cluster称为leaf cluster，两个界点的称...

Posted by ShanLunjiaJian's Blog on March 13, 2023

数数从入门到直僵僵地镶嵌在门框里

/cf

把所有数数trick统一放在这里好了。线性求多项式卷积的一项系数，线性插值一项系数抱歉，这是不可能的。但是请注意$O(n^2)$插值所有系数是不需要法法塔并且容易实现的，就直接把拉插的式子那个prod里面的东西全乘起来，每次除掉其中一项就行了，而这个除法是容易计算的。如果你的卷积是两个东西卷起来，那么可以直接卷。如果你想求系数的前缀和，那么可以拿一边卷另一边的前缀和。如果数量...

Posted by ShanLunjiaJian's Blog on March 5, 2023

重写筛子

怄火。

dgf dgf定义为$F(z)=\sum\limits_i\frac{f(i)}{i^z}$，容易知道它的乘法就是狄利克雷卷积。平时我们经常用$\mathbf{1}=\zeta$来表示其它的dgf，比如$\mathrm{id}_k=\zeta(z-k),\mathrm{\mu}=\frac{1}{\zeta},\varphi=\frac{\zeta(z-1)}{\zeta(z)},\m...

Posted by ShanLunjiaJian's Blog on February 25, 2023

格雷码相关问题

/kk

basic 我们要构造的是一个$[0,2^k)$的排列，使得相邻两个二进制有恰好一位不同。可以看成$k$维超立方体上的哈密顿路。分治，考虑我们现在构造了$[0,2^{k-1})$，那么都添上最高位的$1$就有一个$[2^{k-1},2^k)$的gray code。为了把两边接起来，我们只需要把右边反过来。注意到第一位总是$0$，最后一位总是$2^{k-1}$，这是一个环。 ...

Posted by ShanLunjiaJian's Blog on February 20, 2023

未归类问题

/kk

标题五个字/cf spoj CARD - Cardsharper 来自fajne zadania。考虑每个元素会如何移动。在$a$上沿着一个环走，在$b$上同样沿着一个环走。我们想起来一个经典问题，好像来自atc，说的是如果你能够转整个序列，或者转前三个元素，就可以排序。显然还有很多类似的东西。猜测我们总是可以生成绝大多数的排列。事实证明确实是这样，在几乎所有情况下我们可...

Posted by ShanLunjiaJian's Blog on February 9, 2023

[冬日绘板]税收计划

全世界无产者，联合起来!

好像一个月没发新文了。同步发表于洛谷。那里毕竟还是绘板主战场。新归零计划因为世界不可能平等而毁灭世界。但是我又发现了世界可能平等，所以新归零在它提出之后立刻被推翻了。我们希望一个人的(等效理想，也即考虑其脚本效率下；下同)token数和他维护的面积成正比，通过用恰好占场上一半的token来随机撒点就可以实现这个目标，这相当于对每个势力按照占领面积收税，或者如果一个token占领的...

Posted by ShanLunjiaJian's Blog on January 7, 2023

关于dfa的多串化，可能算是dfa杂谈

/jw

今天看了一个多串pam题，然后就来看看。简单dfa 最简单的dfa，比如，前缀自动机。前缀自动机的合并就是trie合并。如果你需要支持给一个trie挂叶子，更新合并后的trie，你发现这个好像很简单，只要在合并掉一个点的时候记录它指向了谁，然后并查集维护一下即可。 pam 妈的，空的之言可谓切中了肯綮。pam就是个带suffix link的trie，让你可以插入一个字符...

Posted by ShanLunjiaJian's Blog on November 7, 2022

更新了click test。

好耶

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

Posted by ShanLunjiaJian's Blog on November 4, 2022

讲稿索引

/hanx

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

Posted by ShanLunjiaJian's Blog on October 8, 2022

oi题选做

麻麻麻

从这一篇开始我要使用两个$作为latex的标识符。 polish oi poi大概是，有三轮，r1五题，r2 r3都是有D0 D1 D2，D0一题，D1 D2两题。 VIII(2000~2001) Stage 1 A. Liczby antypierwsze tooooooooooooooo classic。 B. Mapa gęstości 前缀和。 C. Przedzi...

Posted by ShanLunjiaJian's Blog on September 13, 2022

重写平方串，润和琳墩串

/dk

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

Posted by ShanLunjiaJian's Blog on September 7, 2022

线性代数

用啥学啥。

觉得应该开一个，所以就开了。特征多项式和零化多项式经典应用是常系数齐次线性递推。特征多项式是$\det(A-xI)$，零化多项式是$f(A)=0$。cayley-hamilton定理说明特征多项式是一个零化多项式。常系数齐次线性递推中，转移矩阵的特征多项式就是递推式，求这一矩阵的幂$A^n$，可以把它对零化多项式取膜，变成矩阵大小内的次数的线性组合这样的。特征向量和矩...

Posted by ShanLunjiaJian's Blog on September 3, 2022

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

狂笑

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

Posted by ShanLunjiaJian's Blog on July 20, 2022

用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，我们需要构造一个插...

Posted by ShanLunjiaJian's Blog on July 17, 2022

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

/ll

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

Posted by ShanLunjiaJian's Blog on May 9, 2022

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

/tuu

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

Posted by ShanLunjiaJian's Blog on April 29, 2022

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。...

Posted by ShanLunjiaJian's Blog on March 2, 2022

fib数列

/dk

Posted by ShanLunjiaJian's Blog on February 23, 2022

开杯题选做

/cf

XIX(2018~2019) Zhejiang A. Automorphism 考虑给一棵树，怎么算自同构数。考虑只有两棵同构的子树才能换，并且两棵同构的子树可以随便换。于是答案就是每个父亲相同并且子树同构的等价类大小的阶乘乘起来，我们称这个关系是等价。注意到挂一个叶子最多会增加$\log$对等价关系，因为每次等价子树大小都会翻倍。但是如何找到这些等价关系? 考虑这个性...

Posted by ShanLunjiaJian's Blog on January 23, 2022

icpc训练营题选做

/kk

很久之前就想开这个坑了（计划写hdu多校，ptz营，nowcoder之类的。但是比较咕啊。可能上了带学也会做吧，但是先上个带学再说/fendou 很多是胡的，不保证正确性，仅供参考。欢迎您来交流讨论，可以在评论区给我留言/se hdu多校这些题可以在vj上看到题面，但是并不能提交。讲道理胡题可以锻炼思维的精确度，也就是说你想出来基本是对的?（狡辩 hduoj好像马上就要复活了。...

Posted by ShanLunjiaJian's Blog on January 23, 2022

KTT

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

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

Posted by ShanLunjiaJian's Blog on December 10, 2021

听穿车万曲

/se

Posted by ShanLunjiaJian's Blog on November 19, 2021

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

实际上是一些trick

Posted by ShanLunjiaJian's Blog on November 16, 2021

板子

/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...

Posted by ShanLunjiaJian's Blog on October 25, 2021

AGC选㗅

fuck

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

Posted by ShanLunjiaJian's Blog on August 31, 2021

松毛虫诗集（

/se

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

Posted by ShanLunjiaJian's Blog on July 16, 2021

微积分和组合计数

¿

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

Posted by ShanLunjiaJian's Blog on June 21, 2021

dp和容斥

玄幻

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

Posted by ShanLunjiaJian's Blog on June 15, 2021

基数堆和Dij

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

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

Posted by ShanLunjiaJian's Blog on May 12, 2021

ARC选㗅

/kk

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

Posted by ShanLunjiaJian's Blog on April 27, 2021

类楼房重建线段树

有意思

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

Posted by ShanLunjiaJian's Blog on April 16, 2021

Hello World!

ShanLunjiaJian's new blog!

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

Posted by ShanLunjiaJian's Blog on February 8, 2021