做題筆記17

9.30

歌：WAIT FOR DAWN (feat. 棗いつき)

之前打的時候覺得這個一般，現在再聽覺得攙冰了

模擬賽

完蛋了今天就做了 2 個題，算幽默模擬賽可能就 6 個題了，感覺這輩子做題量都不可能趕上遼沈了

T1

何意味。

T2

線段樹優化 dp。

T3

分解質因數。

T4

FWT。

#7980. 區間切割

我佛

把一個區間分成三段，每段都是原長的 \(\frac{1}{3}\)，發現如果修改的位置落在第一段或第三段，永遠都是去掉一段前/后綴，如果落在第二段，這時候線段的長度至少會減少 \(\frac{1}{3}\)，每一個區間的有用操作只有 \(\mathcal{O}(\log)\) 次

那么可以線段樹求出第一個落在中間一段的操作，然后左右兩段線段樹二分一下就完了，，，

首先答案為 \(\sum 2^{\min(maxdep_{ls},maxdep_{rs})}-(n-1)+\sum a_i\times dep_i\)，前后兩部分的代價顯然是相對獨立的，我們先考慮第二部分，也就是說先去確定一組 \(dep\) 和 \(a\)，如果 \(dep\) 確定了，那肯定是大的 \(dep\) 和小的 \(a\) 配對，也就是說，對于一組合法的 \(dep\) 數組，其 \(\sum a_i\times dep_i\) 的代價是固定的，那么前者的貢獻之和樹的形態有關，考慮如何 dp

我們從下往上考慮，假如當前正在考慮 \(dep=d\) 的點，將這些點按照 \(maxdep\) 排序，我們可以發現，最后肯定是 \(d_1\) 和 \(d_2\) 合并，為啥呢，如果這倆不合并，最后會傳上去一個 \(h_1\)，在最終的貢獻里至少會變成 \(2^{h_1+1}\)，所以肯定劣完了，那么這一層最后一定是全都合并完了再向上傳遞

同時我們可以把 \(dep_i\times a_i\) 拆了，變成一些 \(s_i=\sum_{j\le i}a_j\) 的相加，這樣方便我們 dp

記狀態 \(f_{i,j}\) 表示考慮了前 \(i\) 個點，當前層有 \(j\) 個點，那么有兩種轉移：

新加一個葉子：\(f_{i-1,j}\rightarrow f_{i,j+1}+\text{lowbit}(j)\)
把當前層合并到上一層：\(f_{i-1,2j}\rightarrow f_{i,j}+s_{i}\)

復雜度 \(\mathcal{O}(n^2)\)

#2064. Bitset Master

我操這不是我們模擬賽的題嗎，怎么被呂神扔到好題里了，下次記得表明出處

還是說一下吧，點分治，對于每一個點，詢問所有跨過分支中心的答案，求出 \(u\) 第一次合并到根的時刻，再求出根到 \(u\) 的時刻，然后做一個二位數點即可

10.1

今天還是擺完了。

歌：キラーチューン

其實不是今天的歌，但是差不多啦

模擬賽

T1

記 \(pre_i=\max_{j\le i}v_j,suf_i=\min_{j\ge i}v_j\) 把點掛到二維平面上，每個點控制到的地方就是 \(\le i\) 中 \(v_j>suf_i\) 的部分和 \(\ge i\) 中 \(v_j<pre_i\) 的部分，考慮 dp，從 \(j\) 轉移到 \(i\) 時，\((j,i)\) 中 \(v\) 在 \(pre_{j}\) 和 \(suf_i\) 之間的點是覆蓋不到的，那 \(j\) 可以雙指針到，直接前綴和就行，復雜度線性對數，瓶頸在于排序

T2

幽默。

T3

不會。

T4

哦。

最后肯定是 A 走到一個位置 B 再去追他，如果 A、B 之間只隔了一條邊，設狀態是 \((u,v)\)，那么接下來 A 走到 \(w\)，B 可以直接跟上去，狀態變成 \((w,u)\)，如果接下來 A 返回 \(u\)，B 可以先等待，然后走到和 A 重合，然后 A 走到 \(w\)，B 跟上，A 再走回 \(u\)，這樣花費四步將狀態變成 \((u,w)\)

然后建圖跑最短路。

P4495 [HAOI2018] 奇怪的背包

如果加入 \(V_i\)，\(\gcd(V_i,P)\) 的倍數都可以取到，所以可以令 \(V_i=\gcd(V_i,P)\)，若加入了 \(V_i,V_j\)，所有的 \(\gcd(V_i,V_j)\) 的倍數都可以取到，所以我們可以取出來所有 \(P\) 的因子，考慮一個 dp，記 \(f_{i,j}\) 為考慮了前 \(i\) 個因子，目前 \(\gcd\) 為第 \(j\) 個因子的方案數，直接轉移是簡單的，詢問的話預處理一下就行了，復雜度 \(\mathcal{O}(\sqrt P+q+\tau(P)^2\log P)\)

AT_arc184_d [ARC184D] Erase Balls 2D

哦。

直接 dp 選了哪些點顯然會重，考慮 dp 出 “再多選一個點就會至少刪除一個點” 的選點集合，這樣和留下的點的集合顯然是雙射

如何 check 一個選點方案合法？對于每一對選的點 \((x_i,y_i),(x_{i+1},y_{i+1})\)，把 \(x\) 坐標在 \((x_i,x_{i+1})\)，\(y\) 坐標在 \((y_i,y_{i+1})\) 這個矩形內的點都拎出來，如果他們互相滿足這個限制，那這個選點方案就是合法的，于是可以 \(\mathcal{O}(n^2)\) 枚舉，\(\mathcal{O}(n)\) check，總復雜度 \(\mathcal{O}(n^3)\)

AT_agc035_e [AGC035E] Develop

我們把 \(x\) 給 \(x+K\) 和 \(x-2\) 各連一條有向邊，那我們最終的限制就變成了選出來的點無環，因為有 \(x-2\) 的邊，我們就可以考慮把點按奇偶性分類

如果 \(K\) 是偶數，此時只有奇偶性相同的點會連邊，我們把這些點放到一條鏈上，會形成環當且僅當連續選擇了 \(\frac{K}{2}\) 個點，直接 dp，記 \(f_{i,j}\) 表示考慮了前 \(i\) 個點，已經連續選了 \(j\) 個的方案，轉移是平凡的

如果 \(K\) 是奇數，此時奇數和偶數會各有出邊入邊，為了方便考慮，我們把奇數向偶數的連邊對齊，那大概是一個這樣的圖

   1<-3<-5<-7<-9
   v  v  v  v 
2<-4<-6<-8<-10

這是 \(n=10,K=3\) 的情況，省略了偶數向奇數的連邊

發現每一個環長度都是 \(K+2\)，而且每一個環都恰有一個偶數到奇數的邊和一個奇數到偶數邊，那么我們保留奇數邊，要求最長鏈長度 \(<K+2\)，這樣就不會有環了，我們從左往右依此考慮當前層加入奇數或者加入偶數的點，于是可以 dp，記 \(f_{i,j,k}\) 為考慮了前 \(i\) 個數，奇數為起點的最長鏈長度為 \(j\)，偶數為起點的最長鏈長度為 \(k\)，那么有轉移：

\(f_{i-1,j,k}\rightarrow f_{i,0,0}\)，奇數和偶數都不選
當 \(2i\ge K+1\) 時，有 \(f_{i-1,j,k}\rightarrow f_{i,j+1,0},f_{i-1,0,k}\rightarrow f_{i,0,0}\)，奇數選但偶數不選
當 \(2i\le n\) 時，有 \(f_{i-1,j,k}\rightarrow f_{i,0,k+1}\)，奇數不選但偶數選
當 \(K+1\le 2i\le n\) 時，有 \(f_{i-1,j,k}\rightarrow f_{i,\max(j+1,k+2),k+1}\)，奇數偶數都選

視 \(n,K\) 同階，總復雜度 \(\mathcal{O}(n^3)\)

AT_agc070_c [AGC070C] No Streak

哇襖?。?！

把題目轉化為，走 \(A\) 步向右，\(B\) 步向上，\(N\) 步停留，不能連續走兩步向右或者向上，且不能經過 \(y=x+1\) 這條線的格路計數，我們考慮反射容斥，先把不能經過 \(y=x+1\) 這個限制容了，于是可以記 \(f(a,b,n)\) 為不限制走到 \(y=x+1\) 的方案，那么有 \(Ans=f(a,b,n)-f(a+1,b-1,n)\)

嗎？我們發現會出問題，因為經過 \(y=x+1\) 的格路再翻折之前可能經過了兩次連著向上，在翻折之后就變成向上再向右，這顯然不是雙射

我們再回到反射容斥這個過程，我們的目標是找到 \((0,0)\rightarrow (a+1,b-1)\) 到 \((0,0)\rightarrow (a,b)\) 的雙射，考慮怎么修補一下我們的做法

考察一下翻折之后路徑的形態，這里有兩種情況：

與 \(y=x+1\) 相交之后直接右轉
與 \(y=x+1\) 相交之后停留一步，隨后隨便走

那翻折之前他們都對應什么呢？

與 \(y=x+1\) 相交之后直接向上走，這一部分的貢獻就是 \(f(a+1-1,b-1,n)\)，也就是我們欽定了一步向上走，其余的隨便
與 \(y=x+1\) 相交之后停一步，這一部分的貢獻就是 \(f(a+1,b-1,n-1)\)，也就是欽定了這一步停留，其余的隨便
發現我們少算了上->停留->上，那再減掉這部分即可，也就是 \(f(a+1-1,b-1,n-1)\)

那么有

\[Ans=f(a,b,n)-f(a,b-1,n)-f(a+1,b-1,n-1)-f(a,b-1,n-1) \]

如何算 \(f(a,b,n)\)？考慮寫出其遞推式，具體的，我們考慮路徑最開頭走了什么

停留：\(f(a,b,n-1)\)
上->停留：\(f(a-1,b,n-1)\)
右->停留：\(f(a,b-1,n-1)\)
上->右&右->上：稍微有點復雜，不過他們加起來顯然就是 \(f(a-1,b-1,n-1)+f(a-1,b-1,n)\)

于是有遞推式：

\[\begin{aligned}&f(a,b,n)\\=&f(a,b,n-1)+f(a-1,b,n-1)+f(a,b-1,n-1)+f(a-1,b-1,n-1)+f(a-1,b-1,n)\end{aligned} \]

可以寫出來生成函數：

\[\begin{aligned} F&=(z+xz+yz+xyz+xy)F+(1+x+y+xy)\\ F&=\frac{1+x+y+xy}{1-xy-z(1+x+y+xy)} \end{aligned} \]

這個式子非常好看啊！先求 \(z^n\) 處的系數，有

\[\begin{aligned} \left[z^n\right]F&=\left[z^n\right]\frac{\frac{1+x+y+xy}{1-xy}}{1-\frac{1+x+y+xy}{1-xy}z}\\ &=\left(\frac{1+x+y+xy}{1-xy}\right)^{n+1}\\ \end{aligned} \]

括號里面的不好求，考慮分子分母分別求了再卷積，有

\[[x^ay^b]\left(1+x+y+xy\right)^{n+1}=[x^ay^b](1+x)^{n+1}(1+y)^{n+1}=\binom{n+1}{a}\binom{n+1} \]

\[[x^ay^b](1-xy)^{-(n+1)}=[a=b]\binom{n+a}{a} \]

那答案就是

\[\sum_{i=0}^{\min(a,b)}\binom{n+i}{i}\binom{n+1}{a-i}\binom{n+1}{b-i} \]

總復雜度線性

P6800 【模板】Chirp Z-Transform

幽默陳睿變換。

\[P(c^i)=\sum_{j=0}^{n-1}a_jc^{ij}=\sum_{j=0}^{n-1}a_jc^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}=c^{-\binom{i}{2}}\sum_{j=0}^{n-1}a_jc^{-\binom{j}{2}}c^{\binom{i+j}{2}} \]

卷積即可。

10.2

AT_arc180_f [ARC180F] Yet Another Expected Value

哦哦，哦哦哦哦。

找個組合意義，我們注意 \(j\ge i+1\) 這個東西，可以往樹上考慮，我們去設一個啞元 \(y\)，把原式寫成

\[\prod_{i=1}^{N}\left(y^A+\sum_{j>i}x_j^A\right) \]

如果我們把后面那個和式拆開，就有一個很好的組合意義了，就是說，每個點 \(i\) 可以向 \(0\sim i-1\) 連邊，如果向 \(1\sim i-1\) 連邊，貢獻為 \(x_i^A\)，否則就看成向 \(0\) 號點，也就是根連邊，權值是 \(y^A\)，我們不妨欽定 \(x_i<x_{i+1}\)，最后答案再乘上 \(n!\) 即可，那么我們要算的就是所有樹的權值和，每個樹的權值是其所有邊權值的乘積

我們把上面那個東西記作 \(a_{n}(y)\)，寫出其生成函數 \(F(y,x)=\sum_{i\ge 0}a_i(y)x^i\)，然后可以開推了，枚舉連 \(k\) 個子樹，子樹間無序，則有

\[\begin{aligned} F(y,x)&=\sum_{k\ge 0}\frac{y^{Ak}\left(\int_{0}^{y}F(t,x)\mathrmw0obha2h00t\right)^{k}}{k!}x^{k}\\ &=\exp\left(y^Ax\int_{0}^{y}F(t,x)\mathrmw0obha2h00t\right) \end{aligned} \]

取 \(x^n\) 處的系數，有

\[\begin{aligned} a_n(y)&=[x^n]\exp\left(y^Ax\int_{0}^{y}\sum_{i=0}^{\infty}a_{i}(t)x^{i}\mathrmw0obha2h00t\right)\\ &=[x^n]\exp\left(y^A\sum_{i=0}^{\infty}x^{i+1}\int_{0}^{y}a_{i}(t)\mathrmw0obha2h00t\right)\\ \end{aligned} \]

考慮算一下前幾項：

當 \(n=1\)，有 \(a_1(y)=y^{A+1}\)
當 \(n=2\)，有 \(a_2(y)=\left(\frac{1}{2}+\frac{1}{A+2}\right)y^{2(A+1)}\)

非常的 amazing 啊，我們發現只有 \(y^{n(A+1)}\) 這一項！那么可以歸納證明得到形如 \(a_n(y)=g_ny^{n(A+1)}\)，特別的 \(g_0=1\)，具體原理是什么我也不知道，反正就是很神奇！

那 \(y\) 差不多就沒用了，我們直接把那個積分算出來，就是

\[\frac{y^{1+i(A+1)}}{1+i(A+1)}g_i \]

帶回原式并令 \(y=1\)，有

\[g_n=[x^n]\exp\left(\sum_{i\ge 0}\frac{g_i}{1+i(A+1)}x^{i+1}\right) \]

記里面的東西是 \(h\)，那就隨便遞推了，有

\[g_n=[x^n]\exp h=\frac{1}{n}\sum_{i=1}^{n}ih_ig_{n-i} \]

\[h_n=[x^n]\sum_{i\ge 0}\frac{g_i}{1+i(A+1)}x^{i+1}=\frac{g_{n-1}}{1+(n-1)(A+1)} \]

\(\mathcal{O}(n^2)\) 遞推即可

AT_agc069_c [AGC069C] AB*A Changing

帶芮晨純神，審計與不會寫題解就別寫了

考慮把 \(S\) 和 \(T\) 都看成一個二進制數，那么每次操作相當于選擇一個位置 \(i\)，給 \(S\) 加上 \(3\times 2^{i}\)，設 \(i\) 被操作了 \(x_i\) 次，那么顯然有一個合法的必要條件 \(3\times\sum_{i}x_i2^i=T-S\)，而我們要保證操作的位置 \(s_i=0\)，所以 \(x_i\) 能操作的次數的上界為 \([s_i=0]+\left\lfloor\frac{S+3\sum_{j<i}x_j2^j}{2^i}\right\rfloor-\left\lfloor\frac{S}{2^i}\right\rfloor\)，后面的東西是進位的次數

欲最小化 \(\sum x_i\)，由于 \(\sum x_i2^i\) 是定值，所以可以從大往小貪心取最大的，那么有兩個限制，第一個限制是 \(3\times x_i\times 2^i\le T-S\)，另一個限制是 \(x_i\le [s_i=0]+\left\lfloor\frac{S+3\sum_{j<i}x_j2^j}{2^i}\right\rfloor-\left\lfloor\frac{S}{2^i}\right\rfloor=[s_i=0]+\left\lfloor\frac{T-3\sum_{j>i}x_j2^j}{2^i}\right\rfloor-\left\lfloor\frac{S}{2^i}\right\rfloor-3x_i\)，這兩個限制都能隨便維護，復雜度 \(\mathcal{O}(n)\)

AT_arc180_e [ARC180E] LIS and Inversion

牛。

把問題轉成 \(\ge a_i\) 的才有貢獻，考慮成本為 \(0\) 時的最大得分，記 \(f_{i,j}\) 為考慮了前 \(i\) 個數，LIS 結尾位置的排名為 \(j\) 的最大長度，那么有轉移：

\(f_{i-1,j}\rightarrow f_{i,j}\)
\(f_{i-1,j-1}\rightarrow f_{i,j}\)，\(j>a_i+1\)
\(f_{i-1,k}+1\rightarrow f_{i,j}\)，\(k\ge j>a_i\)

最長的 LIS 即為 \(\max f_{n,i}\)

根據定義又有 \(f_{i,j}\le f_{i,j+1}+1\)，因為交換 \(j\) 和 \(j+1\)，答案最多變化 \(1\)

那第二種轉移顯然就廢了，第三種轉移 \(k>j\) 的也是沒用的，于是就有

\[f_{i,j}=f_{i-1,j}+[j>a_i] \]

那記

\[g_i=\sum_{j\ge i}a_j<i \]

答案就是 \(\max_{i=1}^n g_i\)

成本不是 \(0\) 的情況，成本加一就是把其中一個 \(a_j\) 變成 \(0\)，設成本為 \(x\)，那答案就是

\[\max(0,x-\max_{i=1}^{n-x+1}g_i) \]

復雜度線性

P2398 GCD SUM

誰跟你莫反/qd。

弓禪黨卷積。

P3768 簡單的數學題

莫反。

\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d=1}^nd[\gcd(i,j)=d]\\ =&\sum_{d=1}^nd^3\sum_{i=1}^{\left\lfloor \frac{n}w0obha2h00\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}w0obha2h00\right\rfloor}ij[\gcd(i,j)=1]\\ =&\sum_{d=1}^nd^3\sum_{i=1}^{\left\lfloor \frac{n}w0obha2h00\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}w0obha2h00\right\rfloor}ij\sum_{t|\gcd(i,j)}\mu(t)\\ =&\sum_{d=1}^nd^3\sum_{t=1}^{\left\lfloor \frac{n}w0obha2h00\right\rfloor}\mu(t)t^2\sum_{i=1}^{\left\lfloor \frac{n}{dt}\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{dt}\right\rfloor}ij\\ \end{aligned} \]

設 \(f(n)=\left(\sum_{i=1}^{n}i\right)^2\)，令 \(k=td\)，原式等于

\[\begin{aligned} &\sum_{k=1}^{n}f\left(\left\lfloor \frac{n}{k}\right\rfloor\right)\sum_{d|k}\mu\left(d\right)d^2\left(\frac{k}w0obha2h00\right)^3\\ =&\sum_{k=1}^nf\left(\left\lfloor \frac{n}{k}\right\rfloor\right)k^2\sum_{d|k}\mu(d)\frac{k}w0obha2h00 \end{aligned} \]

后面那個東西是 \(\mu*id=\varphi\)，那就要求

\[\sum_{k=1}^{n}f\left(\left\lfloor \frac{n}{k}\right\rfloor\right)k^2\varphi(k) \]

問題在算 \(f(k)=k^2\varphi(k)\) 的前綴和，構造 \(g(x)=x^2\)，則有

\[(g*f)_{n}=\sum_{d|n}d^2\left(\frac{n}w0obha2h00\right)^2\varphi\left(\frac{n}w0obha2h00\right)=n^2\sum_{d|n}\varphi(d)=n^3 \]

直接杜教篩，復雜度 \(\mathcal{O}(n^{\frac{3}{4}})\)

P3704 [SDOI2017] 數字表格

這一塊這一塊這一塊這一塊這一塊這一塊

\[\begin{aligned} &\prod_{i=1}^{n}\prod_{j=1}^{m}f_{\gcd(i,j)}\\ =&\prod_{d=1}^{\min(n,m)}f_d^{\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]}\\ \end{aligned} \]

上面那個

\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]\\ =&\sum_{t=1}^{\left\lfloor\frac{\min(n,m)}w0obha2h00\right\rfloor}\mu(t)\left\lfloor\frac{n}{dt}\right\rfloor\left\lfloor\frac{m}{dt}\right\rfloor \end{aligned} \]

原式就是

\[\prod_{T=1}^{n}\left(\prod_{d|T}F_w0obha2h00^{\mu\left(\frac{T}w0obha2h00\right)}\right)^{\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{n}{T}\right\rfloor} \]

里面的可以預處理，外面的整除分塊，復雜度

\(\mathcal{O}(n\log n+T\sqrt n\log MOD)\)

P5221 Product

把 \(\text{lcm}\) 拆了，\(\prod \prod \gcd\) 直接莫反完了指數上是一個歐拉函數前綴和，直接算就完了

P6825 「EZEC-4」求和

\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)^{i+j} \end{aligned} \]

莫反完了是

\[\sum_{T=1}^{n}\sum_{d|T}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\left(\left(\frac{T}w0obha2h00\right)^T\right)^{i+j} \]

后面那個，等比數列求和。

復雜度 \(\mathcal{O}(n\log n\log MOD)\)

P3700 [CQOI2017] 小 Q 的表格

有

\[\frac{f(a,b)}{ab}=\frac{f(a,a+b)}{a(a+b)} \]

這不是我們啥啥啥啥術嗎，就有

\[f(a,b)=\frac{ab}{\gcd(a,b)^2}f(\gcd(a,b),\gcd(a,b)) \]

于是我們要求的就是

\[\sum_{d=1}^{k}f(d,d)\sum_{i=1}^{\left\lfloor \frac{k}w0obha2h00\right\rfloor}\sum_{j=1}^{\left\lfloor \frac{k}w0obha2h00\right\rfloor}ij[\gcd(i,j)=1] \]

后面那個東西跟 P3768 一樣，可以 \(\mathcal{O}(1)\) 求，于是現在只需要單點修改求前綴和，上個分塊平衡一下復雜度，總復雜度 \(\mathcal{O}(m\sqrt n)\)

#10098. Random Sum

別做多項式了。

直接做就是求 \(\prod_{i=1}^{n}(1+q_ix^{a_i})\pmod {x^{p}-1}\)，把 \(a_i\bmod p\) 相同的放到一組里分治乘，帶入 \(x^{t}\)，最后再卷起來，復雜度是 \(\mathcal{O}(m\log^2m+p^2\log p)\)，后面的復雜度太大了

考慮平衡一下復雜度，先取一個閾值 \(B\)，有結論，對于任意的 \(x\in [0,p)\)，都存在 \(i\in[1,B]\) 使得 \(ix\bmod p\le \frac{p}{B}\) 或者 \(ix \bmod p \ge p-\frac{p}{B}\)，為啥呢，考慮在長為 \(p\) 的環上取 \(B\) 個點，根據鴿巢原理，最近的兩個點的距離 \(\le\frac{p}{B}\)，把某兩個點作差即可得到結論

那每一組中的多項式度數 \(\le\frac{p}{B}\)，再做復雜度就是 \(\mathcal{O}(\frac{p}{B}m\log m+pB\log p)\)，平衡得到 \(\mathcal{O}(p\sqrt m\log^{1.5}(p+m))\)，這個時限還有這個數據范圍有點逆天了

P10222 [省選聯考 2024] 最長待機

這種題目是在區分誰來著，區分誰看知乎看得多嗎。

題意很繞，我們每個點肯定會選一個盡量大的數，這個數比任何正整數都要大，我們記作 \(\omega\)，然后有 \(1+\omega>\omega\)，因為你可以花 \(1\) 的時間看一下對面的數，然后再選擇一個比對面更大的數，而 \(\omega+1=\omega\)，因為你在 \(\omega\) 后面加一并沒有什么卵用

由此你可以得到 \(1+\omega,2+\omega,\cdots,\omega+\omega\)，\(\omega+\omega\) 用 \(2\omega\) 表示

還可以得到 \(2\omega,3\omega,\cdots,\omega^2\)

還可以得到 \(\omega^2,\omega^3,\cdots,\omega^{\omega}\)，但是這個跟此題就沒什么關系了

另外，有 \(\omega\times F=\omega^{\text{deg}(F)+1}\)，當 \(a>b\) 時有 \(\omega^{a}+\omega^=\omega^a\)

這樣就能做了，對于詢問 \(e=1\) 的節點，只需要知道子樹中到根鏈上 \(e=1\) 的節點數量最多的葉子就行了，這個可以線段樹維護，對于 \(e=0\) 的節點，我們要算的是一個前綴最大值的和的形式，直接做不好維護，我們可以考慮在括號序上維護，只需要一個單側遞歸線段樹

復雜度 \(\mathcal{O}(n\log^2n)\)

10.3

模擬賽

T1

T1。

T2

T2。

T3

T3。

T4

把 \(\varphi(ab)\) 拆成 \(\varphi(a)\varphi(b)\frac{\gcd(a,b)}{\varphi(\gcd(a,b))}\)，枚舉 \(\gcd\) 做一個支配點對的東西就沒了

10.4

腦子快報了，啥也想不動

P5325 【模板】Min_25 篩

欲求

\[Ans=\sum_{i=1}^{n}f(i) \]

由于每個合數的最小質因子都 \(\le \sqrt n\)，可化為

\[\sum_{p\in \text{prime},1\le p\le n}f(p)+\sum_{p\in \text{prime},1\le p\le\sqrt n,1\le p^c\le n}f(p^c)\left(\sum_{1\le i\le \frac{n}{p^c},minp_{i}>p}f(i)\right) \]

其中 \(minp_i\) 為 \(i\) 的最小質因子

記

\[g(n,i)=\sum_{j\in\text{prime or }minp_j>p_i }f'(j) \]

其中 \(f'\) 是一個與 \(f\) 在質數處值相同的完全積性函數，有

\[g(n,i)=g(n,i-1)-f'(p_i)\left(g\left(\left\lfloor\frac{n}{p_i}\right\rfloor,i-1\right)-g(p_{i-1},i-1)\right) \]

我們把 \(g(n,x)\) 的值存下來，其中 \(x\) 是最大的 \(\le \sqrt n\) 的質數的位置，不妨直接記這個東西為 \(g(n)\)，需要存所有的 \(\left\lfloor\frac{n}{i}\right\rfloor\) 處的值，開個 map 就太唐了，那對于 \(\left\lfloor\frac{n}{i}\right\rfloor\le\sqrt n\) 的，存到 \(id1\) 里，對于 \(\left\lfloor\frac{n}{i}\right\rfloor>\sqrt n\) 的，把 \(\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor\) 存到 \(id2\) 里，這樣兩個數組存的都 \(\le \sqrt n\) 了

記

\[S(n,x)=\sum_{1\le i\le n,minp_i>p_x}f(i) \]

有

\[S(n,x)=g(n)-sp_x+\sum_{p_k^e\le n,k>x}f(p_k^e)\left(S\left(\frac{n}{p_k^e},k\right)+[e> 1]\right) \]

直接計算，復雜度好像是 \(\mathcal{O}(n^{1-\epsilon})\)

AT_agc055_d [AGC055D] ABC Ultimatum

定義 \(prea_k=\sum_{i=1}^k \left[s_i=A\right]\)，同理可以定義 \(preb,prec\)，我們觀察一下這三種串

ABC
BCA
CAB

我們發現，只有 ABC 是 A 的位置在 C 的前面，那么合法序列的一個必要條件就是

\[\forall i,prea_i-prec_i\le cnt_{ABC} \]

同理，我們可以得到

\[\forall i,preb_i-prea_i\le cnt_{BCA} \]

\[\forall i,prec_i-preb_i\le cnt_{CAB} \]

合起來就是

\[\max(prea_i-prec_i)+\max(preb_i-prea_i)+\max(prec_i-preb_i)\le n \]

這顯然是一個必要條件，我們可以證明他是充要的

首先，如果一個序列合法，那么他的輪換也合法，因為那三種串輪換對稱，所以我們可以每次把一個字符放到最后的位置，如果他本來和另外兩個字符在一起，把這三個字符還放在一起，其他的不變就可以了，那我們不妨直接把整個序列首尾相連變成一個環，給出構造：對于環上的第 \(i\) 個 A，令其和第 \(i+cnt_{BCA}\) 個 B 與第 \(i+cnt_{BCA}+cnt_{CAB}\) 個 C 一組

我們要說明這個構造合法，只需要說明第 \(i+cnt_{BCA}+cnt_{CAB}\) 個 C 不在第 \(i\) 個 A 和第 \(i+cnt_{BCA}\) 個 B 之間，考慮從第 \(i\) 個 A 處斷環成鏈，去證明第 \(i+cnt_{BCA}+cnt_{CAB}\) 個 C 的位置 \(\le 3n\)，這時候他在第 \(1+cnt_{BCA}+cnt_{CAB}\) 個 C 處，因為 \(cnt_{BCA}+cnt_{BCA}+cnt_{CAB}=n\)，而 \(A\) 又是在最開頭所以 \(cnt_{ABC}>0\)，所以就能得到 \(1+cnt_{BCA}+cnt_{CAB}\le n\)，而最壞的時候是這個 C 在所有的 A 和 B 的右邊，所以結論得證

直接 \(\mathcal{O}(n^6)\) dp 即可

對于 \(i\in[l,r]\)，\(a'_i=a_i,c'_i=(his_i+a_i)-(t+1)\times a_i=c_i\)

對于 \(i\not \in[l,r]\)，\(a'_i=a_i+k,c'_i=(his_i+a_i+k)-(t+1)\times (a_i+k)=c_i-t\times k\)

posted @ 2025-09-30 13:49 fqmzwmhx 閱讀(21) 評論(0) 收藏舉報

刷新頁面返回頂部

oaigoaigilowoaigiy

9.30

模擬賽

T1

T2

T3

T4

10.1

模擬賽

T1

T2

T3

T4

10.2

10.3

模擬賽

T1

T2

T3

T4

10.4

公告