# TFcis t27 寒訓 + 台南一中 115&116資訊讀書會 練習賽 (div 1) 題解

## pA - 爬樓梯 2.0

**author : blame**
**problem setter : blame**

**first kill : 聖殤**

:::spoiler **subtask 1 (5/100) 1 <= N <= 2 × 10^5**
**div 2的 ac code**
:::

:::spoiler **subtask 2 (10/100) M = 0**
**算數學**
:::

:::spoiler **subtask 3 (12/100) M = 1**
**分成兩半，算數學**
:::

:::spoiler **subtask 4 (100/100)**
**$N$ 看起來就一臉超大的樣子**
**然後爬樓梯又是經典的DP問題**
**所以我們可以馬上想的到DP優化中的 "矩陣快速冪" 幫助轉移**
**然後經過一連串的實作就可以AC了**
:::

## pB - APMO初選第1.5階段

**author : paul**
**problem setter : blame**

**first kill : 聖殤**

:::spoiler **subtask 1 (1/100)**
$$
mn = c
$$
**所以只要找 $C$ 的因數個數 $\times 2$ 就行**
:::

:::spoiler **subtask 2 (100/100)**
$$
mn = a \times m + b \times n + c
$$
$$
mn - am - bn = c
$$
$$
m(n-a) - bn = c
$$
$$
m(n-a) - bn + ba = c + ba
$$
$$
m(n-a) - b(n-a) = c + ab
$$
$$
(m-b)(n-a) = c + ab
$$
**所以簡單的找 $c + ab$ 的因數個數 $\times 2$ 即可**

#include <iostream>
using namespace std;
int frac[1000001];
int main() {
    for(int i = 2; i <= 1000000; i++)
        for(int j = i; j <= 1000000; j+=i)
            frac[j]++;
    int t; cin >> t;
    while(t--) {
        int a, b, c; cin >> a >> b >> c;
        cout << frac[c+a*b]*2+2 << '\n';
    }
}

**複雜度 $O(10^6lg(10^6) + Q)$**
:::

## pC - 快速冪

**author : blame**
**problem setter : blame**

**first kill : wonderhoi**

:::spoiler **subtask 1 (1/100) 1 <= A, B <= 10^9**
**正常的快速冪，只是要記得 $1 \le C \le 10^12$**
**所以在快速冪相乘的時候會溢位 超出 long long 範圍**
:::

:::spoiler **subtask 2 (2/100) 1 <= B <= 10^9**
**發現 $A$ 已經屬於大數範圍了**
**所以要對 $A$ 做大數取模，取模對象是 $C$**
:::

:::spoiler **subtask 3 (3/100) C 是質數**
**對 $A$ 以 $C$ 做大數取模， $B$ 以 $C-1$ 做大數取模**
:::

:::spoiler **subtask 4 (100/100)**
**發現 $C$ 不是質數了，所以要使用歐拉函數**
**$A^{phi(C)} = 1 \mod C$**
**然後就AC了**
**只是大家都卡在 $int128$**
:::

## pD - 快樂線段樹2.0

**author : blame**
**problem setter : blame**

:::spoiler **subtask 2 (100/100)**
**這題其實應該要有更細一點的配分**
**但是因為來不及，所以就沒有配分了**

**看到區間改值跟區間詢問，第一件事情會想到 "線段樹"**
**而後看到題目說線段樹**
**所以猜這題不是線段樹**
**然後你就猜對了**
**這題是柯朵莉樹**

**普通的科朵莉樹足以解掉這題**
:::

## pE - 區間平方和

**經典問題**
**problem setter : blame**

:::spoiler **subtask 1 (33/100) subtask 2 (100/100)**
**subtask 1 差不多正解，只是差在線段樹的 build 函式跟常數優化而已**
**首先會發現區間改值跟普通的懶標線段樹差不了多少**
**但是現在詢問的是區間平方和ㄟ?**

**國中就會的數學:**
**$(a + b)^2 = a^2 + 2 a b + b^2$**
**所以我們只要維護當前區間總和 跟 答案即可**

**當然，會有人想用zkw來解這題**
**但 zkw 似乎做不到這件事情，可以想一下為什麼**
:::

## pF - 歷史老師的安全帽

**author : brinton**
**problem setter : brinton**

:::spoiler **subtask 3 (5/100)**

#include <iostream>
using namespace std;
int main() {
    cout << "0\n";
}

:::

:::spoiler **ac**
問asdfg1021
:::

## pG - 一堵很高很大的牆

**author : brinton**
**problem setter : brinton**

:::spoiler **subtask 3 (10/100)**
**1直接輸出0**
**3直接輸出3**
**2的話看看有沒有跟3被1隔開，沒有就過是0，否則為1**
:::

:::spoiler **subtask 2 (15/100)**
**暴力解**
**對於每個比自己大的，去求他與自己的低谷值，取最小的**
**實作上可以每次遇到更小的，就把比自己大但還沒更新的更新上去**
:::

:::spoiler **subtask 4 (100/100)**
**滿分解**
**關鍵觀察0:若 $(A \to B)$ 的低谷值 $=(B \to A)$ 的低谷值**

**假設我們已知 $A \to B$ 的低谷值，$A \to C$ 的低谷值，且 $A > B > C$，我們想求 $C$點的神秘值。**
**關鍵觀察1:若 $(A,B)$ 的低谷值為 $x$, $(A,C)$ 的低谷值為 $y$,則 $(B,C)$ 的低谷值至少 $\geq min(x,y)$**
**$proof:$**
**因為 $C-B$ 存在一條 $C \to A \to B$ 的路**
**那 $C$ 點的神秘值能不能寫成 $max(0,C-min(x,y))$?**
**有沒有可能 $B \to C$ 存在更大的低谷值呢?**

**我們這邊只考慮 $min(x,y) \lt C$
不然答案都是 $0$**
**如果 $y \le x$ 那答案是對的(答案由y決定)**
**如果 $x \lt y$ 且 $x < C$,因為 $x >= min(A->C,C,C->B)= min(y,C,C \to B)$，又 $y$, $C \gt x$，故 $C \to B \le x$**

**所以就只要做所有點跟其中一個最高點的低谷值，然後填答案由大到小填，答案為 $max(0,C-min($這點到最高點的低谷值,所有比他大的點和最大點的低谷值$))$**

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (long long)(1e15)
int di[4] = {1,0,-1,0};
int dj[4] = {0,1,0,-1};
signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,M;
    cin >> N >> M;
    vector<vector<int>> grid(N,vector<int>(M));
    vector<array<int,3>> vp;
    for(int i = 0;i < N;i++){
        for(int j = 0;j < M;j++){
            cin >> grid[i][j];
            vp.push_back({grid[i][j],i,j});
        }
    }
    sort(vp.begin(),vp.end());
    reverse(vp.begin(),vp.end());
    // start from high
    priority_queue<array<int,3>> pq;
    pq.push(vp[0]);
    vector<vector<int>> dij(N,vector<int>(M,-1));
    dij[vp[0][1]][vp[0][2]] = vp[0][0];
    while(!pq.empty()){
        auto [upd,pi,pj] = pq.top();
        pq.pop();
        if(upd != dij[pi][pj])continue;
        for(int d = 0;d < 4;d++){
            int ni = pi+di[d];
            int nj = pj+dj[d];
            if(ni < 0 || nj < 0 | ni >= N || nj >= M)continue;
            if(dij[ni][nj] < min(upd,grid[ni][nj])){
                dij[ni][nj] = min(upd,grid[ni][nj]);
                pq.push({min(upd,grid[ni][nj]),ni,nj});

            }
        }
    }
    // for(auto i:dij){
    //     for(auto j:i)cout << j << " ";cout << endl;
    // }cout << endl;


    
    vector<vector<int>> ans(N,vector<int>(M));
    int prev = vp[0][0];
    int preMin = vp[0][0];
    int cMin = vp[0][0];
    for(auto [val,i,j]:vp){
        if(prev != val){
            preMin = min(preMin,cMin);
            prev = val;
        }
        // cout << val << " " << i << " " << j << " " << preMin << " " << cMin << endl;
        if(val == vp[0][0]){
            ans[i][j] = vp[0][0];
        }else{
            // cout << i << " " << j << " " << min(preMin,dij[i][j]) << endl;
            ans[i][j] = max(0LL,val-min(preMin,dij[i][j]));
        }
        cMin = min(dij[i][j],cMin);
    }
    for(auto i:ans){
        for(auto j:i){
            cout << j << " ";
        }
        cout << '\n';
    }
}

:::