洛谷做題筆記 11。

9.14

模擬賽

幽默。

T1

直接 LCT。

發現圖是仙人掌。

每個環記一個 \(\min,\max\) 就完了。

T2

傻逼

\(\mathcal{O}(\frac{n^4}{w})\) 能過。

注意到 \(\text{dis}(u,v)+\text{dis}(v,w)\ge\text{dis}(u,w)\)，判斷 \(x\) 是否在 \((u,v)\) 知道 \(\sum \text{dis}(u,x)+\text{dis}(v,w)\) 就可以了。

T3

直接兩半分別數位 dp

T4

怎么講過

首先定義一個新的串 \(a\)，其中 \(a_i\) 是 \(s_i\) 這個字符和上一次他出現的位置 \(j\) 滿足 \(s_i=s_j\) 的距離，那如果兩個串最小表示是相等的，當且僅當他們的 \(a\) 相同

可以用主席樹維護出來每一個后綴的 \(a\)，查詢時主席樹上二分，復雜度 \(\mathcal{O}(n\log^2n)\)

CF1474F 1 2 3 4 ...

很套路的題啊。。。

我們發現轉移是形如一些線性相加和前綴和操作，那 dp 數組我們可以用 \(\mathcal{O}(n)\) 段 \(\mathcal{O}(n)\) 次多項式來維護，直接做就好了，復雜度 \(\mathcal{O}(n^4)\)

其實用矩陣也是可以快速維護的，應該更好寫一點

CF1605F PalindORme

如何判定一個序列是合法的，考慮以下流程：

• 找到相等的兩個數
• 把所有數中二進制位與那兩個數有重合的都刪掉
• 刪掉這兩個數，重復如上操作直到序列長度 \(\le 1\)

為啥是對的呢？考慮如果當前有若干對數可以被刪，那我們選任意一對，其他的對肯定在之后是能刪的，所以能刪的就刪不會更劣

正難則反，那么對于任意一個不合法的序列，肯定存在一個極長的合法的子序列，滿足刪去這個合法序列之后剩下的數各不相同且全都非 \(0\)，我們可以根據這一點來容斥

記 \(f_{i,j}\) 表示長為 \(i\)，恰好有 \(j\) 個二進制位的方案，\(g_{i,j}\) 表示長為 \(i\)，恰好有 \(j\) 個二進制位且所有數都不相同的方案，\(h_{i,j}\) 表示長為 \(i\)，恰好有 \(j\) 個二進制位的不合法的方案數

\(f\)、\(g\) 可以容斥得到：

\(h\) 的轉移，考慮枚舉極長的合法子序列的長度：

9.16

模擬賽

T1

bitset。

T2

矩乘。

T3

貪心。

T4

做過。

CF1698G Long Binary String

wow

考慮把給定的串看成一個多項式 \(F(x)\)，我們要求的就是一個最小的 \(k\) 滿足存在一個 \(G\)，使得

我們兩邊同時對 \(F(x)\) 取模，就能得到

而在膜 \(2\) 意義下，有 \(1\equiv -1\)，所以也就是要求

這是一個 BSGS 的形式，那我們首先要估計出 \(k\) 大概多大，考慮膜 \(F(x)\) 的剩余系，肯定有 \(k\le 2^n-1\)，所以這里取 \(B=2^{\frac{n}{2}}\)，在膜 \(2\) 意義下，多項式乘法和多項式取模都是簡單的，可以用位運算輕松 \(\mathcal{O}(n)\)，那總復雜度就是 \(\mathcal{O}(n2^{\frac{n}{2}})\)

CF1920F2 Smooth Sailing (Hard Version)

很自然的套路題

首先定義 \(d_{i,j}\) 為 \((i,j)\) 這個格子離最近的火山有多遠，考慮射線法，我們隨便找一個島上的點往右射一條線，一條回路會被這個射線穿過奇數次，于是可以記一個狀態 \((x,y,0/1)\) 表示走到 \((x,y)\)，經過了這個射線次數的奇偶性，那么最終我們要求的就是從 \((x,y,0)\) 轉移到 \((x,y,1)\) 的最小權值的最大值，直接建出來 kruskal 重構樹即可

CF1713F Lost Array

怎么想到對角線的？

經典結論，\(\binom{n}{m}\equiv [m\subseteq n]\pmod 2\)，考慮把 \(a\) 貢獻到對角線上，再從對角線貢獻到 \(b\)，那就是做子集和再做超集和，我們反過來做一遍就能求得 \(a\) 了！！！

CF1747E List Generation

簡單推式子

容斥，求

交換求和符號

現在只需要計算

我們可以用 \(\binom{k}{i}(k+1)=(i+1)\binom{k+1}{k-i}\) 把 \(k+1\) 提出去，于是就變成求

用 \(k-i\) 替換 \(k\)，得到

設 \(S(i)=\sum\limits_{k=0}^{n+m-i}(-1)^{k}\binom{k+i+1}{k}\)，直接裂項

\(S\) 就可以線性遞推了

9.17

只要我做的幽默題夠多，我的紙面數據就夠強！

CF1882E2 Two Permutations (Hard Version)

這么強？！

我們把這個序列當作一個環，如果再給序列開頭添上一個 \(0\)，那么發現每次操作等價于選擇一個 \(x\)，使其和 \(0\) 所在的位置進行交換！使得最后我們的排列和 \(\left\{0,1,\cdots,n \right\}\) 循環同構

枚舉最后目標的排列是什么，然后對原排列，建一張圖，使得每個位置連向這個位置上元素應該在的位置，現在考慮怎么把這置換環都解開，我們對于每一個置換環分別考慮，記其長度為 \(len\)：

• 如果這個置換環包含 \(0\)，只需要 \(len-1\) 步
• 如果不包含 \(0\)，可以先隨便把這個環上某個位置和 \(x\) 交換，做一遍包含 \(0\) 的過程，再把那個數交換回來，需要 \(len+1\) 步

這樣就做完了，復雜度 \(\mathcal{O}(n^2)\)

#6170. 凸多邊形正則劃分問題

搞笑題。

考慮最后一定是形如一堆 \(k\) 邊形放一塊，我們不妨枚舉第一條邊最后構成的多邊形是什么樣的，顯然他會再連出去 \(k-1\) 條邊把整個多邊形分成 \(k-1\) 部分，如果我們記答案為 \(f_n\)，那么這剩余 \(k-1\) 部分的 \(n\) 的總和為現在的 \(n-1\)，記 \(f_n\) 的生成函數為 \(F(x)\)，有

直接拉反，記 \(G(x)=\frac{x-1}{x^{k-1}}\)，有 \(F\circ G=x\)，則有

廣義二項式定理：

直接算就完了，復雜度 \(\mathcal{O}(n)\)，FJOI 確實奇異搞笑，媽的不給數據組數

#8329. Excuse

我操。。。

記 \(f_n\) 為 \(n\) 的答案，枚舉有多少個數 \(>0\)，把這些數減一之后可以遞歸子問題，有

分治 NTT 即可。

#7932. AND-OR closure

首先把所有數上都是 \(0\) 或者都是 \(1\) 的位置都去了，然后可以把一些等價的位縮到一起，我們可以連一些邊，\(u\rightarrow v\) 有邊，當且僅當 \(u\) 這個位上為 \(1\) 數的集合是 \(v\) 這個位上為 \(1\) 的數的集合的超集，這樣可以構造出來一個 DAG，那么原問題的一個必要條件就是選出來這個 DAG 的一個割，即計數點集 \(V\) 的數量，滿足若 \(u\in V\)，\(v\rightarrow u\)，有 \(v\in V\)，發現他其實也是充分的，我們只需要建出來反向圖就可以證明了

而一個 DAG 割的數量等于其反鏈的數量，因為一個割會有一些沒有后繼的點，這些點構成一個反鏈，所以我們只需要數反鏈的數量，考慮 meet in the middle，我們選出來前 \(\frac{K}{2}\) 個點的反鏈，這樣可以找到后 \(\frac{K}{2}\) 個點中與前 \(\frac{K}{2}\) 個點無偏序關系的點的集合，再枚舉后 \(\frac{K}{2}\) 個點，判斷他們是不是反鏈即可

復雜度 \(\mathcal{O}(nK^2+2^{\frac{K}{2}}K^2)\)，其中 \(K=\log V\)

AT_arc138_c [ARC138C] Rotate and Play Game

好玩啊

嘗試構造一種方案把前 \(\frac{n}{2}\) 大的都取走

如果要能把大的都取走，那取大的之前，必須要有一個不是大的，這是一個格路的形式，那把大的看成 \(-1\)，小的看成 \(1\)，把前綴和最小的地方提到最前面就行了

P9528 [JOISC 2022] 螞蟻與方糖

經典的。

這個東西直接人員調度不是很好做，考慮霍爾定理，即 \(\forall S\subseteq L,|N(S)|\ge|S|\)，這里有一個推論，即最大匹配數等于 \(|L|-\max_{S\subseteq L}\left\{|S|-|N(S)|\right\}\)，這個推論的證明的話，考慮選出來 \(|S|-N(S)\) 最大的那個集合的補，這個集合肯定不存在 \(S>N(S)\) 的子集，要不然他就可以加到那個最大的集合中去，在這道題中，我們肯定是選擇一些區間 \([l_i,r_i]\)，把這個區間中的螞蟻都選中，因為如果存在兩個鄰域有交螞蟻區間 \([l_1,r_1],[l_2,r_2]\)，此時還有一個螞蟻 \(r_1< x<l_2\)，把 \(x\) 選進去肯定更優，形式化一下，我們要求的就是：

那我們可以記錄一下 \(a\)、\(b\) 的前綴和 \(S_1,S_2\)，令 \(p_i={S_2}_{i-L+1}-{S_1}_{i-1}\)，\(q_i={S_1}_{i}-{S_2}_{i+L}\)，問題就轉化為交替選 \(p,q\)，并最大化權值和，直接線段樹維護，用 \(f_{t,0/1,0/1}\) 表示線段樹上 \(t\) 這個節點所代表的區間內最左邊選 \(p/q\)，最右邊選 \(p/q\) 的最大權值

現在考慮修改，如果新加了螞蟻，那么其貢獻是形如一個單點加和一個區間加，單點加好處理，區間加的話，具體而言，就是給 \(p\) 加上 \(x\)，給 \(q\) 減去 \(x\)，其對 \(f_{0,1}\) 和 \(f_{1,0}\) 的貢獻顯然是 \(0\)，而 \(f_{0,0},f_{1,1}\) 的貢獻并不會發生變化，打一個區間加的標記即可

如果新加了方糖，其貢獻是形如一段區間 \(q\) 加和一段區間 \(p\) 加 \(q\) 減，后者好處理，前者的話，發現這個區間的大小 \(<2L\)，所以不用考慮 \(f_{1,0}\) 的貢獻，只需要考慮 \(f_{0,0},f_{1,1},f_{0,1}\) 三者，他們也都最多只包含了一個 \(q\)，所以可以直接計算貢獻

復雜度線性對數

P12294 [THUPC 2025 決賽] 一個 01 串，n 次三目運算符，最后值為 1（加強版

這種把幾個相鄰的數合并成一個數，最后能變成某個狀態的集合，大概是一個正則語言，也就是存在一個確定性有限狀態自動機可以判定一個串是否合法，所以我們可以使用 Myhill–Nerode 定理

Myhill–Nerode 定理：
對于一個語言 \(L\)（字符集 \(\Sigma\) 上的一個字符串集合），對于兩個串 \(x,y\in\Sigma^{*}\)，如果對于任意 \(z\in L\)，有 \(xz\in L\Leftrightarrow yz\in L\)，那么稱 \(x,y\) 關于 \(L\) 等價，記作 \(x\equiv_{L} y\)

因為條件比較簡單，所以我們只需要對于長度很短的 \(01\) 串（試驗得到閾值為 \(9\) ）劃分等價類，判定兩個串 \(x,y\) 是否等價，只需要枚舉一個長度（試驗得到長度為 \(6\)）的 \(01\) 串 \(z\)，判斷 \(xz\) 和 \(yz\) 是不是能合并出我們想要的串，如果都能或者都不能，那么他們是等價的

我們可以輕松對于一個目標狀態 \(q\) 建出來自動機，并可以 \(\mathcal{O}(n)\) 判斷一個長度為 \(n\) 的串是不是能變成目標狀態 \(q\)，對于給定的串，我們可以通過一些數據結構來判斷一個區間的子串是不是能變成 \(q\)，可以通過貓樹在 \(\mathcal{O}(n|Q|\log n)-\mathcal{O}(1)\) 的復雜度完成預處理和查詢，為了節省內存也可以使用線段樹做到 \(\mathcal{O}(n|Q|)-\mathcal{O}(1)\)

構造方案，考慮分治 \(\text{solve}(l,r,t)\) 表示 \([l,r]\) 的子串是不是能變成 \(t\)，最終我們要調用 \(\text{solve}(1,n,1)\)，考慮啟發式分裂，我們維護兩個指針 \(i,j\)，\(i\) 從左往右掃，\(j\) 從右往左掃，枚舉 \(i=mid\) / \(j=mid\)，對于 \(1\) 或者 \(0\) 的判定，我們需要把他分解成一個長度為 \(2\) 和一個長度為 \(1\) 的，長度為 \(2\) 的可以再遞歸直接分成兩個長度為 \(1\) 的，所以 \(t\in\left\{0,1,00,01,10,11\right\}\)，我們需要建出來六個自動機來支持區間查詢，啟發式分裂指針的移動量是 \(\mathcal{O}(n\log n)\) 的，最后總復雜度可以做到 \(\mathcal{O}(n|Q|\log n+n\log n)\) 或者 \(\mathcal{O}(n|Q|+n\log^2n)\)

P10436 [JOIST 2024] 卡牌收集 / Card Collection

為這個題做了上面那個題QAQ。

首先我們發現，對于目標數對 \((x,y)\)，每一個 \((a_i,b_i)\) 只有 \(a_i\) 與 \(x\) 的大小關系還有 \(b_i\) 與 \(y\) 的大小關系是重要的，也就是我們令新的 \(a'_i=[a_i>x]+[a_i=x]-1\)，令 \(b'_i=[b_i>y]+[b_i=y]-1\)，然后考慮構造 DFA，此時字符集的大小為 \(8\)，參考一下上一題，我們依舊考慮找到那兩個長度，而在這題中分別是 \(4\) 和 \(3\)，同時有 \(|Q|=24\)，這樣我們每次直接在 DFA 上走就能得到一個 \(\mathcal{O}(nq)\) 的做法

建出來 DFA 后觀察一下，發現這個 DFA 忽略掉自環后是一個 DAG，而且這個 DAG 最長鏈只有 \(8\)，這啟發我們考慮那些不走自環的轉移，于是每次就相當于一個 \(2-\text{side}\) 矩形查詢最小值，即在一個形如 \(a_i<x,b_i<y\) 中查詢 \(i\) 的 \(\min\)

于是可以直接對于 \(a\) 掃描線，同時用一顆線段樹維護區間 \(\min\)，每次線段樹二分找到我們想要的位置，復雜度 \(\mathcal{O}(n|P||\Sigma|\log n)\)，其中 \(|P|\) 是 DAG 上最長鏈的長度，\(|\Sigma|\) 是字符集大小

AT_arc128_c [ARC128C] Max Dot

考慮差分。

記 \(B_i=\sum_{j\ge i}a_j\) 如果我們給差分數組上 \(i\) 的位置加上 \(x\)，那么得分就會增加 \(xB_i\)，而總和會增加 \((n-i+1)x\)，于是就相當于以總和加上 \(x\) 的代價給得分加上 \(x\frac{B_i}{n-i+1}\)，那肯定是選擇 \(\frac{B_i}{n-i+1}\) 最大的那個一直加直到加不動，而我們又有 \(x_i\le M\) 的限制，所以策略就是每次選擇最大的 \(\frac{B_i}{n-i+1}\)，如果當前剩下的 \(S\) 還夠用，就直接把這些 \(S\) 都加過去，否則把 \([i,n]\) 全都變成 \(M\)，并刪掉這些后綴，所以 \(x\) 序列在最優情況下一定是三段，最前面的一段全 \(0\)，中間的一段全是一個 \(<M\) 的數，最后一段全 \(M\)，直接 \(\mathcal{O}(n^2)\) 枚舉斷點即可

CF1310D Tourism

問號。

隨機化。

我們給每個點隨機黑白染色！然后直接 \(\mathcal{O}(n^2k)\) dp！隨機 \(5000\) 次就是對的！

對于最后的最優解，如果這條路徑長度為 \(k\)，那么染色合法的概率就是 \(\frac{1}{2^{k-1}}\)，當 \(k=10\) 的時候有 \(\frac{1}{2^{k-1}}=\frac{1}{512}\)，而找不到合法解的概率就是 \(\left(\frac{511}{512}\right)^{5000}\approx 5\times 10^{-5}\)。

9.18

?

9.19

?

#7837. 挑戰積和式

天才！

假如我們當前已經選了 \(\sum a_{b_i}=A\)，\(\prod b_i=B\)，那么考慮調整，將其中一個 \(b_i\) 變成 \(1\)，則權值變成了 \(A-a_{b_i}+a_1-\frac{B}{b_i}\)，如果這樣調整不優當且僅當 \(\frac{(a_{b_i}-a_1)(b_i-1)}{b_i}>B\)，所以可以得到 \(B\le 2V\)

由此我們可以得到一個 \(\mathcal{O}(V\log^2 V)\) 的做法，直接 dp，記 \(f_{i,j}\) 表示選了 \(i\) 個，乘積為 \(j\) 的最大和

考慮優化，能不能把乘積分成兩半再拼起來

引理：對于任意有限集 \(S\subset [0,\frac{2}{3}]\)，滿足 \(\sum_{x\in S}\le 1\)，一定存在一個 \(T\subseteq S\)，滿足 \(\frac{1}{3}\le\sum_{x\in S}\le \frac{2}{3}\)

證明：

• 若 \(\max\left(S\right)\ge \frac{1}{3}\)，可以取 \(T=\left\{\max\left(S\right)\right\}\)
• 否則將 \(S\) 從小到大排序，取 \(T\) 為 \(S\) 的偶數位置上的數字構成的集合，此時有 \(\sum_{x\in T}\ge \frac{1}{2}\)，考慮 \(\max\left(S\right)\) 則有 \(\sum_{x\in T}\le\frac{1}{2}(1+\max\left(S\right))\le \frac{2}{3}\)

于是值域只需要保留到 \(V^{\frac{2}{3}}\)，最后合并兩個 dp 數組可以直接用 凸包做到線性，每個數選的個數可以直接快速冪，轉移是調和級數的

復雜度 \(\mathcal{O}(V^{\frac{2}{3}}\log V\log{\min\left\{k,\log V\right\}})\)

9.20

初賽。

9.21

初賽。

9.22

#7872. 崩壞天際線

不會高級做法，，，

先考慮一個其中一個區間，我們每次插入一個崩壞的位置，其貢獻是什么？如果他左邊第一個崩壞的位置是 \(l\) 和右邊第一個崩壞的位置是 \(r\)，那么貢獻就是 \(-\frac{1}{2}(r-l)\)，因此我們可以直接離線，做兩邊單調棧做到 \(\mathcal{O}(q^2)\)

接著考慮所有 \(2\) 操作都在 \(1\) 操作之后，我們發現這時候所有的區間會有一些段是相同的，而區別只在于兩端 \(\mathcal{O}(q)\) 個區間，于是我們可以把每個端點左邊和右邊的區間都維護出來，這樣最多只會維護 \(\mathcal{O}(q)\) 個，具體的，我們可以找到每個區間第一次崩壞的位置，可以直接 rmq，記這個位置為 \(x\)，然后把 \(l\) 掛在 \(x\) 左邊，\(r\) 掛在 \(x\) 右邊

然后考慮插入一個新的 \(x\)，記其左邊的崩壞點為 \(L\)，右邊的為 \(R\)，在這里我們先只考慮 \(L\) 所維護信息的變化，對于 \(L\) 中右端點大于 \(x\) 的區間，\([L,R']\)，他會被分成 \([L,x]\) 和 \([x,R']\)，端點都是崩壞的點的區間的信息是好維護的，我們只需要繼承下來，\(L\) 中那些斷開的區間的信息，即 \([L,R']\rightarrow [x,R']\)，可以直接線段樹分裂，區間維護乘法標記，單點插入

套路的，考慮對詢問分塊，塊長為 \(B\)，對于塊內的操作我們直接暴力操作是 \(\mathcal{O}(B^2)\) 的，而最后在插入到線段樹中復雜度是 \(\mathcal{O}(\frac{q}{B}B^2\log q)=\mathcal{O}(qB\log q)\)，塊內的操作對于塊前的影響的復雜度則是 \(\mathcal{O}(q\frac{q}{B}\log q)\)，可以平衡得到總復雜度為 \(\mathcal{O}(q\sqrt q\log q)\)，可以通過

如果從笛卡爾樹的角度考慮則可以得到一個 \(\mathcal{O}(q\sqrt q)\) 的做法，不過有 \(\mathcal{O}(q\log^2q)\) 的做法，但是網上的題解都沒怎么說

#7976. 最后的晚餐

這么強？！

為了方便，記 \(F(c)=f(S)-1\)，其中 \(c_i\) 為 \(i\) 的出現次數，可以發現有一個答案上界是 \(\left\lfloor\frac{sum(S)}{10}\right\rfloor\)，當 \(a_i<11\) 的時候，這個上界一定可以被取到，如果有 \(a_i=11\) 怎么辦？這時候只有某個時刻前綴和為 \(9\) 的時候會寄掉，先隨便搞出來一個貪心算法：

1. 如果前綴和不是 \(9\)，直接放一個 \(11\)
2. 否則放一個不是 \(11\) 的數

如果這個算法最后還剩了一些 \(11\)，那么每一個時刻肯定都可以進位！這樣我們能取到另一個上界 \(F(c)=n\)，所以這個時刻總能構造出來一個方案使得 \(F(c)=\min\left\{\left\lfloor\frac{sum(S)}{10}\right\rfloor,n\right\}\)，可以簡單 \(\mathcal{O}(n^2)\) 計數

如果多出來一些 \(12\)，這時候我們考慮如果集合形如 \(\left\{1,12,12,12,12,12\right\}\) 不能卡到上界 \(n\)，所以我們需要尋找一個更緊的上界

如果只有偶數和 \(1\)，此時每個 \(1\) 都需要兩兩配對，則上界為 \(n-\left\lceil\frac{c_1}{2}\right\rceil\)，如果 \(1\) 能進位當且僅當前綴和為 \(9\)，只有奇數能改變前綴和奇偶性，于是可以把 \(1\) 和其他的奇數兩兩配對，使得只有 \(\max(c_1-(c_3+c_5+c_7+c_9+c_{11}),0)\) 個 \(1\) 無法進位，而這些 \(1\) 必須互相兩兩配對

于是可以考慮如下策略：

如果前綴和個位 \(< 8\)，直接填 \(12\)，如果 \(12\) 用完了，可以直接用先前的算法

如果前綴和個位為 \(8\)：

• 任選一個 \([2,10]\) 內的偶數
• 否則選 \(11\)
• 否則選一個 \(>1\) 的奇數
• 否則填 \(1\)

若前綴和為 \(9\)：

• 填 \(1\)
• 否則任選一個 \([3,9]\) 的奇數
• 否則填 \(11\)

這個算法只有在只剩偶數和 \(1\) 的時候會有 \(F(c)<\min(sum(S),n)\)，如果只剩 \(1\) 和偶數，可以直接構造到 \(n-\left\lceil\frac{\max(c_1-(c_3+c_5+c_7+c_9+c_{11}),0)}{2}\right\rceil\) 的上界，于是有：

剩下的就是計數了，記 \(f(n,m)\) 為大小為 \(n\)，和為 \(m\)，僅包含偶數的集合個數，\(g(n,m)\) 為大小為 \(n\)，和為 \(m\)，僅包含 \(>1\) 的奇數的集合個數，\(f\) 和 \(g\) 可以直接 dp 得到，最終答案為

其中 \(d_1\) 為枚舉 \(1\) 的個數

先考慮 \(1\) 和 \(g\) 的轉移，記一個 \(h(n,m)\)，則有轉移：

可以前綴和優化，再考慮 \(f\) 和 \(h\) 的轉移，有答案等于

這時候的轉移對于 \((\left\lfloor\frac{m}{10}\right\rfloor-n,m\bmod 10)\) 的項都是類似的，于是總復雜度 \(\mathcal{O}(n^2)\)

9.23

模擬賽

T1

搞笑。

T2

有點意思，但不多。

T3

鬧麻了

T4

艚膩嘛

P13844 集合冪級數 ln（非素數模數）

我是集級領域大師！

\frac{\partial}{\partial x_n}G=\frac{1}{F}\frac{\partial}{\partial x_n}F

[x_n^{1}]G=[x_n0]\frac{1}{F}[x_{n}^1]F

\frac{\partial}{\partial x_n}H=-\frac{1}{F^2}\frac{\partial}{\partial x_n}F=-H^2\frac{\partial}{\partial x_n}F

[x_n^{1]H=-\left([x_n}0]H\right)^2[x_n1]F

G=e^{F}

\frac{\partial}{\partial x_n}G=e^F\frac{\partial}{\partial x_n}F=G\frac{\partial}{\partial x_n}F

[x_n^1]G=[x_n0]G[x_n^1]F

P(L_{\min}\ge x)=(1-nx)^{n-1}

E(L_{\min})=\int_{0}^{\frac{1}{n}}P(L_{\min}\ge x)\mathrmw0obha2h00x=\frac{1}{n^2}

\frac{1-nE(L_{\min})}{(n-1)^1}+E(L_{\min})=\frac{1}{n}\left(\frac{1}{n}+\frac{1}{n-1}\right)

E(L_{k})=\frac{1}{n}\sum_{i=1}^{k}\frac{1}{n-i+1}

\begin{aligned}
Ans& =\frac{1}{3}\sum_{k=1}^{{n}\left(\frac{1}{3}{k-1}}-\frac{1}{3^k}\right)E(L_k)\
&=\frac{1}{3n}\sum_{k=1}^{n\left(\frac{1}{3}{k-1}}-\frac{1}{3^{k}\right)\sum_{i=1}}\frac{1}{n-i+1}\
&=\frac{1}{3n}\sum_{i=1}^{{n}\frac{1}{n-i+1}\sum_{k=i}}\left(\frac{1}{3^{{k-1}}-\frac{1}{3}k}\right)\
&=\frac{1}{n}\sum_{i=1}^{{n}\frac{1}{3}i(n-i+1)}\
\end{aligned}

Ans=\sum_{E}(-1)^{{|E|}\prod_{i=1}}\left\lfloor\frac{m}{\text{lcm}(s_i)}\right\rfloor

Ans=\sum_{s_1,s_2,\cdots,s_k}\prod_{i=1}^{k}\left\lfloor\frac{m}{\text{lcm}(s_i)}\right\rfloor\sum_{E}\lambda(E)

g(n)=\sum_{i=0}^{{\frac{n(n-1)}{2}}(-1)}\binom{\frac{n(n-1)}{2}}{i}=[n=1]

f(n)=g(n)-\sum_{i=1}^{n-1}\binom{n-1}{i-1}f(i)g(n-i)=[n-1]-(n-1)f(n-1)

\begin{aligned}
E(\varphi(A_{n+1})-\varphi(A_{n})|A_{n})&=1\
\sum E(f(a_{n+1,i})|A_n)-E(f(a_{n,i})|A_n)&=1\
\sum E(f(a_{n+1,i})|A_n))-f(a_{n,i})&=1\
\sum \frac{a_{n,i}}{S}f(a_{n,i}-1)+(1-\frac{a_{n,i}}{S})\frac{1}{n-1}f(a_{n,i}+1)+(1-\frac{a_{n,i}}{S})(1-\frac{1}{n-1})f(a_{n,i})-f(a_{n,i})&=1\
\sum \frac{a_{n,i}}{S}f(a_{n,i}-1)+(1-\frac{a_{n,i}}{S})\frac{1}{n-1}f(a_{n,i}+1)-\left(\frac{a_{n,i}}{S}+\frac{1}{n-1}-\frac{a_{n,i}}{S(n-1)})f(a_{n,i}\right)&=1\
\end{aligned}

\frac{a_{n,i}}{S}f(a_{n,i}-1)+(1-\frac{a_{n,i}}{S})\frac{1}{n-1}f(a_{n,i}+1)-\left(\frac{a_{n,i}}{S}+\frac{1}{n-1}-\frac{a_{n,i}}{S(n-1)})f(a_{n,i}\right)=\frac{a_{n,i}}{S}

f(x+1)=(\frac{x(n-1)}{S-x}+1)f(x)+\frac{x(n-1)}{S-x}(1-f(x-1))

f(x+1)-f(x)=(f(x)-f(x-1)+1)g(x)

E(T)=\varphi(A_T)-\varphi(A_0)

f_i=\sum_{j}(-1)^{j-i}\binom{a}{j}\binom{i+1}{j-i}

f_i=[x^{{a-i}]\sum_{k=i}}\binom{a}{k}x^{{a-k}\binom{i+1}{k-i}(-x)}

f_i=x^{a-i}^a(1-x)

G_k'=G_k\left(\frac{a}{1+x}-\frac{k}{1-x}\right)

(1-x^2)G_k'(x)=a(1-x)G_k(x)-k(1+x)G_k(x)