# 複習與題目
我已經不知道可以講什麼了 最後一次資讀就讓我偷懶一下
[cses](https://cses.fi/problemset/list/)
[usaco guide gold](https://usaco.guide/gold/)
## 數學
### 講義
#### [模逆元](https://hackmd.io/@Viecon-342524/SJzSuO_Bj#%E6%A8%A1%E9%80%86%E5%85%83-Modular-Multiplicative-Inverse)
#### [其他數學](https://hackmd.io/MGfghW7KQu2MdWTOzM6WcQ?view#-Math)
### 題目
#### 模逆元
[Exponentiation II](https://cses.fi/problemset/task/1712)

$$
\begin{aligned}
a^{b^c}&\equiv a^{k(p-1)}a^{b^c-k(p-1)} (\text{mod}\, p)
\\&\equiv a^{b^c-k(p-1)}
\end{aligned}
$$

#### 排列組合
大部分直接代公式就好
[Bracket Sequences II](https://cses.fi/problemset/task/2187)
畫方格然後把不合法的映射到對稱的地方就可以扣掉了

#### 因數
[Common Divisors](https://cses.fi/problemset/task/1081)
對值域做事
[Sum of Divisors](https://cses.fi/problemset/task/1082)
不難發現答案為$\sum_{i=1}^n i\lfloor {n\over i}\rfloor$
把$\lfloor {n\over i}\rfloor$一樣的一起做，複雜度為$O(\sqrt n)$
## 字串
### 講義
#### [Hash](https://hackmd.io/IKxtR4cLTwasYZPLFc7Q_w#Hash)
#### [string technique](https://hackmd.io/-5rjlBbuSeq6YpRm12XA7A)
### 題目
#### hash
[Finding Periods](https://cses.fi/problemset/task/1733)
窮舉長度，然後用前綴和的想法去算hash
[E. Compress Words](https://codeforces.com/contest/1200/problem/E)
暴力
#### trie
[Word Combinations](https://cses.fi/problemset/task/1731)
由後往前，如果前綴有在trie裡(並且要是結尾)就更新dp
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
vector<int> dp;
struct Trie{
    Trie* T[26];
    int cnt;
    Trie(){
        cnt=0;
        memset(T,0,sizeof(T));
    }
};
Trie *t;
void insert(string s){
    Trie *ptr=t;
    for(char i:s){
        if(!ptr->T[i-'a']){
            ptr->T[i-'a']=new Trie();
        }
        ptr=ptr->T[i-'a'];
    }
    ptr->cnt++;
}
void query(string s,int pos){
    Trie *ptr=t;
    int l=1;
    for(char i:s){
        if(!ptr->T[i-'a']){
            return;
        }
        if(ptr->T[i-'a']->cnt>0){
            dp[pos]+=dp[pos+l];
            dp[pos]%=mod;
        }
        l++;
        ptr=ptr->T[i-'a'];
    }
}
int main(){
    string s;
    int n,k;
    cin>>s>>k;
    n=s.size();
    dp.resize(n+1);
    dp[n]=1;
    t=new Trie();
    for(int i=0;i<k;i++){
        string a;
        cin>>a;
        insert(a);
    }string tmp="";
    for(int i=1;i<=n;i++){
        tmp=s[n-i]+tmp;
        query(tmp,n-i);
    }
    cout<<dp[0]%mod<<endl;
}

:::
## dp
### 講義
[Dynamic Programming II](https://hackmd.io/@Viecon-342524/ryjjol4Ns)
### 題目
#### 有限背包
[Book Shop II](https://cses.fi/problemset/task/1159)
令$dp[i][j]$為考慮前$i$個物品且重量為$j$的方法數，則
$$
\begin{aligned}
dp[i][j] &= \max_{0 \leq num \leq x_i}(dp[i - 1][j - num * w_i] + num * v_i)
\\&= \max_{k \equiv j \pmod {w_i}, 0 \leq \frac{j - k}{w_i} \leq x_i}(dp[i - 1][k] + v_i * \frac{j - k}{w_i})
\\&=v_i * \lfloor \frac{j}{w_i} \rfloor + \max_{k \equiv j \pmod {w_i}, 0 \leq \lfloor \frac{j}{w_i} \rfloor - \lfloor \frac{k}{w_i} \rfloor \leq x_i}(dp[i - 1][k] - v_i * \lfloor \frac{k}{w_i} \rfloor)
\end{aligned}
$$
只有和$j$同餘的會有可能是轉移點。
然後維護一個單調隊列，每次從$x_i$的範圍中找最大的

另一種方法:
把東西分成$2^0, 2^1, 2^2$個
## 分治
把東西切小塊的都是分治，包含二分搜、線段樹等。
### 題目
#### 線段樹與bit的應用
[Subarray Sum Queries](https://cses.fi/problemset/task/1190)
要存的資訊:sum、最大prefix、suffix、subarray

void pull(){
    sum=lc->sum+rc->sum;
    pre=max(lc->pre,lc->sum+rc->pre);
    suf=max(rc->suf,rc->sum+lc->suf);
    mx=max({lc->mx,rc->mx,lc->suf+rc->pre});
}

[Intersection Points](https://cses.fi/problemset/task/1740)
對x的值域開bit(或線段樹)，把所有線段依y座標排序，就可以轉換成區間加值和區間求和了(或者單點加值區間求合)。
#### 其他
[Meet in the Middle](https://cses.fi/problemset/task/1628)
從中間切一半，枚舉集合，把可能的合丟進vector裡，sort，然後再二分搜找有哪些可以合成$x$。
[E. Maximum Subsequence](https://codeforces.com/contest/888/problem/E)
就和上面那題差不多。
[F. Xor-Paths](https://codeforces.com/contest/1006/problem/F)
把方格從右上到左下(原因是每條路徑都一定只通過這條線一次)切一半，線上每個點都存從起點走和從終點走可能有哪些值，一樣可以二分搜。
:::success
:bulb: 若$a\oplus b=c$ 則 $b\oplus c=a$
:::