ShanLunjiaJian's Blog

Welcome to My Blog!

好耶

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

Posted by ShanLunjiaJian's Blog on February 8, 2021

用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

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

Posted by ShanLunjiaJian's Blog on March 2, 2022

fib数列

/dk

Posted by ShanLunjiaJian's Blog on February 23, 2022

acm/icpc题选做

/kk

很久之前就想开这个坑了（计划写hdu多校，ptz营，以及open cup。这三个感觉上难度是递增的吗（区域赛啥的先咕了，太多了不知道先做哪些（很多是胡的，不保证正确性，仅供参考。欢迎您来交流讨论，可以在评论区给我留言/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

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

实际上是一些trick

呃。树上动态斯坦纳树边权和对于一个点集，按dfn排序，相邻dis之和(转一圈)就是斯坦纳树边权和的两倍。可以用set维护，更牛逼的方法是veb。操作独立删少量边动态图连通性大概是说每次删一个集合，集合大小不超过\(15\)，然后求是不是连通，查询独立。如果dfs树上一条树边被删了，并且所有跨过它的非树边也删了，那就完蛋了。 xor hash。每条非树边分配一...

Posted by ShanLunjiaJian's Blog on November 16, 2021

子集反演

奇怪

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

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

AGC选㗅

fuck

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

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

集合幂级数

草?

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

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

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

CF再选做

定个小目标，今年上Newbie

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

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

Hello World!

ShanLunjiaJian's new blog!

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