# k799. WEBWORK 的逆襲 題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 觀察

首先這個函數 $F(x)=ln(ax)^{-ln(bx)}$ 就很想要求他的不定積分，然後再代入$l, r$，但其實會發現好像很難，你會想去問計算機或 ChatGPT，然後 ...

他算不出來 :(

好啦，其實這個不是初等函數，所以其實不能直接積 (nani?)

### 定義

他要求的是 $\int _l^r F(x)dx$，根據積分的定義可以想成是 $F(x)$ 在 $(l,r)$ 下的面積，那這個我們可以怎麼求呢? (要看正解請跳過下面黎曼和的部分)

### 黎曼和? (Riemann Sum?)

首先，最簡單就是把它分成 $K$ 塊長方型，然後直接算 $K$ 個的面積加起來，理論上當 $K \rightarrow \infty$ 算出來的就會是面積，我們也可以把它變成梯形這樣子可能可以更貼近 $F(x)$ 的形狀，但是這題好像很難用梯形法，如圖，我吃了一堆 $\text{WA}$ 跟 $\text{TLE}$，~~然後偷偷透過潮汐跟一些數學及程式上的奇技淫巧過了~~，upd: 題主發現我三個ㄟ西的扣裡面混了一個假解，更新測資後被 hack 掉了QQ，becaidorz。

### 辛普森積分 (Simpson's method)
我們都能算出梯形面積了，這時候我們會想出一個通靈想法，就是辛普森在做的事情，那我中間再取一個點。
梯形法本來是像上面那樣(~~請假設紅色的是直線~~)，對於每一塊取兩個點，那如果是取三個呢? 我們多取一個中間的變成一個二次函數(因為是三個點，可以透過牛頓插值求二次方程)，請欣賞下面的精美畫圖(~~請假設他轉折的地方剛好在中間~~)

積分後這個的面積是 $\frac{F(L)+4F(mid)+F(R)}{6}$，其中 $\text{mid}$ 代表 $l, r$ 的中點，知道了這件事後，可以來做更奇怪的事情。

### 自適應辛普森積分 (Adaptive Simpson's method)

有的時候我們可能會遇到函數其實他是有一邊彎彎曲曲，一邊蠻平滑的，那對於平滑那邊可以切少一點(時間複雜度會好一點)，彎彎曲曲那邊可以切多塊一點，那個函數可能像下面這樣，那我們可以做一件特別的事情。


我們定義函式 $\text {cal (L,R)}$ 拿來計算區間 $(L,R)$ 的面積，當呼叫 $\text {cal (L,R)}$ 時我們把一個區間切成兩塊，算左半跟右半的辛普森積分然後相加起來，整體的辛普森積分也算一次，我們比較這兩個值的差，如果差的不多就停止遞迴，否則就真的把區間切成兩塊，然後呼叫 $\text {cal (L,mid)}$、$\text {cal (mid,R)}$ 這兩個函數並回傳它們的總和 (這裡的 $\text{mid}$ 代表 $l, r$ 的中間)。

實作上大概長這樣

Simpson(l, r):
    let mid be (l + r) / 2
    return (F(l) + 4 * F(mid) + F(r)) * (r - l) / 6


Cal(l, r, eps):
    let mid be (l + r) / 2
    let ST be Simpson(l, r)
    let SL be Simpson(l, mid)
    let SR be Simpson(mid, r)
    if abs(SL + SR - ST) <= 15 * eps then
        return SL + SR + (SL + SR - ST) / 15
    
    return Cal(l, mid, eps / 2) + Cal(mid, r, eps / 2)

上面先算出三個東西的辛普森積分 $ST, SL, SR$ ，根據它們的差去決定要不要繼續遞迴下一層，注意上面的 $eps$ 指的是可容許的誤差，那個 $15$ 是一個係數，根據J. N. Lyness 推導出來感覺這數字能確保很多函數的精度落在 $eps$ 內(其實我也不知道為什麼)，[論文](https://dl.acm.org/doi/pdf/10.1145/321526.321537)。