# d311. 數學少女的難題

###### tags: `競程題解`,`競程`

Timestamp:2023/10/07 17:56

> 明明備審只剩三天可以弄了 還有一堆事情要做XD 結果還是跑來戳題

我的想法是透過分治去解

就是要取 m 項，有三種可能

取的在 1~n 之間
在 1~/n2
n/2+1~n
就這樣一直遞迴下去

更詳細一點就是：

先假設左塊的名字叫 L 然後範圍是 1~n/2 右塊是 R 然後 n/2+1~n

假設已經算好 L 裡面取 0~n/2 個數字的分別答案 R 也是算好了 接下來就是要合併成一塊大塊的 1~n 名字叫 O

合併的話 在 O 裡面取 x 個 就會是：從 L 裡面取 0 R 裡面取 x , 從 L 取 1 R 裡面取 x-1 ... L 取 x R 取 0 個 這些數的總和就會是在 O 裡面取 x 個算出來的答案

這樣做的複雜度是 O(x)

然後接下來因為有 O(logn) 層 總節點數是 O(nlogn) //可以想成線段樹那樣啦

然後每一層要做的就是從下面的合併 合併的話就會是計算該層要拿 0 個 ~ n 個 所以一次合併就會是 O(n*n)

這樣算起來會發現複雜度是 O(n^3 logn) 會 TLE (我自己拿到 80%)

接下來就是要優化一下

可以發現 每一個節點 最多拿的就是他的節點大小 例如這一個節點代表的是從 k~k+100 這一段的答案，那這一個節點大小就會是 101

所以在合併的過程中，我們只需要計算每一個節點拿 0~sz(node) 個就好!

這樣的複雜度就會變成是 O(2^0*n*n + 2^1*(n/2)*(n/2) + 2^2 *(n/4)(n/4)........+2^(logn)*1*1 )

這樣整理起來就會變成是 O(n^2 + (n^2)/2 + (n^2)/4....)

提出 n^2 就會變成是也就是 O(logn * (n^2)) 這樣就 AC 了 雖然複雜度分析沒有那麼直觀?

但那個優化的點應該是非常非常直觀的XD

附上 AC 扣的碎片
雖然會 TLE 但看完後理解應該就知道怎麼改了XDD

void build(int l,int r,int now){
    int sz = ｎ;
    for(int i=0;i<=sz;i++){
        for(int j=0;j<=sz;j++){
            seg[now][i] = (seg[now][i]+seg[now*2][j]*seg[now*2+1][i-j])%P;
        }
        seg[now][i] = (seg[now][i]+seg[now*2][i]+seg[now*2+1][i])%P;
    }
    return ;
}