# 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
Sign in with Wallet
Connect another wallet