NOIP模拟75

「如何優雅的送分·陰陽·你猜是不是找規律·小說」on 10.12

前言

先吐槽一下出題人，T2 牛馬資料連棵樹都不是。。

T3 描述不清楚。。

T1 如何優雅的送分

我考場上還真以為是個送分題，然而。。。

莫比烏斯反演。。。

對于一個數字 n 有 \(2^{F(n)}=\sum\limits_{d|n}\mu^2(d)\) ，由于有平方因子的數字的 \(\mu\) 的值是 0 ，就相當于在所有的質因數裡面選擇若幹個質因數組合。

\(\mu^2(n)=\sum\limits_{d^2|n}\mu(d)\) 對于質數的情況是比較顯然的，畢竟符合條件的隻有 1 。

這個可以了解為枚舉質因數的個數算對應的答案。

假設這個數質因數的個數是 \(cnt\) ，那麼答案就是 \(\sum\limits_{i=0}^{cnt}(-1)^i\times \binom{cnt}{i}\) 由二項式定理可得上式為 0 。

于是答案就是 \(\displaystyle\sum_{i=1}^n 2^{F(i)}=\sum_{i=1}^n\sum_{d|i}\sum_{k^2|d}\mu(k)\)

更改枚舉順序 \(\displaystyle\sum_{k=1}^n\mu(k)\sum_{k^2|d}\lfloor\frac{n}{d}\rfloor\)

也就是 \(\displaystyle\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k^2}\rfloor}\lfloor\frac{n}{k^2i}\rfloor\)

設 \(S(n)=\sum\limits_{i=1}^n\lfloor \frac{n}{i}\rfloor\) 上述柿子就是 \(\sum\limits_{k=1}^n \mu(k)S(\lfloor\frac{n}{k^2}\rfloor)\) 。

對于 \(S\) 的運算可以數論分塊 複雜度是 \(\mathcal{O}(\sqrt{n}logn)\)

T2 陰陽

正解不太會，打了個暴力，可能是由于資料水，騙到了 100pts （雖然後來被Hack成了 91pts）

比較好奇的就是出題人的資料怎麼造的（原來 n 個點 n-1 條邊還可以是有環的森林。。。）

暴力思路比較簡潔，我們需要一個可以動态開空間并且支援查找并且删掉某一個值的資料結構，<code>unoedered_set</code> 剛好可以滿足我們的需求。

于是我們可以維護每一個版本的所有黑色節點，每次暴掃整個 <code>set</code> 求出答案。

T3 你猜是不是找規律

我還真就以為是個找規律了。。。

出題人描述不清楚，題目認為的有序序列隻是一種順序隻能是升序或者隻能是降序。

DP 轉移 \(f_{i,j}\) 表示對于有序的序列前 i 個數字交換 j 次可以得到的不同序列。

就有方程：\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times(i-1)\) 。

然後發現其實字首和是一個有 \(2k\) 項的多項式（我也不知道為啥是這個。。），然後直接拉格朗日插值。。

T4 小說

運用退背包每次枚舉退掉的點，選擇造成損失比較小的，方案可以在對于大質數取模的意義下考慮。

然後有了這個去掉的物品，接下來我們所選擇的 b 不可以被剩下物品 \(v_i,-v_i\) 構成。

對于剩下的物品按上面兩個值做一個 01背包，取大于 0 的第一個值作為答案。