All - ShanLunjiaJian's Blog

Welcome to My Blog!

好耶

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

Posted by ShanLunjiaJian's Blog on February 8, 2021

几个不需要静态top tree的树分治问题

咍咍

静态top tree，非常好数据结构! 22集训队胡策 R3 B. 举办乘凉州喵，举办乘凉州谢谢喵大家都会静态top tree做法，就是不停split直到这条链被拆成了$\log$个cluster path，然后直接在此时的收缩树上dfs即可。我们有一个点分治+重链剖分+长链剖分的1$\log$做法。考虑祖先-后代链咋做，大家都知道轻子树大小和是$n\log n$级别，所以就重...

Posted by ShanLunjiaJian's Blog on June 17, 2023

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

sdcpc23

青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。青鱼请我吃饭。

被H创死了。大家好我是坏耶 BAD的队长，我们在封榜前过了11题，封榜后我狂冲H，过了所有样例但是wa了。感谢青鱼删除样例。 A. 模拟 B. 模拟 C. 当然贪心，问题是我们如何比较两棵子树的字典序。考虑每次以较小的子树的大小的代价比较两棵子树，对两棵子树同时dfs即可，这样重子树相当于没有代价。每个点会在到根的链上贡献$\log\Sigma$的代价，复杂度是$O(n\lo...

Posted by ShanLunjiaJian's Blog on June 5, 2023

蒙日阵

劲爆

海草。海草。 Semi-local string comparison: Algorithmic techniques and applications 的导读。蒙日阵现在有一个矩阵$M$，它的下标是整数。定义它的分布矩阵$M^\Sigma$是它的子区间和，它的密度矩阵$M^\square$是它的二维差分，这里分布矩阵的下标是整数$+\frac{1}{2}$，密度矩阵的下标是整...

Posted by ShanLunjiaJian's Blog on May 31, 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

网络流从未入门

咍咍

在slides/2023-04-08-flow.html之后，想直接全部整理一下。

Posted by ShanLunjiaJian's Blog on May 8, 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++开发日志

/oh

打算用cpp重写一个uoj，或者重写一个qoj也行啊! 使用的库 https://github.com/yhirose/cpp-httplib https://github.com/pantor/inja https://mariadb.com/docs/skysql/connect/programming-languages/cpp/ https://github.com/S...

Posted by ShanLunjiaJian's Blog on April 12, 2023

雪灾与外卖

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

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

Posted by ShanLunjiaJian's Blog on April 10, 2023

物理

/kx

劲爆。今天突然想拿相对论推一遍电动力学的结论。狭义相对论测光速的时候，大家发现一个劲爆结论是不管在什么运动状态下测量，光速都是不变的，具体一点就是你向前发出一束光，然后以$0.99$倍光速前进，在你看来这束光的速度还是光速，而不是$0.01$倍光速。也就是说，时空在每个观测者看来是不同的。那么问题就是怎么在不同的观测者之间转换。认为空间是$d$维的，而时间是另外的一维...

Posted by ShanLunjiaJian's Blog on April 7, 2023

生电笔记

/cf

省选D1下午摸了一下午空岛，然后想起来要写这个。后来开了一个carpet sky additions服。简易刷怪塔寻路陷阱非常劲爆。如果有水，结合水流也是可以的。胡乱造造即可。不建议把红石用在这上面。守卫者塔前期必备的。玩空岛务必选择一个离海洋神殿近的种子，当然不建议神殿在常加载区块。我们随的种子，下面就是远古城市。直接在家打监守者/kx 刷铁机 ...

Posted by ShanLunjiaJian's Blog on April 6, 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

杨表

乐

已经是老年选手了，却没有一个老年选手应有的科技树，这是为什么呢? 杨图就是把ferrers图的点换成可以填数的格子。我们还是用从上往下每行的长度表示一个杨图。杨表杨图里填一个排列。标准杨表是每个格子填的数比右边和下边都小的杨表，如果连连边并固定所有极右下的格子，它就是一个拓扑序。如果杨图里填的不是排列。比右边小，不比下边大的称为行严格杨表，反过来就是列严格，这两种统...

Posted by ShanLunjiaJian's Blog on March 26, 2023

树分治的remake

/tuu

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

Posted by ShanLunjiaJian's Blog on March 13, 2023

thupc

/cf

5htoAk : 0htoAi, ShanLunjiaJian, fireinice。拉了。6题。场上会了B和C但是没有过掉。可见我的嘴巴已经是中国顶尖嘴巴，但手还是很烂! 如果手很好可以直接过D。乐。 A 考虑这么一个容斥 : 对于每对祖先-后代$u,v$，祖先A选贡献$1$，B选贡献$-1$，后代反过来，那么同一个人选的情况就抵消掉了。于是按$w+\mathrm{size}...

Posted by ShanLunjiaJian's Blog on March 5, 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

虽然是竞赛机房，机子还是每天remake C盘。于是我们需要想个办法让所有东西开箱即用。 qq 没有找到怎么做。每天重装得了。浏览器洋葱本身是完全portable的。它的浏览器部分是firefox的魔改。但是也不能全用洋葱，看了一圈在k-meleon，pale moon和icecat中选择了firefox。为了让firefox portable，使用 firefox....

Posted by ShanLunjiaJian's Blog on February 15, 2023

未归类问题

/kk

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

Posted by ShanLunjiaJian's Blog on February 9, 2023

关于如何成为vtuber

/oh

哪天出个道。咍咍! talking head anime是不错的。主要问题是用什么代替ifacialmocap。它的pc端是免费的，android上可以用meowface来搞定。然后经过混乱邪恶的多次尝试就连上了。很赢。你也看到我的fps只有4。这样是出不了道的。等我有钱了买个tesla玩玩。现在手里是3050，比较的拉! 需要注意的一个问题是，ifacialmoca...

Posted by ShanLunjiaJian's Blog on February 3, 2023

[冬日绘板]税收计划

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

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

Posted by ShanLunjiaJian's Blog on January 7, 2023

解析几何

发怒发怒发怒发怒发怒发怒发怒发怒发怒发怒

回去whk了。咕，因为并不会。直线直线是$ax+by=c$，非常建议这么写。可以为直线钦定一个唯一的最简形式，让$a,b,c$中第一个非$0$的是$1$即可。一个简单的和直线垂直的向量是$d=(a,b)$，可以称作是它的法向量，这是因为直线就是$(x,y)\cdot(a,b)=c$，也就是在法向量上的投影，乘上法向量长度为某个定值的点集。一个和直线平行的向量就是$(-b,...

Posted by ShanLunjiaJian's Blog on November 29, 2022

抽代

怄火

又感觉应该开一篇，所以就开了。浅谈群论在信息学竞赛中的简单应用宁波市镇海中学虞皓翔摘要群论在信息学竞赛中没有用。置换群论一个染色$\mathbb{c}$的轨道$G(\mathbb{c})$是所有置换作用于它的结果的集合。一个染色$\mathbb{c}$的稳定子群$G_{\mathbb{c}}$是作用于它时和恒等置换等价的置换的集合。问题是要计算不同轨道...

Posted by ShanLunjiaJian's Blog on November 24, 2022

关于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

rooks problem

怄火

大概是21年itst集训队论文的学习笔记。满棋盘是所有$(i,j):1\leq i\leq n,1\leq j\leq m$的集合。一个棋盘是满棋盘的一个子集。一个棋盘是轮廓线的，当且仅当每一列都是下面若干个格子存在。一个棋盘是ferrers的，当且仅当它是轮廓线的，并且每一行都是右边若干个格子存在。棋盘多项式定义一个棋盘$S$的rook number $r_k(S)$是...

Posted by ShanLunjiaJian's Blog on October 24, 2022

讲稿索引

/hanx

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

Posted by ShanLunjiaJian's Blog on October 8, 2022

atc选做

/jy

突然又想起来做atc了。之前阅读了arc058~103和agc001~022D，但是今天我不关心比赛，我只想钦点难度，这就不得不说 https://kenkoooo.com/atcoder/ 。选择了2000~3199。 arc150d 考虑一个点$u$被染的期望次数，只考虑它到根的链上发生的操作，注意到在这条链全黑之前$u$总是坏点，所以我们可以把只染坏点改成可以染所有点，...

Posted by ShanLunjiaJian's Blog on October 6, 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

一些阅读及其笔记

whk是一个必然会降临的节日。

呃呃，呃呃，反正总感觉一篇blog的第一行应该是一句话而不是一个标题，那就写这么一句话。更新时间跨度很大，所以有的地方会略显青涩，有的地方不够魔怔。史铁生所以whk是一件不必急于求成的事，whk是一个必然会降临的节日。这样想过之后我安心多了，眼前的一切不再那么可怕。比如你起早熬夜学OI的时候，忽然想起有一个长长的高三在前面等待你，你会不会觉得轻松一点？并且庆幸并且感激这样的安排？...

Posted by ShanLunjiaJian's Blog on August 27, 2022

三轮省集

我的青春......是不是还剩-1点啊?

没有见到山东的朋友们。由于lcez认为的疫情原因，以及noi22需要提前七天到昆山，所以原定在noi22之前举行的sdptt r3改为线上进行。但是双感觉我已经不再年轻了。 D1 爆力100+100+100=300。 A. adventure 求所有$n$个点的竞赛图中，$1$能到达的点数之和。$n\leq 10^5$，2s。考虑竞赛图缩scc之后变成链，把点分成...

Posted by ShanLunjiaJian's Blog on August 14, 2022

随机数据背包，Graham-Joux算法

/fn

背包也就是判定一个集合是否存在一个和为$k$的子集的问题。译自 A new generic algorithm for hard knapsacks http://www.joux.biz/publications/Knapsacks.pdf 。关于背包，大家都会直接折半，然后排序双指针。请注意，数据随机。指的是每个数是随机的，而目标可以不是随机的。为了简化问题，我们定义...

Posted by ShanLunjiaJian's Blog on August 7, 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

二轮省集

我的青春......是不是还剩0点啊?

双见到了山东的朋友们。又感觉我已经不再年轻了。 D1 爆力100+100+100=300，可惜我不会爆力。杜爷认为难度是B<C<A。 A. light 原题luogu7163 COCI2020-2021 #2 Svjetlo。树，每个点有一个0/1，给定初始状态，你需要选一条不一定简单的路径，翻转上面的状态，求变成全1最小路径长度。\(n\leq 5\times ...

Posted by ShanLunjiaJian's Blog on July 16, 2022

7月5日闲话 : 读x义x《食盐》

所有东西都可以戳到我的痛处啊?

对《食盐》更合理的解读收录于一些阅读及其笔记，本文仅作存档。感觉人的思想变深刻是很突然的事情呢。不要撑伞。你要流泪。你要走进雨中。眼泪是咸的。眼泪是食盐和雨。你是食盐。《食盐》 : https://www.luogu.com.cn/blog/zyxxs/si-yan 如果你想要理解，那么请先考虑这么几个问题 : 食盐是谁? ...

Posted by ShanLunjiaJian's Blog on July 5, 2022

线性规划

/se

只谈一点自认为比较深刻的。线性规划的可行解构成一个凸集或者说单纯形，而最大化的目标是一个去截这个凸集的超平面。 simplex所做的事情就是每次尝试沿着一个维度向增大目标的方向推动这个超平面，直到目标的所有系数变成负的，此时我们必然找到了那个截的位置。但是很遗憾，我们在推动它的过程中，会受到各约束的限制，而约束 ipm，或者说内点法考虑我们用一个牛逼函数，它在可行域内是\(0...

Posted by ShanLunjiaJian's Blog on July 2, 2022

一轮省集

我的青春......是不是还剩一点啊?

又见到了山东的朋友们。感觉我已经不再年轻了。 D1 爆力50+50+100=200/xia A. nset 给一棵树，给每个点分配一个权值，求对于所有$i$，权值$\geq i$的点构成一个连通块的方案数。但是这个问题太简单了，于是多次查询，每次钦点一个点的权值，求答案。$n,q\leq 10^5$，答案膜$998244353$。1.5s。考虑这个看起来就是把树分...

Posted by ShanLunjiaJian's Blog on June 18, 2022

两类欧拉积分

算力为负了/ll

第二类欧拉积分，gamma函数是 \[\Gamma(z)=\int_0^\infty t^{z-1}e^{-t}\mathrm{d}t=(z-1)!\] ，不是很知道它在哪里会被用到。第一类欧拉积分，beta函数是 \[\mathrm{B}(x,y)=\int_0^1t^{x-1}(1-t)^{y-1}\mathrm{d}t=\frac{\Gamma(x)\Gamma(y)}{\G...

Posted by ShanLunjiaJian's Blog on June 8, 2022

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

/ll

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

Posted by ShanLunjiaJian's Blog on May 9, 2022

纯粹的功能，实时的德克与卡廷化

/se

实际上是，支持合并的纯函数式deque。这个翻译是deepl给出的。大家都知道单链表是可以简单可持久化的，但是双链表不行。大家都会用单链表均摊地实现双端队列。那么如何可持久化双端队列呢?今天小编就带大家来看一看 https://dl.acm.org/doi/pdf/10.1145/324133.324139 这篇论文。这个可持久化deque是严格$O(1)$，而不是均摊$O(1)$。...

Posted by ShanLunjiaJian's Blog on May 7, 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

一些比赛的题解

/ll

因为没地方放就开了一个。联合省选2022 D1 A. 预处理器模拟。 B. 填树考虑枚举一条链，然后枚举最小值$l$，那么我们需要所有数都在$[l,l+k]$之中，并且有一个数$=l$。第二个限制可以用$[l,l+k]-[l+1,l+k]$差分掉，也就是我们拿$k-1$再跑一次。考虑固定一个区间$[l,r]$之后，一个点的方案数分成五段，贡献也分成五段。 ...

Posted by ShanLunjiaJian's Blog on April 24, 2022

斯特林数

很复杂啊（

qwq。第一类斯特林数求一行第一类斯特林数第$n$行的ogf就是$z^{\overline{n}}$，这个是经典结论。考虑倍增，我们现在知道$z^{\overline{n}}$，那么$z^{\overline{2n}}=z^{\overline{n}}(z+n)^{\overline{n}}$。考虑一个更广泛的问题，我们知道多项式$f(z)$，那么\(...

Posted by ShanLunjiaJian's Blog on April 19, 2022

拟阵

/se

还是过来学这个了（参考文献有，wiki上的若干词条，18年杨乾澜的集训队论文浅谈拟阵的一些拓展及其应用，15年wc董宏华的课件拟阵选讲，zghtyarecrenj的谷日报从拟阵基础到 Shannon 开关游戏，21年潘佳奇的集训队论文浅谈线性代数与图论的关系。如果你很有兴趣，可以看看Tutte的 Lectures on Matroids，反正我是懒得看了（拟阵一个子集...

Posted by ShanLunjiaJian's Blog on April 13, 2022

arras

/jy

大家都听说过arras.io和woomy.arras.cx! 我来随便扯两句。卡如果你很卡，那么干脆不要打。关于woomy-arras的ffa。 Sniper系 Auto-Freezer 个人纪录1.4m，41 kills。配装0068889300或者0058899300。打法基本就是跟着Auto炮开炮就行了，听起来很离谱，但是注意到Auto打的非常准，然...

Posted by ShanLunjiaJian's Blog on April 8, 2022

嘴巴选手挑战noio

qwq

提高组 A. 丹钓战直接做，对于每个位置求出后面那个弹掉它的位置，容易发现不管询问的开始位置在哪，这个都会被那个弹掉。然后从左端点开始每次跳到下一个弹空的位置，直到右端点，跳的次数就是答案。倍增或者离线排序并查集即可，后者上个基排就是线性。 B. 讨论考虑枚举一个元素，把所有包含它的集合拿出来，按大小从小到大排序，如果有大小相同的，随便用个啥去重一下，去重之后这两个肯定不相互包含...

Posted by ShanLunjiaJian's Blog on March 26, 2022

广义二项级数/广义指数级数

赵神赢，________

好水（赵神赢在模拟赛里面出了个不知道啥题，然后我转化成算Catalan数的$k$次幂的$n$次项系数，然而我不知道任何这方面的结论直接无了。具体数学上面的描述太过惊悚了。讲道理要是有个良好的引入像这个Catalan $k$次幂这样的，是不是机械求和法什么的也能看懂?感觉我过一段时间会回来补一句这是不可能的。广义二项级数$\mathcal{B}_t$满足递归式\...

Posted by ShanLunjiaJian's Blog on March 19, 2022

thupc2022初赛游寄

寄/jy

和我校的王卷王(id yixiuge777)，以及dysy初中部的do_while_true组队，队名是切卷对偶定理，英文则要更帅一些，是 oi-whk duailty theorem owdt。过了ABDFGIJK共8题，排在69名。看起来是包含sd现役oi选手的rk5，前面四个队应该都进决赛了，守门了啊/ll。前面四个是唐队长(青蛙。)，切队长(差不多得了)，核仁(一碗鸡汤)，王好...

Posted by ShanLunjiaJian's Blog on March 14, 2022

学习使用cpp

看起来还是很有必要啊（

一些标准库和语法的内容。主要参考cppreference.com。输入输出如果你是c党，想要读入一行，可以使用fgets(char *str,int count,FILE *stream)这个函数，看起来用法可能是fgets(s,inf,stdin)这样的。不过更好的方法是使用scanf("%[^\n]",s)这样的。来详细学习一下scanf()。 scanf()的第一...

Posted by ShanLunjiaJian's Blog on March 13, 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

鸽巢原理新解

/xia

你一定听说过鸽巢原理。并且如果你阅读过我的blog，我会把鸽巢原理称为鸽子原理。这是为什么呢? 考虑你找了$n+1$个大鸽子来办$n$件事(每个鸽子办这些事各一次)。由于他们是大鸽子，每个至少鸽一件事，于是至少有一件事同时被至少两个鸽子鸽了。所以它就叫鸽子原理(piegon principle/gu gu gu principle)。你学会了吗?

Posted by ShanLunjiaJian's Blog on February 22, 2022

群友诗集

/se

之前写了孙诗豪诗集，现在开个新坑收录所有群友的诗（爆零岁月 2022-02-17 wyx : 比赛响起爆零的讯号在他生涯里仿佛带点唏嘘平庸天赋给他的意义是一生奉献内卷斗争中强基把拥有变作失去 fys : 疲倦的代码带着Bug qyc : 今天只有n!^8的爆力迎接爆零岁月切队长随手阿克一生经过彷徨的挣扎自信可改变oi 问谁又能做到 ——wyx《爆零岁月》 ...

Posted by ShanLunjiaJian's Blog on February 17, 2022

dp of dp

/fn/fn/fn/fn/fn/fn

不懂了。跟着不知道哪里来的题单做一做。 dp是一个dag(除了spfa，但是spfa真的算是dp吗?)，然后每个点是一个计算单元，它接收前面的点的计算结果并进行加工，作为自己的计算结果，不妨将这样的东西称为计算网络，当然这是胡乱叫的，不要把这个名字拿出去说是我起的，并且你应该自己起一个/xia 如果想要计算满足某些条件的什么东西的个数，现在我们已经会用一个计算网络计算一个东西是否满足...

Posted by ShanLunjiaJian's Blog on February 16, 2022

超现实数的基本理论

/fn

咕。做了一个上古hdu多校博弈论题(09 contest3 E)，然后发现自己爆了（以下我们认为游戏都是两个人轮流进行，谁没法操作了就输了。也许可以在板子找到板子。定义一个博弈描述一个博弈游戏的局面，它由左集合和右集合构成，每个集合包含若干个博弈，表示左方和右方(Alice和Bob)操作一步之后得到的局面。我们可以写作$x=\{L\vert R\}$，这么...

Posted by ShanLunjiaJian's Blog on January 24, 2022

wc2022

/kk

Day1 上午信息学奥赛中的直觉与证明/jy 前面似乎非常亲民/se nwerc2018 Equality Control https://codeforces.com/gym/102483/problem/E 看起来好惊悚（给两个程序，只包含列表常数，合并，随机打乱，排序。判断它们是否相同。直接搞出最后的序列(每一段要么是一个常数，要么是一个序列随机打乱的结果...

Posted by ShanLunjiaJian's Blog on January 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

电子琴学习笔记

怎么会有这么奇怪的post（

发现所有人都会乐器，居然苏铁也是钢琴十级，于是我打算学一学电子琴。硬件是nektar gx61，软件是freepiano+scvt，网课是 https://www.bilibili.com/video/BV1nx411q72a?spm_id_from=333.999.0.0 。感觉用键盘弹也挺帅的，但是我这阿米洛樱花没有小键盘，也不想买新的了（首先你要会装freepiano。...

Posted by ShanLunjiaJian's Blog on January 14, 2022

你不会分析复杂度?我也不会

/fn

这是另一个讲稿，第一个是扫描线方向和dp转移结构。计划搞定之后给小朋友们讲。但是可能还要做大量的题才会有很多这方面的题扔进来（收录了一些离奇题，在你做完之后才会去尝试分析复杂度。当然很多可能对提高组选手来说并不离奇（ sdptt2021 r2 day4 B. 今天好像是dls的题?但是不知道原出处（给$n,m$，求$(0,0)$走到$(n,m)$的单增下凸函数...

Posted by ShanLunjiaJian's Blog on January 12, 2022

爆搜的胜利

/se

在看Itst的OI Memory，然后看到了 https://zhuanlan.zhihu.com/p/56269536 。下面这个题确实把我吓到了。然后我就把这个blog看完了，感觉上非常牛逼。给一个序列，求所有子序列中权值和第$k$小的。$n\leq 10^5,a_i\leq 10^9,k\leq 10^6$。考虑二分答案$d$，然后问题变成统计有多少个子序列...

Posted by ShanLunjiaJian's Blog on January 11, 2022

使用python asyncio那一套，写一个冬日绘板客户端

fuck

最快的冬日绘板客户端，它只差一车代理（讲道理，这个确实需要一个系统的讲解。异步就是开一个事件循环，然后有一个操作叫挂起，异步处理若干个异步函数(或者叫协程)的计算，如果一个函数挂起了，那么会去队列里找到下一个来执行，这样可以几乎总是做着有效计算，除非没有计算任务了。异步的调度速度比起线程调度器要更快，这是显然的。 python标准库提供asyncio来写异步。 asy...

Posted by ShanLunjiaJian's Blog on January 3, 2022

joi题选做

qaq

写的还是比较拉，会在新开的 oi题选做里面把这些再补一遍。本来是几个loj上的选做计划，然后只开了joi一个坑，后来发现loj的joi并不全，于是去atc上找了，于是就改名成刷穿joi了（怎么感觉joi经常被到处搬（发现dwt已经把这些刷穿了（ joi大概是，final相当于noi，sc相当于ctt cts，open相当于wc这样的。 https://www.io...

Posted by ShanLunjiaJian's Blog on December 18, 2021

随机造句

interesting

月考完了，我们来拿卷子随机造句（本题共3W小题，每小题99分，共$k+\tan\alpha$分。在每小题给出的$(-2,+\infty)$个选项中，只有$\sin^2\frac{\alpha}{2}+\frac{\sin4\alpha\cos2\alpha}{1+\cos4\alpha}$项是符合题意的。现代文阅读II \[^7\mathrm{LiH}\] ...

Posted by ShanLunjiaJian's Blog on December 17, 2021

猜帽问题

¿

太阳爆了英才，然后被小学奥数题干爆了。拉了。一类经典问题，从不知道进行推理。从一个笑话开始。三个绝顶聪明的人走进酒吧，招待问，都来一杯啤酒? 第一个人说，我不知道。第二个人说，我也不知道。第三个人说，是的。这个笑话的意思大概是，第一个人说不知道，说明她肯定想要啤酒，不然她就会说不是都要啤酒了。第二个人也是一样的，所以第三个人知道大家都要啤酒。于是我们知道，不知道...

Posted by ShanLunjiaJian's Blog on December 13, 2021

KTT

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

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

Posted by ShanLunjiaJian's Blog on December 10, 2021

期望线性MST

¿

好水（铃在谷群说有线性mst的科技，然后就找了一篇来看。严格线性mst看起来很离谱，期望线性则还可以。它俩的难度大概类似于sa-is之于dc3? 如果我们现在有一个生成树，那么不在生成树上的边可能可以更新这个生成树，方法是把它在树上经过的路径上边权最大的边拿出来，尝试用它来替换。如果这个最大边比这条不在树上的边边权小(不包括相等)，我们称这条不在树上的边是重边，否则这条边是轻边。引...

Posted by ShanLunjiaJian's Blog on December 7, 2021

Higman引理

¿

警告 : 这篇文章的主体部分未完成，并且可能将来也不会完成了。太离谱了。 TREE(3) 如果你看过一些数学科普，那么你应该知道$TREE(3)$。 $TREE(2)$随便就数过来了，而这个数是如此之大，并且它还是有限的，这真是太奇怪了。 Minimal Set 给一个语言(字符串的集合)$L$，它可以是无限集，它的Minimal Set定义为从小到大排序之...

Posted by ShanLunjiaJian's Blog on November 24, 2021

扫描线方向和dp转移结构

垂直屏幕向外扫描线

呃这个可能会用作讲稿? 呃现在确定要用作讲稿了，寒假里会给小朋友讲。作为弱校选手，公开的资源很重要，自己写的东西肯定是会给大家公开的/se 打算继续公开校模拟赛题，因为反正所有题都是搬的（ sdfz还没牛逼到有人可以出模拟赛。上古时期的模拟赛题，有两个合集可以在Czzsy0531(讲道理，应该是cunzai_zsy0531)的luogu blog找到。来更新第二部分，也就是dp...

Posted by ShanLunjiaJian's Blog on November 21, 2021

noip2021题解及游记

/fn

除了D都有简单做法了（ A 埃筛。 B 数位dp。 C 考虑这个操作等价于任意重排差分数组，于是我们考虑什么样的重排可以让答案最小。注意到是方差，贪心地，我们一定是放一个双调的，也就是先增大然后减小，这样可以快速逼近平均值而慢速离开平均值。然后你发现第一项和最后一项都不能动，所以我们可以从大到小枚举差分数组的一项，决策加到左边还是右边。枚举一个平均值，于是...

Posted by ShanLunjiaJian's Blog on November 20, 2021

听穿车万曲

/se

Posted by ShanLunjiaJian's Blog on November 19, 2021

icpc济南站2021

rush

sdfz两个队都进金线了/se 但是非正式只有三个金，我们是守门员/cy 收录一下正常水平队伍应该切掉的八个题。B不包含在内。 A. Space Ship 三维空间中有$n$个球，$n-1$个棍，连成一棵树。支持把一个棍沿着一个球在某一维上转90度，或者查询两个球的距离。$n,q\leq 10^5$。对于一根棍，转两边都可以转化成转深度更大的一边。用树剖维护变换复...

Posted by ShanLunjiaJian's Blog on November 17, 2021

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

实际上是一些trick

Posted by ShanLunjiaJian's Blog on November 16, 2021

线性规划对偶

离谱

关于线性规划对偶定理的一些问题。对偶是什么，你真的知道吗?(wikipedia) 经典的引入 Alice开了一个拖拉机厂，她进购了一批铁，轮胎和发动机，这些东西可以用来生产拖拉机，挖掘机和三蹦子(为什么三蹦子的发动机和轮胎和拖拉机是一样的啊¿)，每个都需要一定量的原料。显然，Alice希望自己的利润尽量大。 Bob有一个魔法工厂，他用铁，轮胎和发动机批量生产黄金，于是Bob想买...

Posted by ShanLunjiaJian's Blog on November 15, 2021

双端优先队列 : min-max heap和deap

有时候还挺好用的（

Min-Max Heap min-max heap是一种堆，其中的结点在奇数层(根在第一层)满足小根堆的性质，在偶数层满足大根堆的性质，这个性质说的是根是子树中最小/最大的。注意到min-max heap的最小值必然是根$1$，最大值必然在$2,3$中，如果只有一个元素则需要特判。 min-max heap的操作和二叉堆基本相同。插入的时候，如果插入在奇数层，那么我们首先检查...

Posted by ShanLunjiaJian's Blog on November 9, 2021

素性测试

数论入门读物/cf

(实际上是摘抄wiki) 突然想起来还没写过MR，于是来写一篇，同时写一些别的东西。众所周知，有个东西叫费马小定理。人们发现费马小定理在膜数不是素数的时候有不小的可能性是不成立的，所以就考虑用这个来判定一个数是不是素数，也就是找一些$a$，如果$a^{n-1}\neq 1\pmod{n}$，那么就说明$n$不是素数。固定一个$a$很容易就没了。让一个$a$没了的数$n$被称为关...

Posted by ShanLunjiaJian's Blog on November 3, 2021

用Sublime写Wolfram

牛逼

安装Wolfram Engine 打开Sublime，用Package Control安装WolframLanguage，然后新建编译系统，写一个 1 2 3 4 5 6 7 8 { "encoding":"gbk", "shell_cmd": "wolframscript -file $file_name -print", "selector": "source.wl", "w...

Posted by ShanLunjiaJian's Blog on November 1, 2021

带项式的常数优化

你的exp怎么比我的inv还快?

板子库里有Poly，所以写一下带项式的常数优化吧。摘抄自negiizhao的blog。记号长度$n$总是某个$2^k$。 $\mathrm{E}(n)$表示做长度为$n$的dft的时间。显然有$\mathrm{E}(2n)=2\mathrm{E}(n)+O(n)$，一般来说线性的部分我们可以忽略。 $\mathrm{M}(n)$表示做长度为$n$的...

Posted by ShanLunjiaJian's Blog on October 31, 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

子集反演

奇怪

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

Posted by ShanLunjiaJian's Blog on October 18, 2021

数学作业

退钱

参考cmd 《多项式计数杂谈》，MiFaFaOvO 《A problem collection of ODE and differential technique》。众所周知，处理生成函数的时候我们经常遇到导数和积分，常见的是三种情况 : EGF平移，例如 UR3 链式反应 OGF凑系数，例如$\vartheta$算子利用微...

Posted by ShanLunjiaJian's Blog on October 9, 2021

Z algo

吃串串

Z algo，或者说扩展kmp，实在是非常经典。大家第一次见到这个科技，可能是在动物园，也可能是在 ARC058F。题外话是，我认为058F超越了一直到103的所有ARC传统题(意思是070F这个交互可能竞争最棒的ARC058~103题)，所以我来学Z algo了。 Z algo用来求出一个字符串的$z$函数，其中$z(i)$的定义是$s$和它的后缀$i$的最长公共...

Posted by ShanLunjiaJian's Blog on October 7, 2021

Silde Test

好耶

很好很好，以后可以用reveal.js了

Posted by ShanLunjiaJian's Blog on October 2, 2021

PAM；回文和border理论

My string technology is tooooooooooooooooo weak.

pam是简单的自动机，它用于计算和索引一个串所有回文子串及它们的结构。pam和border理论可以很好地结合，从而搞出一些看起来很牛逼的题。比起manacher，pam的优势在于它处理了回文子串的结构。 pam的理论和构造 pam保存了一个字符串中所有的回文子串，其中每个结点都代表着一个回文子串，当然任意两个结点代表的回文子串是不同的。 pam存在的可能性基于这样一个定理 : 定...

Posted by ShanLunjiaJian's Blog on September 9, 2021

kmp的正确用法，或者说border理论及其应用

Your string technology is tooooooooooooooooo strong.

说起border理论，大家第一次接触这个东西，可能是在最小回文划分或者论战捆竹竿，或者压根就是这篇blog。这个看起来非常复杂，但是实际上并没有那么可怕哦。参考 command_block Border理论小记，以及ix35 NOI 一轮复习 II：字符串。定义，简单结论和约定周期就是周期。 $s$的一个border是一个串，它既是$s$的前缀又是后缀。这个容易用...

Posted by ShanLunjiaJian's Blog on September 8, 2021

省队胡策

/kk

侵删。 chz T1 给一个序列和$k$，定义一个区间的权值是其中只出现一次的数的个数，求有多少种划分这个序列的方式，使得每一段的权值不超过$k$。$n,k\leq 10^5$。爆力dp显然，如何优化? 考虑加入一个数的时候，用数据结构维护左端点，那么相当于对一个区间的权值$+1$，另一个区间$-1$，要查询全局权值$\leq k$的位置的和。容易用分块搞...

Posted by ShanLunjiaJian's Blog on August 31, 2021

AGC选㗅

fuck

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

Posted by ShanLunjiaJian's Blog on August 31, 2021

模拟费用流

感性理解

Posted by ShanLunjiaJian's Blog on August 21, 2021

松毛虫诗集（

/se

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

Posted by ShanLunjiaJian's Blog on July 16, 2021

三轮省集

/kk/kk/kk

再再次来到宇宙中心曹县所在的省份参加省队集训。 Day1 模拟赛 T1 原来是简单题/ll 给一个$m$次多项式$f$，$a_0$和$b,c$，求 \[a_n=a_{n-1}+f(n)a_{\lfloor\frac{n+b}{c}\rfloor}\] 。$m\leq 20,n\leq 10^{18},b<c-1$，膜$1004535809$。考...

Posted by ShanLunjiaJian's Blog on July 16, 2021

Cost Scaling和Double Scaling

uoj屠榜算法

upd:现在不是了!rk1写的是网络单纯形，会学的会学的/ll 以下默认我们做的是最小费用循环流。$C,U$分别指费用和流量的值域。网上找了一堆东西，最后找到了原论文，Finding Minimum-Cost Circulations by Successive Approximation，可以在这里看到。定义和简单推论定义一个循环网络是说每条边有一个容量\(u(v,w)\...

Posted by ShanLunjiaJian's Blog on July 2, 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

集合幂级数

草?

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

Posted by ShanLunjiaJian's Blog on June 10, 2021

二轮省集

/kk/kk

再次来到宇宙中心曹县所在的省份参加省队集训。 Day1 模拟赛 T1 麻将给一个01串，求最短的没有作为子串出现过的01串，多解输出字典序最小的。$n\leq 2^{24}$，0.2s。省选计划原题（考虑答案长度不会超过$24$，从大到小枚举答案，问题变成求长$k$子串的$\mathrm{mex}$，维护一个值域bool数组表示每种子串是否存在就好了。你发现...

Posted by ShanLunjiaJian's Blog on May 30, 2021

DGF

感觉还是不够深刻?

以下如无特殊说明，默认数论函数贴在一起的乘法和乘方都是点积，除法是狄利克雷除法。 DGF是什么 DGF定义为 \[\tilde{F}(z)=\sum_{i=1}^\infty\frac{f_i}{i^z}\] 。容易发现它的卷积就是狄利克雷卷积。常见的DGF 最基本的DGF是黎曼函数$\zeta=\sum_{i=1}\frac{1}{i^z}$，它也是恒等函数\(\math...

Posted by ShanLunjiaJian's Blog on May 19, 2021

APIO2021的课

还挺强

5.19 决策单调性与四边形不等式抽象决策单调性优化的dp总是可以转化成在矩阵中求每一行最小值的问题。比如经典的方程 \[dp(i)=\min_{j<i}(dp(j)+w(i,j))\] 就可以用$A_{i,j}=dp(j)+w(i,j)$构成一个矩阵$A$，这样$i$行的最小值就是$dp(i)$。以下默认一行的最小值是位置最大的最小值。啊当然我们一般没有必要整个求出这...

Posted by ShanLunjiaJian's Blog on May 19, 2021

高斯整数

/fad

我可能有时候用质数，有时候用素数，大家懂的都懂即可（高斯整数是形如$a+bi$的数，其中$a,b$都是整数。画到复平面上，高斯整数就是整点。高斯整数对加法和乘法都是封闭的，并且存在加法单位元、逆元和乘法单位元。然而只有$1,-1,i,-i$是可逆元(有乘法逆元)，当然这四个构成一个群，称为高斯整数的可逆元群。对于$z=a+bi$，定义$\overline{z}=a-b...

Posted by ShanLunjiaJian's Blog on May 17, 2021

thusc2021游记

爆零啦

说在前面切朗瑞天下第一帅! Day0 旷了一天的课，坐枣上的火车到了杭州。真的热…… 据说ytez前一天就来热身了。 Day1 上午讲座。扯了半天清华怎么好，怎么上清华反而一笔带过/jy 然后suxxsfe就去紫金了。教练跟着去了，剩我一个在嘻嘻/jk 去找到了切队/se，然后在大礼堂睡大觉。下午。开题，这个T1啥东西? 弃了弃了，看T2。好像可做? 看了一...

Posted by ShanLunjiaJian's Blog on May 16, 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

法嘛塔，或者说sos dp

有趣

法嘛塔和sos dp说的都是子集前/后缀和，用来求解一类这样的问题 : 给出$g$，求 \[f(S)=\bigoplus_{T\subseteq S}g(T)\] ，其中$\oplus$是任意交换律、结合律运算。为什么要交换律?因为子集的枚举顺序很多，法嘛塔也不知道你要的是哪一种，并且一般情况下我们用到的运算都有交换律。我的板子习惯和法法塔类似，写起来大概是 1 2 ...

Posted by ShanLunjiaJian's Blog on May 11, 2021

一轮省集

/kk

来到宇宙中心曹县所在的省份参加省队集训。还有很多锅，可能很久才能补完，不过反正没人看，有人看大家也不要着急（目前在补Day3，意思是12已经补完了/jy。 Day1 模拟赛兔队(PinkRabbit)搬题。 T1 permutation XXI Opencup, GP of Tokyo, Problem. I CF Gym 102978I 给一个长$m$，值域\(...

Posted by ShanLunjiaJian's Blog on May 1, 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

换根dp

恶心

感觉完全没啥用啊。呃口胡了一套智障符号化方法。例题只有一道，所以算是还在施工吧。换根dp解决一类性质比较好的子树为阶段的dp，其中看起来需要以每个点为根做一遍dp，不过实际上可以只dp一遍，然后通过父亲之类点的信息快速推出当前点为根的dp值。我们设$dp_r(u)$表示以$r$为根时$u$的$dp$值，那么显然有子树不变的结论如果以$u$为根时，\(...

Posted by ShanLunjiaJian's Blog on April 25, 2021

连通性相关问题

玄学

还在施工。整合了Tarjan的SCC，割点割边，DCC；以及支配和支配树；它们的例题。其中DCC正在施工，支配树还没学/kk 连通几乎是废话。强连通有向图中，两个点强连通，当且仅当它们可以互相到达。换句话说$u,v$强连通当且仅当存在$u\rightsquigarrow v$和$v\rightsquigarrow u$。强连通分量的定义是强连通的极大子图...

Posted by ShanLunjiaJian's Blog on April 16, 2021

类楼房重建线段树

有意思

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

Posted by ShanLunjiaJian's Blog on April 16, 2021

CF再选做

定个小目标，今年上Newbie

打算今年上个Newbie（所以来刷穿CF了，选了Rating 2600+，按通过人数降序。然而发现刷不穿，甚至完全做不动。那就多见点经典题吧! 如果真有人想看这个的话，请结合CF的题库来阅读，当然选和我一样的tag。如果做法只有几个意义不明的字，说明这题太简单或者太经典。 13E : 弹飞绵羊 321E : 题意不是很清晰。考虑直接dp，设\(dp(i,j...

Posted by ShanLunjiaJian's Blog on April 13, 2021

luogu省选计划2021

今天又是爆零的好日子

R1 T2 求$\sum_{i=1}^n f(i)$，其中$f(n)$表示$n$的最大平方因子。$n\leq 10^{14}$，$100$次询问。单次询问显然可以Powerful Number，复杂度是$O(T\sqrt{n})$，卡的就是你（打表发现构造出来的$h$只在完全平方数处有值，于是可以用经典trick优化到\(O(\sqrt{n}+T\sqr...

Posted by ShanLunjiaJian's Blog on April 9, 2021

莫比乌斯反演、子集反演以及min-max容斥的瞎扯

绝了

感觉一点都不绝捏。把多重集写成多元gf来考虑就会简单了吧。公式如果出现问题，可以右键任意一个公式，选择Math Settings->Math Renderer->Common HTML，可以解决一部分问题。众所周知莫比乌斯反演就是多重集的子集反演，gcd就是min，lcm就是max。说完了。具体一点?一个数的质因子集合是一个多重集，这个多重集上的子集反演就是莫比乌斯反...

Posted by ShanLunjiaJian's Blog on April 5, 2021

好像是nowcoder上的一道题的题解

降智

公式如果出现问题，可以右键任意一个公式，选择Math Settings->Math Renderer->Common HTML，可以解决一部分问题。题号忘了（题意 : 对于所有长$n$，值在$[1,m]$之间的序列$a$，求 \[\prod_{a}\mathrm{lcm}(a_i)^{\gcd(a_i)}\] 。$n\leq 10^9$，\(m\leq...

Posted by ShanLunjiaJian's Blog on April 5, 2021

状压dp学习笔记

/jy

模拟赛考了一个轮廓线dp，然后输出样例走人……就爬来学了…… 状压dp是什么呃，就是当转移必须考虑前面做出的$\omega(1)$个决策的时候，把这些决策加入状态中进行转移。为什么是$\omega(1)$?因为$O(1)$的一般不叫状压dp。基本的状态运算二进制运算优先级，从高到低是 : ~最高，<<,>>其次，&再次，|最低。注意&...

Posted by ShanLunjiaJian's Blog on April 4, 2021

优化建图

有意思

为了让复杂度能看一点，Dij默认使用Fib堆优化的Dij。 Range Query数据结构包括线段树，k-dt和一些别的奇怪数据结构(比如分块?)。不再多说。分块有一个应用挺好玩。例题 CF786B Legacy 线段树优化建图板子题，不再赘述。 ARC069F Flags 最小值最大，显然二分答案。然后就变成，如果选了$x$，那么\([x-mid+1,x+...

Posted by ShanLunjiaJian's Blog on April 2, 2021

NOIP2021 游记

退役了啊!

打完Day 1，晚上睡不太着，先写一下。 Day 0 跟sdfz的同志们坐高铁到了日照。这是高二的学长们参加的最后一届NOIP了，他们几个都在切神仙题(NOIP前做静态Top tree+法法塔真的有帮助吗，zsy?)，我呢在和小朋友们聊天。发现kdw这一年进步好快啊!感觉已经吊打初三的我了，我被单调队列了/cy。码神kdw！ ljc在调他的Simplex来放松(这也叫放松?)，...

Posted by ShanLunjiaJian's Blog on April 1, 2021

ddp总结和题选做

得得得得得得得得得得得得得得得得得得得得得得得得得得得得得得p（bushi

ddp通过把转移写成矩阵的形式来证明结合律并简单地合并转移。一般情况下，由于转移具有结合律并可以快速合并，我们使用线段树等数据结构来维护转移，从而解决带修改或range query的简单dp问题。广义矩阵乘法，两个基本定理首先我们要定义广义矩阵乘法。设$\oplus,\otimes$是两种运算，那么定义两个矩阵$A,B$的广义矩阵积$C$为 : \[c_{i,j}=\b...

Posted by ShanLunjiaJian's Blog on March 28, 2021

PGF学习笔记

解决概率期望问题的好家伙

参考18年集训队论文《浅谈生成函数在掷骰子问题上的应用》。一个随机变量$X$的PGF定义为 : \[F(z)=\sum_{i=0}^{\infty}\mathrm{P}(X=i)z^i\] 当然需要满足$X\geq 0$，不然这就不是一个带项式了。容易发现 \[\mathrm{E}(X)=\sum_{i=0}^{\infty}i\cdot\mathrm{P}(X=i)=...

Posted by ShanLunjiaJian's Blog on March 23, 2021

CF思维题选㗅

不想上GM的Newbie不是好Newbie

再开一个坑，整合各种各样的思维题。 CF脑力题选做!(你可以看到URL里面是cf-brain-power-problems) 先是一点理论，大概是jly集训队论文的东西。解决构造题的利器 : 抽屉原理，平均值定理，这两个可以用来满足各种”至少/至多”限制。归纳法和递归，用归纳法证明方案存在性的时候常常可以得到递归构造的算法。 dfs树(图论问题)。 1495F : ...

Posted by ShanLunjiaJian's Blog on March 12, 2021

k-DT

我n^2过2e5!

k-dt(k近邻树)是一种维护$k$维空间中点集的数据结构。它称为k近邻树，是因为它最开始被发明就是用来求点集中到一个点最近的点。为了避免歧义，以下用”结点”指k-dt上的点，用”点”指给出的点集中的点。应用k-dt时，一般有$n$远大于$2^k$，这里直接认为$k$是常数。在OI中，k-dt一般维护二维空间，此时它也称为2-dt。2-dt维护一个二维空间中的点集，它的每个结点维...

Posted by ShanLunjiaJian's Blog on March 11, 2021

雅礼集训2019 Day2 题解

神仙T3

T1. two 题意 : 有两棵树，结点相同而边不同。定义一条边$x$对另一条边$y$有害，当且仅当两条边不在同一棵树上，并且在$y$所在的树上，$x$的一个端点在$y$较深端点的子树中，而另一个端点不在。接下来进行若干轮删边，第一轮删掉一条给定边，此后每一轮删除所有对上一轮删掉的某条边有害的边。输出每一轮删了哪些边。 $n\leq 10^5$，时限4s，空...

Posted by ShanLunjiaJian's Blog on March 7, 2021

单位根反演学习笔记

好家伙

我们要求一个gf $F(z)$的所有$k,2k,3k,...$次项系数之和，它就是$[z^0](F(z)\bmod{(z^k-1)})$这样的。对这个东西我们看起来完全没办法，考虑把$z^k-1$分解成$\displaystyle\prod_i (z-\omega_k^i)$这样的，然后我们知道膜$z-a$就是求$F(a)$。最后crt合并即可。搞一搞可以得到...

Posted by ShanLunjiaJian's Blog on March 7, 2021

ICPC2020济南站 L. Bit Sequence 题解

/kk

我参加的第一场ICPC/kk，赛时跟zrz搞了两个小时这个L(，同时gkj搞了两个小时A)，还是没有搞出来，最后四题打铁了/kk 然后模拟赛出了这题的加强版，我一看这不是原题吗?结果写不动爬了/kk 好了我们进入正题。题意 : 给一个长$m$的01序列$a_0,...,a_{m-1}$，求$[0,L]$间有多少个数$x$满足$x+0,...,x+m-1$的\(\m...

Posted by ShanLunjiaJian's Blog on February 28, 2021

Min_25筛学习笔记

毒瘤

可以阅读更新的重写筛子，本文仅作存档。本文参考wqy神犇的blog。好像快要学完数论板子了呢! Min_25筛是扩展埃氏筛(Extended Eratosthenes Sieve, EES)的一种，是日本选手Min_25发明的，用来求一类积性函数的前缀和。它的应用范围广，代码难度与杜教筛接近，常数很小，把洲阁筛吊着打。不过它的推导过程有些奇妙，比杜教筛和Powerful Numb...

Posted by ShanLunjiaJian's Blog on February 19, 2021

Powerful Number学习笔记

求积性函数前缀和的奇妙方法

本文参考zzq神犇的blog。要求数论函数的前缀和，大家都会杜教筛。 Powerful Number跟杜教筛是类似的。杜教筛构造$f\ast g=h$，其中$g,h$可以快速求前缀和；而Powerful Number构造$f=g\ast h$，其中$g$可以快速求前缀和以及质数幂处的点值，而$h$只在Powerful Number处有值。首先我们来看一道例题。 ...

Posted by ShanLunjiaJian's Blog on February 18, 2021

置换群论学习笔记

玄妙而优美的鬼东西

这里主要是对Burnside定理(或者说引理)和Pólya定理的一点讲解。主要来自机械工业出版社的《组合数学》第五版。前置知识是置换和群的基础。引入先举一个例子 : 有四个球，从1到4标号，摆在一个正方形的顶点上。现在要给球染色，每个球有两种染色方式——染成黑色或白色，求本质不同的染色方案数。至于怎么定义本质相同?两种染色方案，经过若干次操作之后，如果能完全重合(颜色，而...

Posted by ShanLunjiaJian's Blog on February 15, 2021

生成函数和多项式学习笔记

毒瘤

注意日期!别人情人节在和girlfriend亲亲，我呢在和generating function亲亲…… 这篇学习笔记不打算从头开始讲什么是GF，只说一些简单的trick。约定 : 我们使用球和盒子的模型来考虑问题，也就是说数列$f$的组合意义被认为是 : 我们现在要往盒子$f$里放一些球然后涂色，$f_n$表示在放$n$个球之后有$f_n$种涂色方案。因为我...

Posted by ShanLunjiaJian's Blog on February 14, 2021

Hello World!

ShanLunjiaJian's new blog!

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

Posted by ShanLunjiaJian's Blog on February 8, 2021

一篇blog

在机房写的奇怪文章

感觉这个写的好奇怪，看起来还是很有征文色彩（反正搬上来了就搬上来了。那天机房被征文了，我就写了3000多字的奇怪东西，结果学校也没摘我的，我就扔到blog上来了（ (实际上是因为天天做题做累了，然后看到爷们投稿，我也跟着划划水) 这个写的非常奇怪，我也不知道是给学校投稿而写还是作为回忆录而写(也许一半一半?)，所以大家凑活看吧。评论区菲克一律删评，不作解释。有一些不太彳亍...

Posted by ShanLunjiaJian's Blog on January 18, 2021

NOIP2020 游记

ShanLunjiaJian的NOIP2020游记

Day -3,-2,-1 草草草体质不好的我之前天天集训累垮了?感冒了在家躺了三天。 Day 0 上午回去上了半天课，下午跟刀，zrz和赵神一起开车到了日照。在车上看了日颓智障题和拓扑排序。大约五点多到了宾馆，一起吃了晚饭之后回房间预习。我就看了之前三天的模拟赛题，看了个《赛道修建》，然后学习了一下左偏树，然后十点半就睡觉了。半夜有点冷，给我冻醒了……然后裹紧被子继续睡了。感觉...

Posted by ShanLunjiaJian's Blog on December 6, 2020

Rank-Pairing Heap学习笔记

一个玄学堆

Rank-Pairing Heap(rp-heap，赋级配对堆)是一种堆。（废话复杂度和Fib堆相同(如果不知道Fib堆什么复杂度，百度，请)。论文里说rp堆更优秀(理由是维护的信息更少)，但wiki说Fib堆更快一些。不过至少我觉得rp-heap要好写得多(论文里好像也这么说了)。毕竟我这种菜鸡都能写出来这里是论文和课件，都是嘤文的。(Tarjan大毒瘤) 还有Etaoi...

Posted by ShanLunjiaJian's Blog on March 21, 2020

苏联笑话精选

/jy

按我们觉得经典的顺序排列。大部分是我自己复述的。 http://www.talkreason.org/marperak/jokes/ 声明 : 文中国家和人物仅作为架空的形象出现，并且不影射任何现实中的人物或事件。拉宾诺维奇到资本主义国家出差，期间他发了一封电报回国 : “我选择了自由”。他的单位立刻组织开会谴责他，会议进行中，突然拉宾诺维奇推开门走了进来，全场一片惊愕。他说道，...

Posted by ShanLunjiaJian's Blog on November 7, 1922