Claimo0611

摘要： 關(guān)于polya和burnside。 閱讀全文

摘要： 關(guān)于 K-D Tree。 閱讀全文

摘要： 可持久化平衡樹 復(fù)習(xí)了一下fhq。 普通可持久化平衡樹 和主席樹類似地，可持久化數(shù)據(jù)結(jié)構(gòu)的精髓在于對(duì)每次進(jìn)行次數(shù)為 \(log\) 級(jí)別的操作進(jìn)行重開點(diǎn)，以此用盡可能小的時(shí)空損耗來保存每次操作完的全樹狀態(tài)。國內(nèi)常用的可持久化平衡樹是fhq，容易想到地，就是將它的split和merge操作進(jìn)行可持久化 閱讀全文

摘要： 前一半家桶 常年做數(shù)據(jù)結(jié)構(gòu)的人都目光呆滯，極度自卑，后面忘了。 線段樹分裂 就是裂開，咋合的就咋裂開,進(jìn)而和線段樹合并類似地，這個(gè)東西用于權(quán)值線段樹的操作。然后線段樹合并和線段樹分裂一般同時(shí)出現(xiàn)，空間炸炸的，這個(gè)時(shí)候就要寫垃圾桶，就是把沒用的節(jié)點(diǎn)編號(hào)扔到一個(gè)棧里頭。 板 inline int mer 閱讀全文

摘要： 如果答案能表示為一個(gè) \(K\) 次多項(xiàng)式的形式可以考慮插值求解，\(O(k^2)\)。 比如求 \(\sum_{i=1}^ni^k\)，可以表示為一個(gè) \(k+1\) 次多項(xiàng)式 \(f(n)\)，事實(shí)上次數(shù)開高是沒影響的（插值出來系數(shù)為0）但是不能插低。 一個(gè)人的數(shù)論 毒瘤。 \[f_k(n)=\ 閱讀全文

摘要： 根據(jù)狄什么卷積，對(duì)于數(shù)論函數(shù) \(f,g\) 有 \[(f\ast g)(n)=\sum_{d|n}g(n)f(\frac{n}w0obha2h00) \]進(jìn)一步地，有 \[\sum_{i=1}^n(f\ast g)(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}w0obha2h00) \]\[ 閱讀全文

摘要： 整除分塊和狄利克雷卷積沒啥說的。 規(guī)定莫比烏斯函數(shù) \(\mu(i)\) 滿足 \(i\) 被表示為 \(x\) 個(gè)單個(gè)質(zhì)因子的積時(shí)返回值為 \((-1)^x\)。其余時(shí)為 \(0\)，\(\mu(1)=1\)。 有重要性質(zhì) \[\sum_{d|n}\mu(d)=[n=1] \]證明：不妨設(shè) \[n 閱讀全文

摘要： 后綴數(shù)組 板題 后綴數(shù)組可以把字符串的所有后綴存起來，然后干各種奇怪的事情。 現(xiàn)在給你一個(gè)字符串 banana，給他的后綴A,NA,ANA,NANA,ANANA,BANANA 跑一個(gè)后綴的trie。 然后把字典序小的字母排在左邊，給每個(gè)后綴對(duì)應(yīng)的葉節(jié)點(diǎn)標(biāo)一下這個(gè)后綴首字母在文本串的位置。 從左到右連 閱讀全文

摘要： 模擬賽和平時(shí)做題時(shí)不時(shí)有一些沒見過的東西，寫一下。 斯特林?jǐn)?shù) 講遞推和初步性質(zhì)。退役前可能學(xué)不到多項(xiàng)式。 第一類斯特林?jǐn)?shù)：$s(n,m) $把 \(n\) 個(gè)元素分成 \(m\) 組圓排列的方案，圓排列是 \((n-1)!\)。 從 dp 意義上推遞推公式，設(shè) \(s(i,j)=dp_{i,j}\) 閱讀全文

摘要： 傳奇水題板塊，我有一萬道紫黑都是做網(wǎng)絡(luò)流，常年做網(wǎng)絡(luò)流的人都目光呆滯極度自卑智商逐年下降最后完全成為傻子后面忘了。 算法難度-1分，思維難度比較高，至少在2024.6.12還沒法靠自己做出來題。 6.14：這個(gè)東西當(dāng)作dp做可能會(huì)比較好想，連邊操作就是在跑大概的轉(zhuǎn)移方程，網(wǎng)絡(luò)流就是自動(dòng)從轉(zhuǎn)移方程里找 閱讀全文