---
# System prepended metadata

title: CSES Mathematics(37 題)

---

# Mathematics(37 題)
## Josephus Queries [problem](https://cses.fi/problemset/task/2164)
```markdown
題目: 

- 給定多組查詢，每組查詢給你 n 和 k。
- 問：在一個大小為 n 的圓圈裡進行 Josephus 問題，每次從當前人開始數第 2 個人並淘汰，問最後第 k 
  個人是誰（1-indexed）。
- 這題是 k 給定，問第 k 個人會坐在哪個位置。
```
``` markdown
解法 : 

### 1. Josephus 的遞迴解法（kill step = 2）：
   - 用經典的 Josephus 遞迴方式推導：
     - 若 k ≤ ⌈n/2⌉，表示第 k 人還活著，位置會被平移到偶數位：
       - 若 2k > n，需對 n 取模（環狀），結果為 2k % n。
       - 否則，結果就是 2k。
     - 若 k > ⌈n/2⌉，表示第 k 人在淘汰之後的子問題中，重編號求解：
       - 遞迴轉為求 f(n/2, k - ⌈n/2⌉)。
       - 根據 n 為奇或偶，平移量不同：
         - 若 n 為奇，結果為 2×f + 1。
         - 若 n 為偶，結果為 2×f − 1。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL f(LL n,LL k)
{
    if(n==1) return 1;
    if(k<=(n+1)/2) 
    {
        if(2*k>n) return (2*k)%n;
        else return 2*k;
    }
    LL temp=f(n/2,k-(n+1)/2);
    if(n%2==1) return 2*temp+1;
    return 2*temp-1;
}
 
int main(){
    fastio;
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        cout<< f(n,k) <<"\n";
    }
}
```

## Exponentiation [problem](https://cses.fi/problemset/task/1095)
```markdown
題目: 

- 給定多組查詢，每次輸入兩個整數 n 和 k。
- 請輸出 n^k mod 10^9+7 的值。
- 數據範圍允許 k 非常大，因此不能使用暴力乘法。
```
``` markdown
解法 : 

### 1. 快速冪（Binary Exponentiation）：
   - 利用指數的二進位展開，讓每次乘法都只在必要時做：
     - f(n, k) = f(n, k/2)^2 若 k 為偶數。
     - 若 k 為奇數，則再乘上 n。
   - 每一步都取 mod 可保證數值不爆炸。
   - 時間複雜度為 O(log k)，非常高效。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL f(LL n,LL k)
{
    if(k == 1)
        return n;
    if(k == 0)
        return 1;
    LL ret = f(n, k >> 1)%MOD;
    ret = (ret * ret) % MOD;
    if(k & 1){
        ret *= n;
        ret %= MOD;
    } return ret;
}
 
int main(){
    fastio;
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        cout<< f(n,k) <<"\n";
    }
}
```

## Exponentiation II [problem](https://cses.fi/problemset/task/1712)
```markdown
題目: 

- 給定多組查詢，每組包含三個整數 a、b、c。
- 要你計算 (a^(b^c)) mod 10^9+7。
- 因為 b^c 可能非常大，不能直接算出再取模，必須分層處理。
```
``` markdown
解法 : 

### 1. 使用模反冪的性質簡化問題：
   - 根據歐拉定理（若 a 與 m 互質，則 a^φ(m) ≡ 1 mod m）：
     - 可將 exponent 降模為 φ(MOD) = 10^9+6。
     - 所以 b^c % (MOD−1) 可作為 a 的最終次方。
     - 最終為：a^(b^c % (MOD−1)) % MOD。

---

### 2. 巢狀快速冪處理：
   - 先用快速冪計算 b^c mod (MOD−1)，再算 a^result mod MOD。
   - 遞迴實作中 `t` 控制當前模數是 MOD（t=0）還是 MOD−1（t=1），防止取錯模。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL solve(LL n, LL k, LL t)
{
    if(k == 1)
        return n;
    if(k == 0)
        return 1;
    LL ret = solve(n, k >> 1, t) % (MOD-t);
    ret = (ret * ret) % (MOD - t);
    if(k & 1){
        ret *= n;
        ret %= (MOD - t);
    } return ret;
}
 
int main(){
    fastio;
    int T;
    cin >> T;
    while (T--) {
        int a, b, c;
        cin >> a >> b >> c;
        cout<< solve(a, solve(b, c, 1), 0) <<"\n";
    }
}
```

## Counting Divisors [problem](https://cses.fi/problemset/task/1713)
```markdown
題目: 

- 給定 T 筆查詢，每筆輸入一個正整數 n。
- 對每個 n，輸出它的**正因數個數**。
- 例如：12 有因數 {1, 2, 3, 4, 6, 12}，總共 6 個。
```
``` markdown
解法 : 

### 1. 利用質因數分解求因數個數：
   - 如果 n 的質因數分解為：n = p1^e1 × p2^e2 × ... × pk^ek，
     - 則它的正整數因數個數為：(e1+1) × (e2+1) × ... × (ek+1)。
   - 程式中做法：
     - 先對 2 和 3 特別處理（效率最佳化）。
     - 接著以 6 為間隔測試質數（i, i+2）來進行 trial division。
     - 若 n 最後大於 1，代表它本身是個大質數，也需要加入。
   - 最後對所有質因數的次方加一並相乘，即為答案。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;

int main(){
    fastio;
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        map<int, int> m;
        while((n % 2) == 0){
            m[2]++;
            n >>= 1;
        } while((n % 3) == 0){
            m[3]++;
            n /= 3;
        } for(int i = 5; i * i <= n; i += 6){
            while((n % i) == 0){
                m[i]++;
                n /= i;
            } while((n % (i+2)) == 0){  // 別忘了 i+2
                m[i+2]++;
                n /= (i+2);
            }
        }
 
        if (n > 1) m[n]++;
 
        LL ans = 1;
        for(auto e: m){
            ans *= e.s + 1;
        }
        cout << ans << '\n';
    }
}
```

## Common Divisors [problem](https://cses.fi/problemset/task/1081)
```markdown
題目: 

- 給定 n 個整數，從中選出兩個數，問這些數中**最大的共同因數（gcd ≥ 1）**可能是幾？
- 換句話說：求所有數對中，最大可能的 gcd。
```
``` markdown
解法 : 

### 1. 頻率表 + 反向枚舉因數：
   - 用 freq[x] 記錄每個數字出現次數。
   - 從 d = 1e6 開始向下枚舉每個可能的 gcd 值 d。
     - 枚舉所有 d 的倍數 m，統計 freq[m] 出現幾次。
     - 若某個 d 作為因數時，出現的數量 ≥ 2，表示存在至少一對數的 gcd 為 d。
   - 最先找到的 d 就是最大的合法解，因為從大到小枚舉。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
int main(){
    fastio;
    int T = 1;
    while (T--) {
        int n;
        cin >> n;
        vector<int> freq(1e6 + 5, 0);
        for(int i=0; i<n; ++i) {
            int x;
            cin >> x;
            freq[x]++;
        }
 
        for(int d=(1e6); d>=1; --d) {
            int cnt = 0;
            for(int m=d; m<=1e6; m+=d) {
                cnt += freq[m];
                if(cnt >= 2) break;
            }
            if(cnt >= 2) {
                cout << d << endl;
                return 0;
            }
        }
    }
}
```

## Sum of Divisors [problem](https://cses.fi/problemset/task/1082)
```markdown
題目: 

- 給定一個正整數 n，請計算：
  - σ(n) = ∑_{i=1}^{n} (n // i) × i。
- 最後答案對 10^9+7 取模。
- 注意：n 非常大，最多到 10^12，不能直接暴力枚舉每個 i。
```
``` markdown
解法 : 

### 1. 數學推導 + 分塊技巧（Divisor Summation Trick）：
   - 對於所有的 i ∈ [1, n]，n // i 的值其實只會改變 √n 次。
   - 令 q = n // i 固定，則能找到一段連續的區間 [l, r]，使得 n//l = n//r = q。
     - 可以對 q 同值的整段 i 批次計算：∑_{i=l}^{r} i = (l + r)(r − l + 1)/2。
   - 每段的貢獻為：q × ∑_{i=l}^{r} i。

---

### 2. 實作細節：
   - 使用快速乘法與模逆元：
     - (l + r)(r − l + 1)/2 mod MOD 使用 inv2 = 500000004（因為 2 的模逆元）。
   - 記得每一項都對 MOD 取模，避免 overflow。
   - 時間複雜度：O(√n)
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
int main(){
    fastio;
    LL n;
    cin >> n;
 
    LL ans = 0;
    for (LL l=1; l<=n; ) {
        LL k = n/l;
        LL r = n/k;
        const LL inv2 = 500000004; // 因為 (2*inv2) ≡ 1 (mod 1e9+7)
 
        LL cnt = (r - l + 1) % MOD;
        LL sum_lr = (l + r) % MOD;
        LL sum_d = cnt * sum_lr % MOD * inv2 % MOD;
        ans = (ans + k % MOD * sum_d % MOD) % MOD;
        l = r+1;
    }
 
    cout << ans << '\n';
}
```

## Divisor Analysis [problem](https://cses.fi/problemset/task/2182)
```markdown
題目: 

- 給定 n 個質因數分解的結果，每個為 (p, a)，代表整數 N = p₁^a₁ × p₂^a₂ × ... × pₙ^aₙ。
- 請輸出以下三個值（mod 10^9+7）：
  1. N 的因數總數。
  2. N 的所有因數之和。
  3. N 的所有因數之積。
```
``` markdown
解法 : 

### 1. 因數總數：
   - 利用公式：N 的因數總數為 (a₁+1) × (a₂+1) × ... × (aₙ+1)。

---

### 2. 因數總和：
   - 每個質因數 pᵢ 貢獻的總和為等比數列：
     - Sᵢ = 1 + pᵢ + pᵢ² + ... + pᵢ^aᵢ = (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1)。
   - 取 mod 需要使用乘法逆元來處理除法：
     - inv(p−1) ≡ pow(p−1, MOD−2)。

---

### 3. 因數積（關鍵）：
   - 因數個數為 D，則因數積為 N^(D/2)。
   - 但要注意 MOD 為質數，指數模運算需用 MOD−1：
     - 使用費馬小定理：a^b mod M，若 b 很大，要對 b 取 mod M−1。
   - 處理奇偶：
     - 若 D 為奇數，將某個 (aᵢ+1)/2，其他正常，確保整體指數為整數。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;

LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main(){
    fastio;
    LL n;
    cin >> n;
    vector<pair<LL, LL>> prime(n);
    for(auto &x: prime){
        cin >> x.f >> x.s;
    }
 
    LL ans = 1LL;
    for(auto x: prime){
        ans *= x.s + 1;
        ans %= MOD;
    } cout << ans;
 
    ans = 1LL;
    for(auto x: prime){
        LL GP = pow(x.f, x.s + 1) % MOD;
        LL inv = pow(x.f - 1, MOD - 2) % MOD;
 
        ans = ans * (((GP-1) * inv) % MOD) % MOD;
    } cout << ' ' << ans;
 
    ans = 1LL;
    LL num1=1;
    LL flag=0;
    for(int i=0;i<n;i++)
    {
        if(prime[i].s%2==1 && flag==0)
        {
            num1*=((prime[i].s+1)/2);
            num1%=MOD - 1;
            flag=1;
        }
        else
        {
            num1*=(prime[i].s+1) % (MOD - 1);
            num1%= (MOD - 1);
        }
    }
    if(flag==0)
    {
        for(int i=0;i<n;i++)
        {
            prime[i].s /= 2;
        }
    }
    LL number=1;
    for(int i=0;i<n;i++)
    {
        number *= pow(prime[i].f, prime[i].s);
        number %= MOD;
    }
    ans = pow(number,num1);
 
    cout << ' ' << ans;
}
```

## Prime Multiples [problem](https://cses.fi/problemset/task/2185)
```markdown
題目: 

- 給定一個整數 n 和 k 個質數 a₁, a₂, ..., aₖ。
- 問從 1 到 n 中，有多少整數是這些質數的倍數？
- 即：有幾個整數 i ∈ [1, n] 滿足 i mod aⱼ = 0 for some j。
```
``` markdown
解法 : 

### 1. 容斥原理 + 枚舉子集：
   - 題目要求的是 union：|A₁ ∪ A₂ ∪ ... ∪ Aₖ|。
   - 使用容斥原理：
     - 每個非空子集 S 對應的貢獻為：
       - (+1)^|S| × floor(n / lcm(S))。
   - 所以對所有子集 mask，計算其 lcm，並將貢獻加總：
     - 若子集大小為奇數 → 加；
     - 若子集大小為偶數 → 減。

---

### 2. 處理 overflow：
   - lcm(a₁, a₂, ..., aⱼ) 容易爆 long long。
   - 因此在乘法前判斷：`prod > n / a[i]` 則提早跳出（避免爆炸）。
   - 此技巧保證運算過程安全。

```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll n;
    int k;
    cin >> n >> k;
 
    vector<ll> a(k);
    for (int i = 0; i < k; ++i) cin >> a[i];
 
    ll ans = 0;
 
    // 枚舉非空子集
    for (int mask = 1; mask < (1 << k); ++mask) {
        ll prod = 1;
        bool overflow = false;
 
        for (int i = 0; i < k; ++i) {
            if ((mask >> i) & 1) {
                if (prod > n / a[i]) {
                    overflow = true;
                    break;
                }
                prod *= a[i];
            }
        }
 
        if (overflow) continue;
 
        int bits = __builtin_popcount(mask);
        if (bits % 2 == 1)
            ans += n / prod;
        else
            ans -= n / prod;
    }
 
    cout << ans << '\n';
}
```

## Counting Coprime Pairs [problem](https://cses.fi/problemset/task/2417)
```markdown
題目: 

- 給定一個長度為 n 的整數陣列，問有多少對數對 (i, j) 滿足：
  - 1 ≤ i < j ≤ n，且 gcd(a[i], a[j]) = 1。
- 也就是要計算總共有哪些互質的數對。
```
``` markdown
解法 : 

### 1. 容斥 + 穆比烏斯函數（Mobius function）：
   - 如果我們能算出 gcd(a[i], a[j]) = d 的數對有幾對，就能透過容斥來求出 gcd = 1 的情況。
   - 令 sum[d] 表示陣列中是 d 的倍數的數量。
   - 則 gcd(x, y) 為 d 的數對總數為 C(sum[d], 2)。

---

### 2. 穆比烏斯反演計算互質對數：
   - 使用 Mobius function μ(d)，可得：
     - 互質對數 = ∑_{d=1}^{max} μ(d) × C(sum[d], 2)
     - 其中 C(sum[d], 2) = sum[d] × (sum[d]−1)/2

---

### 3. 實作步驟：
   - 使用線性篩預處理 μ 值。
   - cnt[x]：記錄每個值 x 出現次數。
   - sum[d]：統計所有是 d 的倍數的數有幾個。
   - 枚舉每個 d，若 μ(d) ≠ 0，累加 μ(d) × C(sum[d], 2)
   - 最後得到所有互質對數量。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 1e6 + 5;
 
int n, a[MAX], cnt[MAX], mu[MAX];
ll sum[MAX];
 
void getMobius() {
    vector<int> prime;
    vector<bool> isPrime(MAX, true);
    mu[1] = 1;
    for (int i = 2; i < MAX; ++i) {
        if (isPrime[i]) {
            prime.push_back(i);
            mu[i] = -1;
        }
        for (int p : prime) {
            if (i * p >= MAX) break;
            isPrime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = mu[i] * mu[p];
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        cnt[nums[i]]++;
    }
 
    getMobius();
 
    for (int d = 1; d < MAX; ++d)
        for (int m = d; m < MAX; m += d)
            sum[d] += cnt[m];
 
    ll total = 0;
    for (int d = 1; d < MAX; ++d) {
        if (mu[d] == 0) continue;
        ll pairs = sum[d] * (sum[d] - 1) / 2;
        total += mu[d] * pairs;
    }
 
    cout << total << '\n';
}
```

## Next Prime [problem](https://cses.fi/problemset/task/3396)
```markdown
題目: 

- 給定 t 筆查詢，每筆為一個整數 n。
- 對每筆查詢，輸出比 n 大的最小質數。
- 注意 n 的數值可以非常大（最大為 2^63−1），需要一個快速且準確的質數判定方法。
```
``` markdown
解法 : 

### 1. 使用 Miller-Rabin 質數測試（確定版）：
   - 對於 64-bit 整數，可以使用特定 base 的 Miller-Rabin 測試組合，達到**確定性質數判定**。
   - 測試流程：
     - 把 n−1 寫成 d × 2^r。
     - 驗證 base^d ≡ 1 或 base^{d×2^i} ≡ −1（mod n）是否成立。
     - 若都不成立，n 為合數。

---

### 2. 快速冪（模乘時使用 __int128）：
   - 因為質數 n 可能接近 2^63−1，乘法需避免 overflow。
   - 使用 `(__int128)` 來保證乘法過程中不會超界。

---

### 3. 搜尋邏輯：
   - 從 n+1 開始暴力遞增，直到找到第一個 isPrime(n) 為 true 的數，即為答案。
   - 由於 Miller-Rabin 判定極快，整體效能可接受。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// 快速冪 (a^b mod m)
ll qpow(ll a, ll b, ll m) {
    ll res = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (ll)((__int128)res * a % m);
        a = (ll)((__int128)a * a % m);
        b >>= 1;
    }
    return res;
}
 
// Miller-Rabin 單次測試
bool check(ll n, ll base) {
    if (n % base == 0) return false;
    ll d = n - 1;
    int r = 0;
    while ((d & 1) == 0) d >>= 1, r++;
 
    ll x = qpow(base, d, n);
    if (x == 1 || x == n - 1) return true;
 
    for (int i = 1; i < r; ++i) {
        x = (ll)((__int128)x * x % n);
        if (x == n - 1) return true;
    }
    return false;
}
 
// 確定版質數測試（64-bit 安全）
bool isPrime(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
 
    static const ll bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll base : bases) {
        if (base >= n) break;
        if (!check(n, base)) return false;
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        ++n;
        while (!isPrime(n)) ++n;
        cout << n << '\n';
    }
}
```

## Binomial Coefficients [problem](https://cses.fi/problemset/task/1079)
```markdown
題目: 

- 給定多組查詢，每次給你整數 a 和 b，要求你計算：
  - C(a, b) = a! / (b! × (a − b)!) mod 10^9+7
```
``` markdown
解法 : 

### 1. 組合數公式：
   - C(a, b) = a! / (b!(a−b)!)。
   - 由於 MOD 是質數，可以使用**費馬小定理**處理除法：
     - x / y ≡ x × y^(MOD−2) (mod MOD)

---

### 2. 實作細節：
   - 預先計算 0 到 10^6 的階乘表 `table[i] = i! mod MOD`
   - 每次查詢時：
     - 先取 table[a]。
     - 再乘上 table[b] 的乘法逆元。
     - 再乘上 table[a−b] 的乘法逆元。
   - 時間複雜度：
     - 前處理：O(N)
     - 每次查詢：O(log MOD)（快速冪取 inverse）

---

### 3. 注意事項：
   - 當 b = 0 或 b = a 時，C(a, b) = 1，自然地這套公式仍然適用。
   - 使用快速冪 pow(base, MOD−2) 處理模逆元，確保效能與正確性。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main(){
    fastio;
    int t;
    cin >> t;
    vector<LL> table(1e6 + 10, 1LL);
    for(LL i = 1LL; i <= 1e6; ++i){
        table[i] = (table[i - 1LL] * i) % MOD;
    }
 
    while(t--){
        LL a, b;
        cin >> a >> b;
        LL inv1 = pow(table[b], MOD - 2LL);
        LL inv2 = pow(table[a - b], MOD - 2LL);
        cout << ((table[a] * inv1 % MOD)* inv2 % MOD) << '\n';
    }
}
```

## Creating Strings II [problem](https://cses.fi/problemset/task/1079)
```markdown
題目: 

- 給定一個小寫字母組成的字串 s。
- 請你計算有多少種不同的排列方式（字典順序不限）。
- 最後答案對 10^9+7 取模。
```
``` markdown
解法 : 

### 1. 排列組合公式：
   - 假設字串長度為 n，且每個字母出現次數為 freq₁, freq₂, ..., freqₖ。
   - 那麼總排列數為：
     - n! / (freq₁! × freq₂! × ... × freqₖ!)
   - 因為涉及除法，需要使用**模逆元**處理：
     - x / y ≡ x × y^(MOD−2) (mod MOD)

---

### 2. 實作細節：
   - 預先計算階乘表 table[i] = i! mod MOD。
   - 統計每個字母出現次數 vocab[i]。
   - 計算：
     - 分子為 table[n]
     - 每個 freq[i]! 取模後再取 inverse，相乘進去。
   - 時間複雜度：
     - O(N + 26logMOD)，適用於長度最多 1e6 的情況。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main(){
    fastio;
    vector<LL> table(1e6 + 10, 1LL);
    for(LL i = 1LL; i <= 1e6; ++i){
        table[i] = (table[i - 1LL] * i) % MOD;
    }
    
    string input;
    cin >> input;
    vector<LL> vocab(26, 0LL);
    for(int i = 0; input[i]; ++i){
        vocab[input[i] - 'a']++;
    }
 
    LL ans = table[input.length()];
    for(int i = 0; i < 26; ++i){
        if(vocab[i] == 0)
            continue;
        LL inv = pow(table[vocab[i]], MOD - 2);
        ans = (ans * inv) % MOD;
    } 
    cout << ans << '\n';
}
```

## Distributing Apples [problem](https://cses.fi/problemset/task/1716)
```markdown
題目: 

- 有 m 顆蘋果要分給 n 個小孩，每個小孩可以拿 0 顆以上。
- 問有幾種不同的分法（不同分配順序視為不同分法）。
- 最後答案對 10^9+7 取模。
```
``` markdown
解法 : 

### 1. 轉換為組合數問題：
   - 問題等價於：
     - 把 m 顆蘋果放入 n 個桶子中，每桶可為 0。
     - 這是經典「**整數劃分 + 重複組合**」問題。
   - 對應公式為：
     - C(n + m − 1, m)
     - 選 m 個蘋果要插入 n−1 個隔板（可重複）

---

### 2. 組合數計算：
   - 使用組合公式：
     - C(a, b) = a! / (b! × (a − b)!)
   - 預先算出階乘表 table[i]。
   - 使用快速冪處理除法模逆：
     - y^(-1) ≡ y^(MOD−2) mod MOD
   - 最終答案為：
     - table[n+m−1] × inv(table[m]) × inv(table[n−1])
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
bool cmp(pair<pLL, LL> a, pair<pLL, LL> b){
    if(a.f.f == b.f.f){
        return a.f.s > b.f.s;
    } return a.f.f < b.f.f;
}
 
bool cmp(pLL a, pLL b){
    return (a.f == b.f) ? a.s > b.s : a.f < b.f;
}
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main(){
    fastio;
    vector<LL> table(2e6 + 10, 1LL);
    for(LL i = 1LL; i <= 2e6; ++i){
        table[i] = (table[i - 1LL] * i) % MOD;
    }
    LL n, m;
    cin >> n >> m;
 
    LL ans = table[n + m - 1];
    cout << ((ans * pow(table[m], MOD - 2) % MOD) * pow(table[n - 1], MOD - 2) % MOD)<< '\n';
}
```

## Christmas Party [problem](https://cses.fi/problemset/task/1717)
```markdown
題目: 

- 有 n 個人參加聖誕派對，每個人可以選擇：
  - 要和某個人互相交換禮物（兩人一組），或
  - 不參與交換。
- 每人最多參加一組，問總共有幾種不同的分組方式（mod 10^9+7）。
```
``` markdown
解法 : 

### 1. 將問題轉換為「錯排（Derangement）」類型：
   - 這是一個經典的「**容斥 + 配對**」動態規劃問題。
   - 定義 D[i] 為 i 個人能產生的有效配對方案數。
   - 遞推關係：
     - D[1] = 0（1 個人無法成對）
     - D[2] = 1（只有 1 種互換）
     - D[n] = (n−1) × (D[n−1] + D[n−2])
       - 選一人 A，有兩種情況：
         1. A 和某人配對：剩下 n−2 人問題轉為 D[n−2]
         2. A 不配對：剩下 n−1 人問題轉為 D[n−1]

---

### 2. 實作細節：
   - 使用動態規劃陣列 D[] 記錄答案。
   - 每次都對 MOD 取模避免 overflow。
   - 時間與空間複雜度：O(n)
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main(){
    fastio;
    int n;
    cin >> n;
    vector<long long> D(n + 1);
    D[1] = 0;
    D[2] = 1;
    for(int i=3;i<=n;i++) {
        D[i] = (i-1) * (D[i-1] + D[i-2]) % MOD;
    }
    cout << D[n] << '\n';
}
```

## Permutation Order [problem](https://cses.fi/problemset/task/3397)
```markdown
題目: 

- 有兩種查詢操作，共 t 筆：
  1. 給你 n 和 k，請你輸出在所有 n! 個排列中字典序第 k 小的排列。
  2. 給你一個 n 的排列，請你輸出它在所有排列中的字典序排名（從 1 開始）。
```
``` markdown
解法 : 

### 1. 查詢類型 1：第 k 小的排列
   - 這是**康托展開反推（Cantor Unranking）**的問題。
   - 對於長度 n 的排列：
     - 每一段有 (n−1)! 種開頭選法。
     - 找到 k 屬於哪個區段後，遞迴解剩下的部分。
   - 時間複雜度：O(n^2)，使用 table[] 來紀錄剩餘可選數字。

---

### 2. 查詢類型 2：給定排列求排名
   - 這是**康托展開（Cantor Ranking）**的問題。
   - 對於每個位置，計算目前未用數中有多少比當前值小的。
     - 計算這些小值能形成多少個排列數，加總即為排名。
   - 最後記得要加 1，因為題目要求從 1 開始算排名。

---

### 3. 技術細節與實作
   - 需用一個 table[] 或 bit[] 來記錄哪些數字已經被選過。
   - 預處理 factorial：最大值約到 20! 以內。
   - 注意康托展開與反展開都需避免重複計數與 index 錯誤。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
LL findKth(LL n, vector<LL> perm){
    LL ret = 0, factorial = 1;
    for(int i = 1; i<n; ++i){
        factorial *= i;
    }
 
    vector<LL> table(n + 1, 1);
    for(int i = 0; i < n - 1; ++i){
        int cnt = 0;
        for(int j = 1; j <= perm[i]; ++j){
            cnt += table[j];
        } table[perm[i]] = 0;
        ret += (cnt - 1) * factorial;
        factorial /= (n - i - 1);
    } return ret;
}
 
vector<LL> getKth(LL n, LL k){
    if(n == 1){
        return vector<LL>(1, k);
    }
    LL section = 1;
    for(LL i = 1; i < n; ++i){
        section *= i;
    }
    vector<LL> ret;
    for(LL i = 1; i <= n; ++i){
        if(k <= section * (i)){
            ret = getKth(n - 1, k - (section * (i-1)));
            ret.push_back(i);
            break;
        }
    } return ret;
}
 
int main(){
    fastio;
    int t;
    cin >> t;
    while(t--){
        int cmd;
        cin >> cmd;
        if(cmd == 1) {
            LL n, k;
            cin >> n >> k;
            vector<LL> perm = getKth(n, k);
            reverse(perm.begin(), perm.end());
            vector<LL> table(n + 1, 1);
            for(auto &e: perm){
                for(int i = 1, cnt = 0; i <= n; ++i){
                    if(cnt + table[i] == e){
                        e = i;
                        table[i] = 0;
                        break;
                    } cnt+= table[i];
                }
            }
 
            for(auto e: perm){
                cout << e << ' ';
            } cout << '\n';
        } else {
            int n;
            cin >> n;
            vector<LL> perm(n);
            for(auto &e: perm)
                cin >> e;
            cout << findKth(n, perm) + 1 << '\n';
        }
    }
}
```

## Permutation Rounds [problem](https://cses.fi/problemset/task/3398)
```markdown
題目: 

- 給定一個長度為 N 的排列 perm[1..N]，定義一場遊戲如下：
  - 每次從一個尚未被拜訪的點開始，沿著 perm 的映射跳，直到回到起點，形成一個 cycle。
- 問你：**所有 cycle 長度的最小公倍數（LCM）是多少？**
- 輸出對 10^9+7 取模的結果。
```
``` markdown
解法 : 

### 1. 尋找 cycle 長度：
   - 每個元素剛好出現在一個 cycle 中。
   - 使用 DFS 或 while-loop 掃描 permutation，記錄每個 cycle 的長度 len。
   - 對所有 len 做 LCM。

---

### 2. 如何高效地取模 LCM？
   - 直接算 LCM 會爆 long long，因此將每個長度分解質因數：
     - LCM(a, b, ...) = 乘上所有質因數的最大次方。
   - 對每個長度做質因數分解，並用 `map<int, int>` 存每個質因數的最高次方。

---

### 3. 實作細節：
   - 使用埃氏篩先求出質數表（primes[]）。
   - 對每個 cycle 的長度進行分解質因數，更新每個質數的最大指數。
   - 最後重建答案：
     - ans = ∏ (p^e) for each (p, e) in map。
     - 用快速乘法處理模 10^9+7。
```

``` cpp
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int maxN = 2e5+1;
const ll MOD = (ll) 1e9+7;
 
int N, perm[maxN];
bool vis[maxN], is_prime[maxN];
vector<int> primes;
map<int,int> ans;
 
void init_primes(){
    for(int i = 2; i < maxN; i++)   is_prime[i] = true;
    for(int i = 2; i < maxN; i++){
        if(is_prime[i]){
            primes.push_back(i);
            for(int j = 2 * i; j < maxN; j += i)
                is_prime[j] = false;
        }
    }
}
 
int dfs(int u){
    vis[u] = true;
    if(vis[perm[u]])    return 1;
    return dfs(perm[u]) + 1;
}
 
void prime_factor(int x){
    for(int i = 0; i < (int) primes.size() && primes[i] <= x; i++){
        int p = primes[i];
        int num_divisions = 0;
        while(x % p == 0){
            x /= p;
            num_divisions++;
        }
 
        if(num_divisions > 0)
            ans[p] = max(ans[p], num_divisions);
    }
}
 
int main(){
    init_primes();
 
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &perm[i]);
 
    for(int u = 1; u <= N; u++){
        if(!vis[u]){
            int len = dfs(u);
            prime_factor(len);
        }
    }
 
    ll prod = 1;
    for(auto const& [prime, power] : ans)
        for(int i = 0; i < power; i++)
            prod = (prod * prime) % MOD;
    printf("%lld\n", prod);
}
```

## Bracket Sequences I [problem](https://cses.fi/problemset/task/2064)
```markdown
題目: 

- 給定一個整數 n，問有多少個長度為 n 的合法括號序列。
- 括號序列只能包含 `()`，且必須合法（左括號數量等於右括號，且任意前綴中左括號不少於右括號）。
- 輸出對 10^9+7 取模的結果。
```
``` markdown
解法 : 

### 1. 卡特蘭數公式（Catalan Number）：
   - 合法括號序列數量對應第 k 個卡特蘭數（k = n/2）：
     - Cₖ = C(2k, k) / (k + 1)
     - 即：Cₖ = (2k)! / (k!(k+1)!)
   - 若 n 為奇數，直接輸出 0。

---

### 2. 快速計算組合數：
   - 預先計算 fact[i] = i! mod MOD，以及其反元素 invfact[i]。
   - 使用快速冪計算模反元素：
     - a^(-1) ≡ a^(MOD - 2) mod MOD（MOD 為質數時）

---

### 3. 實作技巧：
   - `fact[]` 與 `invfact[]` 須開到 2e6+5，避免 overflow。
   - 注意不要在模數下做除法，應使用乘上逆元。
   - 最終答案為：
     - catalan = C(2k, k) × inv(k + 1) mod MOD
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAX = 2e6 + 5;  // 要開到 2 * 1e6
const ll MOD = 1e9 + 7;
 
ll fact[MAX], invfact[MAX];
 
// 快速冪
ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
 
// 組合數
ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}
 
// 初始化階乘與反元素
void init() {
    fact[0] = invfact[0] = 1;
    for (int i = 1; i < MAX; i++)
        fact[i] = fact[i - 1] * i % MOD;
    invfact[MAX - 1] = power(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 1; i--)
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
}
 
int main() {
    int n;
    cin >> n;
 
    if (n % 2 == 1) {
        cout << 0 << '\n';
        return 0;
    }
 
    init();
    int k = n / 2;
    ll catalan = C(2 * k, k) * power(k + 1, MOD - 2) % MOD;
    cout << catalan << '\n';
}
```

## Bracket Sequences II [problem](https://cses.fi/problemset/task/2187)
```markdown
題目: 

- 給定一個整數 n（括號總長度）和一段長度為 k 的合法括號前綴字串 prefix。
- 請問：在補上剩下的 n − k 個括號後，有多少種方法可以形成一個**完整合法**的括號序列？
- 所有結果對 10^9+7 取模。
```
``` markdown
解法 : 

### 1. 前綴合法性檢查：
   - 若 prefix 本身不合法（右括號比左括號多），直接輸出 0。
   - 合法前綴定義：任意前綴中左括號數 ≥ 右括號數。

---

### 2. 剩餘括號補法計算：
   - 計算剩餘括號數 rem = n − k。
   - 假設目前 balance = open − close（還欠 balance 個 `)` 才平衡）。
   - 想要形成合法序列，需保證：
     - 剩下的括號能補足這個 balance，並形成完整對。
     - 所以：(rem + balance) 必須為偶數，且 rem ≥ balance。

---

### 3. 將問題轉為 Catalan-like：
   - 設 a 為要補的左括號個數，b 為要補的右括號個數：
     - a = (rem + balance) / 2
     - b = rem − a
   - 最後用標準公式計算合法括號數：
     - 答案 = C(a + b, a) − C(a + b, a + 1)
       - C(a + b, a): 所有的左右配對可能
       - C(a + b, a + 1): 不合法的括號（會出現過多右括號）
   - 這是經典的「Catalan 數列在有限前綴條件下的應用」

---

### 4. 計算組合數技巧：
   - 使用預處理 factorial 和 inverse factorial 表
   - 所有除法都改為乘上逆元（MOD 為質數）
   - C(n, k) = fact[n] × invfact[k] × invfact[n − k] mod MOD
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MOD = 1e9 + 7;
const int MAX = 2e6 + 5; // 要夠大支援最大 n = 1e6
 
ll fact[MAX], invfact[MAX];
 
ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
 
void init() {
    fact[0] = invfact[0] = 1;
    for (int i = 1; i < MAX; i++)
        fact[i] = fact[i - 1] * i % MOD;
    invfact[MAX - 1] = power(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 1; i--)
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
}
 
ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}
 
int main() {
    init();
 
    int n;
    string prefix;
    cin >> n >> prefix;
 
    int k = prefix.length();
    int open = 0, close = 0;
 
    for (char c : prefix) {
        if (c == '(') open++;
        else close++;
        if (close > open) {
            cout << 0 << '\n';
            return 0; // 不合法：右括號比左括號還多
        }
    }
 
    int rem = n - k;
    int balance = open - close;
 
    // 如果剩下不是偶數個，無法湊成合法對
    if ((rem + balance) % 2 != 0 || rem < balance) {
        cout << 0 << '\n';
        return 0;
    }
 
    int a = (rem + balance) / 2; // 要補的左括號
    int b = rem - a;             // 要補的右括號
 
    // 使用 Catalan-like 公式：C(a + b, a) - C(a + b, a + 1)
    ll ans = (C(a + b, a) - C(a + b, a + 1) + MOD) % MOD;
    cout << ans << '\n';
}
```

## Counting Necklaces [problem](https://cses.fi/problemset/task/2209)
```markdown
題目: 

- 給定整數 n（珠子的數量）和 m（每顆珠子可選的顏色數），
- 問有多少種不同的「項鍊塗色方式」？
  - 項鍊是環狀結構，若透過旋轉可以互相對應，則視為相同方案。
- 結果對 10^9+7 取模。
```
``` markdown
解法 : 

### 1. Burnside 引理（Burnside’s Lemma）：
   - 我們要算的是：在 n 個位置中，有多少種 m 顏色的上色方法，對所有旋轉情況下不重複計數。
   - 根據 Burnside 引理：
     - ans = (1/n) × ∑_{r=0}^{n−1} m^gcd(n, r)
       - r 表示旋轉 r 位
       - gcd(n, r) 表示固定點數（不變的位置）
       - m^gcd(n, r)：固定後每個 cycle 可以隨意染色

---

### 2. 快速冪與模逆元：
   - 因為每次都需要計算 m^gcd(n, r)，使用快速冪加速。
   - 最後的除法 `(sum / n) mod MOD`，改為乘上 n 的乘法逆元：
     - 使用 `mod_pow(n, MOD − 2)` 來計算。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
 
// 快速冪 m^k % MOD
ll mod_pow(ll m, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * m % MOD;
        m = m * m % MOD;
        k >>= 1;
    }
    return res;
}
 
// m^gcd(n, r) 對所有 r=0 到 n-1 做和，再除以 n
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll n, m;
    cin >> n >> m;
 
    ll sum = 0;
    for (ll r = 0; r < n; ++r) {
        ll g = __gcd(n, r);
        sum = (sum + mod_pow(m, g)) % MOD;
    }
 
    // 除以 n，相當於乘上 n 的乘法反元素
    ll inv_n = mod_pow(n, MOD - 2);
    ll ans = sum * inv_n % MOD;
    cout << ans << '\n';
}
```

## Counting Grids [problem](https://cses.fi/problemset/task/2210)
```markdown
題目: 

- 給定一個 n×n 的網格，每格可填入 0 或 1（共 2 種顏色），
- 兩個填色方案若經過旋轉（0°, 90°, 180°, 270°）後一致，則視為**同一種**填法。
- 問有多少種不同的填色方式，mod 10^9+7。
```
``` markdown
解法 : 

### 1. Burnside 引理（Burnside’s Lemma）：
   - 要計算在所有對稱操作下的不重複配置數量，可使用 Burnside 引理：
     - ans = (1/|G|) × ∑_{g∈G} Fix(g)
     - G：所有操作（本題為旋轉 0°, 90°, 180°, 270°）
     - Fix(g)：在操作 g 下不變的塗色方案數

---

### 2. 旋轉類型的固定點數：
   - **0° (恆等變換)**：全部固定，2^(n²)
   - **180°**：每對對稱格子需一致 ⇒ 2^((n² + 1)/2)
   - **90° & 270°**：每 4 個格子形成 cycle ⇒ 2^((n² + 3)/4)
   - 最後總和為：  
     - total = (term0 + 2×term90_270 + term180) / 4

---

### 3. 實作技巧：
   - 使用快速冪計算模下的大次方。
   - 除以 4 使用乘法逆元：`modpow(4, MOD−2)`。
   - 注意使用 `(n² + 1)/2` 和 `(n² + 3)/4` 是為了確保整數除法正確。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll MOD = 1e9 + 7;
 
// 快速冪
ll modpow(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}
 
int main() {
    ll n;
    cin >> n;
    ll n2 = n * n;
 
    ll term0 = modpow(2, n2);
    ll term180 = modpow(2, (n2 + 1) / 2);
    ll term90_270 = modpow(2, (n2 + 3) / 4);
 
    ll total = (term0 + 2 * term90_270 + term180) % MOD;
    total = total * modpow(4, MOD - 2) % MOD; // 除以 4
 
    cout << total << "\n";
    return 0;
}
```

## Fibonacci Numbers [problem](https://cses.fi/problemset/task/1722)
```markdown
題目: 

- 給定一個整數 k，請你輸出 Fibonacci(k) 的值（mod 10^9+7）。
- Fibonacci 定義如下：
  - F(0) = 0, F(1) = 1
  - F(k) = F(k−1) + F(k−2) for k ≥ 2
- 限制：0 ≤ k ≤ 10^18，需要高效計算。
```
``` markdown
解法 : 

### 1. 快速矩陣冪（Matrix Exponentiation）：
   - 對於 Fibonacci 數列，可以用轉移矩陣表示為：
     - [F(k)  ]   = [1 1]^k × [F(1)]
     - [F(k−1)]     [1 0]     [F(0)]
   - 因此，我們只需要將矩陣 A = [[1,1],[1,0]] 快速冪到 k−1 次方，即可得到 F(k)。

---

### 2. 優化細節：
   - 使用 2×2 矩陣乘法實作。
   - 快速冪時間複雜度為 O(log k)，可應對高達 10^18 的 k。
   - 注意要模 MOD = 10^9+7，避免 overflow。

---

### 3. 特殊情況：
   - 若 k = 0，直接輸出 0。
   - 若 k = 1 或 2，F(k) = 1，可直接輸出。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
 
struct Mat {
    ll m[2][2] = {{0,0},{0,0}};
 
    Mat operator*(const Mat &b) const {
        Mat r;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    r.m[i][j] = (r.m[i][j] + m[i][k]*b.m[k][j]%MOD)%MOD;
        return r;
    }
};
 
Mat qpow(Mat a, ll k) {
    Mat r; // 單位矩陣
    r.m[0][0]=r.m[1][1]=1;
    while(k) {
        if(k&1) r = r * a;
        a = a * a;
        k >>= 1;
    }
    return r;
}
 
int main() {
    ll k;
    cin >> k;
    if(k == 0){
        cout << 0 << endl;
        return 0;    
    }
    if(k==1 || k==2) {
        cout << 1 << endl;
        return 0;
    }
    Mat A;
    A.m[0][0]=A.m[0][1]=A.m[1][0]=1;
    Mat res = qpow(A, k-2);
    ll ans = (res.m[0][0] + res.m[0][1]) % MOD;
    cout << ans << endl;
}
```

## Throwing Dice [problem](https://cses.fi/problemset/task/1096)
```markdown
題目: 

- 有一顆六面骰子（面值為 1~6），你每次丟出來的點數會累加。
- 問你總共有幾種方式讓點數總和正好為 n。
- 結果對 10^9+7 取模。
```
``` markdown
解法 : 

### 1. 定義與遞推關係：
   - 定義 dp[n] 為總和為 n 的合法組合數。
   - 轉移式：
     - dp[n] = dp[n−1] + dp[n−2] + ... + dp[n−6]
   - 初始條件：
     - dp[0] = 1（什麼都不丟就是一種方式）
     - dp[1] = 1, dp[2] = 2, dp[3] = 4, ..., dp[6] = 32（可直接列舉）

---

### 2. 矩陣快速冪優化：
   - 因為轉移式是線性遞推，最多依賴前六項，因此可以使用**矩陣快速冪**優化成 O(log n)。
   - 狀態設為長度為 6 的向量 dp[n], dp[n−1], ..., dp[n−5]。
   - 使用 6×6 的轉移矩陣 T，使得：
     - T^k × base = dp[n]，其中 base 是 dp[6], dp[5], ..., dp[1]

---

### 3. 實作細節：
   - 若 n ≤ 6，直接輸出對應初始值。
   - 否則：
     - 對轉移矩陣 T 做 T^(n−6)
     - 再與 base 向量做乘法，取第 0 項即為 dp[n]
   - 所有乘法與加法都取模，確保不爆 long long。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
const int K = 6;
 
using Matrix = vector<vector<ll>>;
 
Matrix mul(Matrix& a, Matrix& b) {
    Matrix res(K, vector<ll>(K));
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            for (int k = 0; k < K; ++k)
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD;
    return res;
}
 
Matrix power(Matrix base, ll exp) {
    Matrix res(K, vector<ll>(K));
    for (int i = 0; i < K; ++i)
        res[i][i] = 1;
    while (exp) {
        if (exp & 1)
            res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}
 
int main() {
    ll n;
    cin >> n;
 
    if (n <= 6) {
        // 手動 dp 初始化
        vector<ll> base = {1, 2, 4, 8, 16, 32};
        cout << base[n - 1] << '\n';
        return 0;
    }
 
    // base dp[1~6]
    vector<ll> base = {1, 2, 4, 8, 16, 32};
 
    // 建立轉移矩陣 T
    Matrix T(K, vector<ll>(K));
    T[0] = {1,1,1,1,1,1};
    for (int i = 1; i < K; ++i)
        T[i][i-1] = 1;
 
    Matrix Tn = power(T, n - 6);
 
    ll result = 0;
    for (int i = 0; i < K; ++i)
        result = (result + Tn[0][i] * base[5 - i]) % MOD;
 
    cout << result << '\n';
}
```

## Graph Paths I [problem](https://cses.fi/problemset/task/1723)
```markdown
題目: 

- 給定一張 n 個點、m 條有向邊的圖，以及一個整數 k。
- 問從點 1 出發，到點 n，走恰好 k 步（邊）的不同路徑總數。
```
``` markdown
解法 : 

### 1. 觀察：
   - 要從 1 到 n 的路徑，且長度正好是 k。
   - 這可以轉化成一個典型的**矩陣乘法遞推問題**。
   - 若 A 為鄰接矩陣，則 A^k[i][j] 表示從 i 到 j 恰好走 k 步的路徑數。

---

### 2. 矩陣快速冪：
   - 使用 n×n 矩陣 A 表示圖的鄰接關係。
     - A[i][j] 為從 i 到 j 有幾條邊（可重邊）。
   - 要計算 A^k 的結果，使用**快速矩陣冪**：
     - 時間複雜度：O(n^3 × log k)
   - 最後輸出 A^k[1][n] 即為答案。

---

### 3. 技術細節：
   - 自定義結構 Mat 支援乘法運算與初始化。
   - 初始化 r 為單位矩陣，用於快速冪起始值。
   - 注意所有運算都要取模 MOD = 10^9+7。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int N = 110;
 
int n;
struct Mat {
    ll m[N][N];
    Mat() { memset(m, 0, sizeof m); }
    Mat operator*(const Mat &b) const {
        Mat r;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    r.m[i][j] = (r.m[i][j] + m[i][k]*b.m[k][j]%MOD)%MOD;
        return r;
    }
};
 
Mat qpow(Mat a, ll k) {
    Mat r;
    for(int i=1;i<=n;i++) r.m[i][i]=1;
    while(k) {
        if(k&1) r = r*a;
        a = a*a;
        k >>=1;
    }
    return r;
}
 
int main() {
    int m;
    ll k;
    cin >> n >> m >> k;
    Mat A;
    while(m--) {
        int u,v;
        cin >> u >> v;
        A.m[u][v]++;
    }
    A = qpow(A, k);
    cout << A.m[1][n] << endl;
}
```

## Graph Paths II [problem](https://cses.fi/problemset/task/1724)
```markdown
題目: 

- 給定一張有向圖（n 個點，m 條邊），每條邊有非負權重。
- 問：從節點 1 出發到節點 n，恰好經過 k 條邊的**最短路徑長度**是多少？
- 若無法在恰好 k 步內抵達，輸出 -1。
```
``` markdown
解法 : 

### 1. 觀察與建模：
   - 我們要找的是：從點 1 到點 n，經過**恰好 k 條邊**的最短路徑。
   - 傳統 Dijkstra / Bellman-Ford 不適用於「剛好 k 步」的限制。
   - 解法是：**最短路徑矩陣 + min-plus 矩陣乘法 + 快速冪**。

---

### 2. 定義與操作：
   - 定義鄰接矩陣 A，其中 A[i][j] 為從 i 到 j 的邊權（若存在，否則為 ∞）。
   - 那麼：
     - A^1[i][j] 表示：從 i 到 j 經過 1 條邊的最短路。
     - A^2[i][j] 表示：從 i 到 j 經過 2 條邊的最短路。
     - ...
     - A^k[i][j] 表示：從 i 到 j 經過 k 條邊的最短路。
   - 所以，我們只需計算 A^k，然後輸出 A^k[1][n]。

---

### 3. 快速矩陣冪（min,+ 乘法）：
   - 與一般矩陣乘法不同，我們這邊使用：
     - r[i][j] = min over all k of (a[i][k] + b[k][j])
     - 稱為 **min-plus 矩陣乘法**。
   - 搭配快速冪計算 A^k，在 O(n³ log k) 時間內完成。

---

### 4. 特別注意：
   - 初始矩陣除了有邊的地方，其餘皆設為 INF（不能為 0！）
   - 計算過程需避免溢位：使用 64-bit 整數。
   - 最後答案若為 INF，表示無解，輸出 −1。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int N = 110;
const long long INF = 1LL << 60;
 
int n;
 
struct Mat {
    ll m[N][N];
    Mat() { 
        for(int i=0;i<N;i++) for(int j=0;j<N;j++) 
            m[i][j] = INF; 
    }
    Mat operator*(const Mat &b) const {
        Mat r;
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) 
                for(int k=1;k<=n;k++) 
                    r.m[i][j] = min(r.m[i][j], m[i][k] + b.m[k][j]);
        return r;
    }
};
 
Mat qpow(Mat a, ll k) {
    Mat r = a; k--;
    while(k) {
        if(k&1) r = r*a;
        a = a*a;
        k >>=1;
    }
    return r;
}
 
int main() {
    int m;
    ll k;
    cin >> n >> m >> k;
    Mat A;
    while(m--) {
        ll u, v, c;
        cin >> u >> v >> c;
        A.m[u][v] = min(A.m[u][v], c);
    }
    A = qpow(A, k);
    cout << (A.m[1][n] == INF ? -1 : A.m[1][n]) << endl;
}
```

## System of Linear Equations [problem](https://cses.fi/problemset/task/3154)
```markdown
題目: 

- 給定一個 n × m 的線性方程組 Ax = b（模質數 MOD）。
- 每個係數與常數項都在 0 到 MOD-1 之間，MOD 是質數（這裡為 1e9+7）。
- 需要求出一組解，如果無解則輸出 -1。
- 如果有多組解，則輸出其中任意一組（自由變數可取 0）。
```
``` markdown
解法 : 

### 1. Gaussian Elimination 模數化：
   - 將矩陣擴充成 n × (m+1)（最後一欄為常數項 b）。
   - 從左到右依序選擇主元列，透過 `modinv` 計算模反元素，使主元歸一化。
   - 使用模數下的加減乘消去其他列的該列元素。

---

### 2. 檢查無解條件：
   - 如果某一列前 m 個係數全為 0，但最後一欄不為 0，則表示 0 = 非零，無解。

---

### 3. 解的構造：
   - `where[col]` 記錄每個變數是否有主元所在的行。
   - 對於有主元的變數，解為該行最後一欄值；自由變數取 0 即可。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int MOD = 1'000'000'007;
 
int modinv(int a, int m = MOD) {
    int b = m, x = 1, y = 0;
    while (b) {
        int q = a / b;
        tie(a, b) = make_pair(b, a % b);
        tie(x, y) = make_pair(y, x - q * y);
    }
    return (x % m + m) % m;
}
 
void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
 
int main() {
    fastio();
    int n, m;
    cin >> n >> m;
    vector<vector<int>> A(n, vector<int>(m + 1)); // augmented matrix: A | b
 
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= m; ++j)
            cin >> A[i][j];
 
    vector<int> where(m, -1);
    for (int col = 0, row = 0; col < m && row < n; ++col) {
        int sel = row;
        for (int i = row; i < n; ++i)
            if (A[i][col] != 0)
                sel = i;
        if (A[sel][col] == 0) continue;
 
        swap(A[sel], A[row]);
        where[col] = row;
 
        int inv = modinv(A[row][col]);
        for (int j = 0; j <= m; ++j)
            A[row][j] = (1LL * A[row][j] * inv) % MOD;
 
        for (int i = 0; i < n; ++i) {
            if (i != row && A[i][col]) {
                int coef = A[i][col];
                for (int j = 0; j <= m; ++j) {
                    A[i][j] = (A[i][j] - 1LL * coef * A[row][j] % MOD + MOD) % MOD;
                }
            }
        }
        ++row;
    }
 
    // Check for inconsistency
    for (int i = 0; i < n; ++i) {
        bool all_zero = true;
        for (int j = 0; j < m; ++j)
            if (A[i][j]) all_zero = false;
        if (all_zero && A[i][m]) {
            cout << -1 << '\n'; // No solution
            return 0;
        }
    }
 
    vector<int> ans(m);
    for (int j = 0; j < m; ++j) {
        if (where[j] != -1)
            ans[j] = A[where[j]][m];
        else
            ans[j] = 0; // free variable
    }
 
    for (int i = 0; i < m; ++i)
        cout << ans[i] << " \n"[i == m - 1];
 
    return 0;
}
```

## Sum of Four Squares [problem](https://cses.fi/problemset/task/3355)
```markdown
題目: 

- 給定一個整數 n（多組測資）。
- 需要找到四個非負整數 a, b, c, d，使得  
  a² + b² + c² + d² = n。
- 如果存在多組解，輸出任意一組即可。
- 由於 n 的範圍相對可控，可以直接枚舉。
```
``` markdown
解法 : 

### 1. 理論背景：
   - 由拉格朗日四平方和定理可知，任意非負整數皆可表示為四個平方數之和。
   - 因此必定有解，只需要找到其中一組即可。

---

### 2. 枚舉策略：
   - 枚舉 a 從 0 到 sqrt(n)。
   - 枚舉 b 從 a 到 sqrt(n - a²)（b ≥ a 可減少重複）。
   - 枚舉 c 從 b 到 sqrt(n - a² - b²)（c ≥ b 同理）。
   - 剩下的值 rem = n - (a² + b² + c²)，判斷是否為完全平方數：
     - d = sqrt(rem)，如果 d² == rem 則找到解。

---

### 3. 複雜度分析：
   - 外層 a 枚舉到 sqrt(n)，b 枚舉到 sqrt(n)，c 枚舉到 sqrt(n)，最壞情況接
   - 近O(n^(3/2))。
   - 由於有提早終止（找到解後立即輸出並結束該測資），實際運行會快得多，適合中等
   - 範圍的 n。

---

### 4. 實作細節：
   - 為避免重複計算平方根，使用 sqrt(rem) 並檢查平方是否相等。
   - b 從 a 開始，c 從 b 開始，確保輸出非降序（符合部分題目要求或方便檢查）。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        bool done = false;
 
        for (int a = 0; a*a <= n && !done; ++a) {
            for (int b = a; a*a+b*b <= n && !done; ++b) {
                for (int c = b; a*a+b*b+c*c <= n && !done; ++c) {
                    int rem = n - (a*a+b*b+c*c);
                    int d = sqrt(rem);
                    if (d*d == rem) {
                        cout << a << " " << b << " " << c << " " << d << '\n';
                        done = true;
                        break;
                    }
                }
            }
        }
    }
}
```

## Triangle Number Sums [problem](https://cses.fi/problemset/task/3406)
```markdown
題目: 

- 定義三角形數為 tri(k) = k(k+1)/2，其中 k 為正整數。
- 對於每個輸入的 n，求最少需要幾個三角形數的和，才能表示成 n。
- 題目保證輸入範圍適合在 long long 計算內。
- 根據數論結果，任何正整數都可以用不超過 3 個三角形數表示（高斯三角形數定理）。
```
``` markdown
解法 : 

### 1. 判斷 1 個三角形數：
   - 若 n 本身是三角形數，答案為 1。
   - 判斷方法：檢查 1 + 8n 是否為完全平方數，且 sqrt(1+8n) - 1 可被 2 整除。

---

### 2. 判斷 2 個三角形數：
   - 設 l 從 1 開始，r 從最大可能的三角形數下標 max_k(n) 開始
   - （tri(max_k) ≤ n）。
 
   - 雙指針法：
     - 若 tri(l) + tri(r) == n，答案為 2。
     - 若和 < n，l++。
     - 若和 > n，r--。
   - 時間複雜度 O(k_max)，其中 k_max ≈ sqrt(2n)。

---

### 3. 判斷 3 個三角形數：
   - 若不屬於上述兩種情況，根據高斯定理可直接輸出 3。
   - 因為定理保證任何正整數皆為 3 個三角形數之和。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// 判斷是否為三角形數
bool is_tri(ll n) {
    ll d = 1 + 8 * n;
    ll sq = sqrtl(d);
    return sq * sq == d && (sq - 1) % 2 == 0;
}
 
// 找到 <= n 的最大三角形數的下標 k
ll max_k(ll n) {
    return (ll)((-1 + sqrtl(1 + 8.0 * n)) / 2);
}
 
// 計算三角形數
inline ll tri(ll k) {
    return k * (k + 1) / 2;
}
 
int solve(ll n) {
    if (is_tri(n)) return 1;
 
    ll l = 1, r = max_k(n);
    while (l <= r) {
        ll sum = tri(l) + tri(r);
        if (sum == n) return 2;
        if (sum < n) ++l;
        else --r;
    }
 
    return 3;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        cout << solve(n) << '\n';
    }
}
```

## Dice Probability [problem](https://cses.fi/problemset/task/1725)
```markdown
題目: 

- 擲一顆公平的六面骰子 n 次，每次點數為 1 到 6。
- 給定區間 [a, b]，求最後總和落在該區間內的機率。
- 輸出結果需保留 6 位小數。
```
``` markdown
解法 : 

### 1. 狀態定義：
   - dp[i][sum] = 擲 i 次骰子後，總和恰為 sum 的機率。
   - 初始條件：dp[0][0] = 1（0 次擲骰，總和為 0 的機率為 1）。

---

### 2. 狀態轉移：
   - 對於第 i 次擲骰：
   - dp[i][sum] = Σ_{face=1}^{6} dp[i-1][sum - face] / 6
   - 意思是：最後一次骰出 face，前 i-1 次的總和為 sum - face，每種點數的機率
     相等

---

### 3. 邊界條件：
   - sum 需介於 i（全部擲 1）到 6i（全部擲 6）之間，其他狀況機率為 0。
   - 在計算 dp[i][sum] 時，若 sum-face < 0 則跳過。

---

### 4. 最終答案：
   - 將 dp[n][sum] 在 sum ∈ [a, b] 範圍內的機率加總，即為答案。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define f first
#define s second
#define INF LL(1e18)
#define MOD LL((1e9) + 7)
typedef long long LL;
 
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
 
bool cmp(pair<pLL, LL> a, pair<pLL, LL> b){
    if(a.f.f == b.f.f){
        return a.f.s > b.f.s;
    } return a.f.f < b.f.f;
}
 
bool cmp(pLL a, pLL b){
    return (a.f == b.f) ? a.s > b.s : a.f < b.f;
}
 
LL pow(LL n, LL k){
    if(k == 1LL){
        return n;
    }
    if(k == 0LL){
        return 1;
    } 
    LL ret = pow(n, k >> 1) % (MOD);
    ret *= ret % MOD;
    ret %= MOD;
    if(k & 1){
        ret *= n % MOD;
        ret %= MOD;
    }return ret;
}
 
int main() {
    int n, a, b;
    cin >> n >> a >> b;
 
    vector<vector<long double>> dp(n+1, vector<long double>(6*n+1, 0));
    dp[0][0] = 1.0;
 
    for (int i = 1; i <= n; ++i) {
        for (int sum = i; sum <= 6*i; ++sum) {
            for (int face = 1; face <= 6; ++face) {
                if (sum-face >= 0)
                    dp[i][sum] += dp[i-1][sum-face] / 6.0;
            }
        }
    }
 
    long double prob = 0;
    for (int sum = a; sum <= b; ++sum)
        prob += dp[n][sum];
 
    cout << fixed << setprecision(6) << prob << endl;
}
```

## Moving Robots

## Candy Lottery

## Inversion Probability [problem](https://cses.fi/problemset/task/1728)
```markdown
題目: 

- 給定一個長度為 n 的陣列 r，r[i] 表示第 i 個元素的隨機值會均勻分布在
  [1, r[i]]。
- 定義 inversion（逆序對）為：i < j 且 a[i] > a[j]。
- 問所有可能情況下 inversion 的期望值（機率和）。
- 由於數值範圍可能導致精度誤差，本題在 C++ 使用 long double 仍可能 WA，需使用
  高精度計算。
```
``` markdown
解法 : 

### 1. 逆序對的期望公式：
   - 對每一對 (j, i)，其中 j < i，計算：
     P(a[j] > a[i]) = Σ{x=1}^{min(r[j],r[i])} P(a[i] = x) × P(a[j] > x)
   - a[i] 均勻分布在 [1, r[i]]，P(a[i] = x) = 1 / r[i]。
   - P(a[j] > x) = (r[j] - x) / r[j]，若 r[j] > x，否則為 0。

---

### 2. 化簡計算：
   - 設 m = min(r[j], r[i])。
   - Σ_{x=1}^m (r[j] - x) = m × r[j] - m(m+1)/2。
   - 機率和為：
     (a × m - m(m+1)/2) / (a × b)，其中 a = r[j], b = r[i]。

---

### 3. 精度處理：
   - 本題輸出需要 6 位小數，但中間計算涉及大量分數相加，累積誤差極大。
   - 若用 C++ double 或 long double，某些邊界測資會錯（精度不足）。
   - Python 內建 `decimal.Decimal` 支援高精度浮點計算，可以安全通過所有測資
```

``` python
from decimal import Decimal, getcontext
 
getcontext().prec = 30
 
n = int(input())
r = [0] + list(map(int, input().split()))
 
ans = Decimal(0)
 
for i in range(1, n+1):
    for j in range(1, i):
        a = r[j]
        b = r[i]
        m = min(a, b)
        s = Decimal(a*m - m*(m+1)//2)
        ans += s / Decimal(a) / Decimal(b)
 
ans = ans.quantize(Decimal('0.000001'))
 
print(ans)
```

## Stick Game [problem](https://cses.fi/problemset/task/1729)
```markdown
題目: 

- 有一堆長度為 n 的木棍，可以從中取走 p 單位長度（p 在集合 P 中）。
- 兩位玩家輪流取木棍，取走長度必須是 P 中的某一個數值。
- 無法取走合法長度的玩家輸掉遊戲。
- 要輸出對於每個初始長度 i（1 ≤ i ≤ n），先手玩家是贏家 (W) 還是輸家 (L)。
```
``` markdown
解法 : 

### 1. 遊戲定義：
   - dp[i] = true 表示當木棍長度為 i 時，先手必勝（Winning position）。
   - dp[i] = false 表示當木棍長度為 i 時，先手必敗（Losing position）。

---

### 2. 狀態轉移：
   - 對於每個長度 i，檢查是否存在一個可取的長度 p ∈ P：
     - 若 i ≥ p 且 dp[i - p] == false（取走 p 後讓對手處於必敗狀態），
     - 則 dp[i] = true。
     - 否則 dp[i] = false。
   - 這是經典的「取石子遊戲」DP，屬於巴什型博弈。

---

### 3. 初始條件：
   - dp[0] = false（沒有木棍長度時，無法取，必敗）。

---

### 4. 輸出：
   - 依序輸出 i = 1 到 n 的狀態，贏家輸出 'W'，輸家輸出 'L'。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    cin >> n >> k;
    vector<int> P(k);
    for (int i = 0; i < k; i++) cin >> P[i];
 
    vector<bool> dp(n + 1, false); // dp[i] = true if winning
 
    for (int i = 1; i <= n; i++) {
        for (int p : P) {
            if (i >= p && !dp[i - p]) {
                dp[i] = true;
                break;
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
        cout << (dp[i] ? 'W' : 'L');
    cout << '\n';
}
```

## Nim Game I [problem](https://cses.fi/problemset/task/1730)
```markdown
題目: 

- 有 n 堆石子，第 i 堆有 x_i 顆。
- 兩位玩家輪流操作，每次可以從某一堆取走任意正數顆石子。
- 無法操作的玩家輸掉遊戲。
- 給出多組測資，判斷先手玩家 ("first") 或後手玩家 ("second") 獲勝。
```
``` markdown
解法 : 

### 1. 理論背景（Nim 遊戲定理）：
   - 對所有堆的石子數做 XOR，得到 nim-sum。
   - 若 nim-sum ≠ 0，先手必勝；若 nim-sum = 0，後手必勝。

---

### 2. 為什麼成立：
   - nim-sum = 0 為必敗局（P-position）：無論先手怎麼取，都會是 nim-sum ≠ 0 
   - 的局面給對手。
  
   - nim-sum ≠ 0 為必勝局（N-position）：先手可透過操作讓局面為 nim-sum = 0

---

### 3. 演算法步驟：
   1. 初始化 xor_sum = 0。
   2. 對每個堆的石子數 x_i，xor_sum ^= x_i。
   3. 若 xor_sum ≠ 0 → "first"，否則 → "second"。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        int xor_sum = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            xor_sum ^= x;
        }
        cout << (xor_sum ? "first\n" : "second\n");
    }
}
```

## Nim Game II [problem](https://cses.fi/problemset/task/1098)
```markdown
題目: 

- 有 n 堆石子，第 i 堆有 x_i 顆。
- 兩位玩家輪流操作，每次可以從某一堆取走 1、2 或 3 顆石子。
- 無法操作的玩家輸掉遊戲。
- 多組測資，需判斷先手 ("first") 或後手 ("second") 獲勝。
```
``` markdown
解法 : 

### 1. Sprague–Grundy 理論：
   - 每一堆的局面可抽象成「取走 1、2、3 顆石子」的子遊戲。
   - Grundy 值定義：
     - G(0) = 0（無石子，必敗）。
     - G(1) = mex{ G(0) } = 1。
     - G(2) = mex{ G(1), G(0) } = 2。
     - G(3) = mex{ G(2), G(1), G(0) } = 3。
     - G(4) = mex{ G(3), G(2), G(1) } = 0。
   - 可以發現規律：G(x) = x % 4。

---

### 2. 判勝條件：
   - 計算所有堆的 Grundy 值的 XOR（nim-sum）。
   - 若 nim-sum = 0 → 後手勝。
   - 若 nim-sum ≠ 0 → 先手勝。

---

### 3. 演算法步驟：
   1. 初始化 xor_sum = 0。
   2. 對每堆石子數 x，計算 g = x % 4。
   3. xor_sum ^= g。
   4. 輸出勝者。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
// Grundy(x) = x % 4, 因為拿法是 {1, 2, 3}
int get_sg(int x) {
    return x % 4;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        int xor_sum = 0;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            xor_sum ^= get_sg(x);
        }
 
        cout << (xor_sum == 0 ? "second\n" : "first\n");
    }
}
```

## Stair Game [problem](https://cses.fi/problemset/task/1099)
```markdown
題目: 

- 有 N 個台階（從 0 編號到 N-1），每個台階上有 p 顆球。
- 兩位玩家輪流操作，每次可以選擇某個台階，將該台階上的球向下移到更低的台階
 （可以一次移動任意數量的球）。
- 無法移動的玩家輸掉遊戲。
- 多組測資，需判斷先手 ("first") 或後手 ("second") 獲勝。
```
``` markdown
解法 : 

### 1. Sprague–Grundy 分析：
   - 對於編號為 i 的台階，其 Grundy 值為：
     - G(i) = i，如果允許一次移動任意數量的球往更低台階。
   - 但這題的移動限制與台階位置奇偶性有關：
     - 當台階編號為偶數時，該堆球的 Grundy 值為 0（因為只能移到更低的偶數層
     - ，等價於無影響）。
     - 當台階編號為奇數時，該堆球的 Grundy 值為球數 p（因為等價於 Nim 堆）。

---

### 2. 化簡成 Nim：
   - 僅對奇數編號的台階，將該層的球數視為一堆 Nim 堆石子。
   - 對所有奇數編號台階的 p 做 XOR（nim-sum）。

---

### 3. 判勝條件：
   - 若 nim-sum = 0 → 後手勝。
   - 若 nim-sum ≠ 0 → 先手勝。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
int T, N, p, xor_sum;
 
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        xor_sum = 0;
        for (int i = 0; i < N; ++i) {
            scanf("%d", &p);
            // 若某樓梯上球數為奇數，則其對應 Grundy 值為 i
            if (i % 2 == 1) {
                xor_sum ^= p;
            }
        }
        // XOR 結果決定勝負：0 -> second wins, non-zero -> first wins
        printf(xor_sum ? "first\n" : "second\n");
    }
}
```

## Grundy's Game [problem](https://cses.fi/problemset/task/2207)
```markdown
題目: 

- 有一堆 N 顆石子。
- 每次可以將這一堆石子分成兩堆，且兩堆石子數量必須不同（禁止平均分）。
- 無法操作的玩家輸掉遊戲。
- 多組測資，需判斷先手 ("first") 或後手 ("second") 獲勝。
```
``` markdown
解法 : 

### 1. 遊戲規則轉換：
   - 每個局面只有一堆石子，能夠進行的唯一操作是「分堆」。
   - 分堆後產生兩個子局面，後續遊戲在兩個子局面上獨立進行  
   -（這是 Sprague–Grundy 遊戲的典型結構）。
   - 規則限制：兩堆數量必須不同，等於禁止將偶數堆均分。

---

### 2. Grundy 值計算：
   - G(n) = mex{ G(a) ⊕ G(b) }，其中 a + b = n 且 a ≠ b。
   - 此遊戲已知只有有限個必敗局（Grundy 值為 0 的局面）。
   - lose[] 陣列即是事先計算好的必敗局 N 值列表。
   - 若 N 在 lose[] 中 → Grundy 值為 0 → 後手勝。
   - 否則 → Grundy 值非零 → 先手勝。

---

### 3. 為什麼可以預先列舉：
   - Grundy’s Game 的必敗局並非規律簡單的等差序列，但範圍內可以透過離線
   - DP 預先計算出來。
   - 題目中 lose[] 包含所有 N ≤ 1222 的必敗局，且實際測資保證 N 落在這個範圍
```

``` cpp
#include <bits/stdc++.h>
 
using namespace std;
const int maxN = 1e6+1;
 
/**
 * A036685
 * Retrivied from https://oeis.org/A036685
 */
 
int T, lose[42] = { 0, 1, 2, 4, 7, 10, 20, 23, 26, 50, 53, 270, 273, 276, 282, 285, 288, 316, 334, 337, 340, 346, 359, 362, 365, 386, 389, 392, 566, 630, 633, 636, 639, 673, 676, 682, 685, 923, 926, 929, 932, 1222 };
bool b[maxN];
 
void init(){
    for(int x : lose)
        b[x] = true;
}
 
int main(){
    init();
    scanf("%d", &T);
    for(int t = 0, N; t < T; t++){
        scanf("%d", &N);
        printf("%s\n", b[N] ? "second" : "first");
    }
}
```

## Another Game