###### tags: `小菜雞解題日記`
# 主題三 : 動態規劃
## 內容
---
## LCS問題
### [裸LCIS](https://codeforces.com/contest/10/problem/D)
**解題心得**：這一題的難度竟然是2800真是嚇人，但其實它就是裸LCIS而已。
**解題想法**：LCIS的狀態就是把LIS和LCS的狀態合併在一起，所以狀態就是，$dp[i][j]$ 代表 $a$ 陣列前 $i$ 個和 $b$ 陣列前 $j$ 個，且 $b[j]$ 必選的情況下所能組成的LCIS長度。 我寫完後突然發現，LCS可以滾動成一維，而且用法不變ㄟ🤣🤣🤣。 我好弱現在才發現。
:::success
AC Code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define FOR(i, a, n) for(int i = a; i <= n; i++)
#define F0R(i, n) FOR(i, 0, n-1)
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m, st, ans, mx, cnt, a[505], b[505], dp[505][505], go[505];
void dfs(int u){
if(u == 0) return;
dfs(go[u]);
cout << b[u] << ' ';
}
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
FOR(i, 1, n) cin >> a[i];
cin >> m;
FOR(i, 1, m) cin >> b[i];
FOR(i, 1, n){
int t = 0;
FOR(j, 1, m){
dp[i][j] = dp[i-1][j];
if(a[i] == b[j]){
dp[i][j] = dp[i-1][t] + 1;
go[j] = t;
}
if(a[i] > b[j] && dp[i-1][j] > dp[i-1][t])
t = j;
if(i == n && dp[i][j] > ans){
ans = dp[i][j];
st = j;
}
}
}
cout << ans << '\n';
dfs(st);
}
```
:::
---
## 背包問題
## bitset加速01背包
### [CF 755F](https://codeforces.com/contest/755/problem/F)
**解題心得** : 這大概是我目前自己解過最難度tag最高的題目了，雖然最後還是偷看了一下要怎麼用bitset加速。
**解題想法** : 這種難度比較高的題目通常都會用到3, 4個想法(雖然我根本沒解過幾題)。看到這種給出1 ~ n排列的題目，第一個想法就是把它縮成很多個環。縮完之後就可以用貪心判斷最大，最小也只會有兩種狀況，不是k就是k+1。如果我們可以選一些環使得長度和剛好為k，那答案就會是k，如果不行就會是k+1，因此背包的狀態只需要是0和1，我們就可以用bitset優化了!!順帶一題，因為這題是多重背包，所以要先使用二進制拆分。
::: success
AC Code
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N], cnt, mn, mx, mxt, tot, len[N], num[N];
bitset<N> vis, dp;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
mxt = k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
if(!vis[i]){
int t = 1;
vis[i] = 1;
for(int j = a[i]; j != i; j = a[j])
t++, vis[j] = 1;
len[t]++;
if(t >= 2 && mxt > 0){
int tt = min(mxt, t/2);
mxt -= tt;
mx += tt * 2;
}
}
}
if(mxt > 0){
mx += mxt * 1;
}
mx = min(mx, n);
dp[0] = 1;
for(int i = 2; i <= n; i++){
if(!len[i]) continue;
int j;
for(j = 0; (1ll<<j) <= len[i]; j++){
num[tot++] = (i<<j);
len[i] -= (1<<j);
}
if(len[i]) num[tot++] = i * len[i];
}
for(int i = 0; i < tot; i++)
dp = dp | (dp << num[i]);
// 傳說中的bitset優化
if(dp[k]) mn = k;
else mn = k + 1;
cout << mn << ' ' << mx << '\n';
}
/*
6 3
2 3 1 5 6 4
*/
```
:::
### [NTUOJ 1327](http://acm.csie.org/ntujudge/problem.php?id=1327)
**解題心得** : 我在解上一題時還沒領悟到bitset背包的真諦，直到解這一題才完全了解。
**解題想法** : 一開始先每個科目都選最低分，然後之後再考慮要怎麼加分，加分的時候bitset就派上用場了，每個科目可以加 $1\ \sim\ r[i] - l[i]$分，再乘上 $w[i]$，但是為了確保同一科目不會被重複加到，我們可以開兩個bitset，先把這個科目加分的結果更新到一個暫存的bitset，最後再和原本的bitset合併(因為可以選擇不加分)。
:::success
AC Code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define F0R(i, n) FOR(i, 0, n)
#define FOR1(i, n) FOR(i, 1, n+1)
using namespace std;
int T, b, n, totw, mn, cnt, mx, g, l[50], r[50], w[50];
bitset<250005> dp, tt;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T--){
cin >> b >> n;
mn = 0; mx = 0; totw = 0; dp = 0;
FOR(i, 0, n){
cin >> l[i] >> r[i] >> w[i];
mn += l[i] * w[i];
mx += r[i] * w[i];
totw += w[i];
}
if(mn >= b * totw) {
mn -= b * totw;
g = __gcd(mn, totw);
cout << mn/g << '/' << totw/g << '\n';
}
else {
dp[mn] = 1;
FOR(i, 0, n){
tt = 0;
FOR(j, 1, r[i] - l[i] + 1){
tt = tt | (dp<<((j) * w[i]));
}
dp = dp | tt;
}
int ans = 1e15;
FOR(i, 0, mx + 1){
if(dp[i] && abs(i - totw * b) < ans) ans = abs(i - totw * b);
}
if(ans == 0) cout << "0/1\n";
else {
g = __gcd(ans, totw);
cout << ans / g << '/' << totw / g << '\n';
}
}
}
}
```
:::
### [中市賽 雙層骨牌](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d091)
**解題心得** : 這題很明顯會有多組解(題目也沒說)，但我不知道要輸出哪一組，所以我先精神AC它。
---
## 環狀DP
### [ICPC 2020 F](https://codeforces.com/gym/102835/problem/F)
**解題心得** : 原本的想法是做很多次樹dp，最後再環狀dp。但後來聽老師說，遇到環狀dp，就先把環拆掉就好。然後就會變成簡單的樹dp了。
**解題想法** : 題目有確保只會有一個環，所以我們只要拆掉一條邊，就可以變成樹，然後我們再分開考慮被拆掉那條邊上的兩個點，是否要選，最後取最小值(結果我樹dp好像是用貪心解的)。
:::success
AC Code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define F0R(i, n) FOR(i, 0, n)
#define FOR1(i, n) FOR(i, 1, n+1)
using namespace std;
int ans, n, m, x, y, cnt;
vector<int> g[200005];
bitset<200005> vis, c;
void dfs(int u, int p, int pp){
for(int v : g[u]){
if(v == p) continue;
dfs(v, u, p);
}
if(p >= 0 && !vis[u] && !vis[p]){
if(c[p] == 0) c[p] = 1, cnt++;
vis[p] = vis[u] = 1;
}
return;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, 0, n + m){
int a, b;
cin >> a >> b;
if(x == 0 && y == 0 && a < n && b < n){
x = a;
y = b;
continue;
}
g[a].pb(b);
g[b].pb(a);
}
cnt = 1;
vis = c = 0;
vis[x] = c[x] = 1;
dfs(x, -1, -1);
vis = c = 0;
ans = cnt;
vis[y] = c[y] = 1;
cnt = 1;
dfs(y, -1, -1);
ans = min(cnt, ans);
cout << ans << '\n';
}
```
:::
---
## 樹DP
### 經典問題
**題目大意** :
樹上每個點有點權，求出樹上每條簡單路徑長度和。
路徑長度定義為路徑上所有點的點權和。
::: spoiler code
```cpp!
void dfs(int u, int p) {
sz[u] = (u <= n);
for (int v : tr[u]) {
if (v == p) continue;
dfs(v, u);
ans += w[u] * sz[u] * sz[v];
sz[u] += sz[v];
}
ans += w[u] * sz[u] * (tot - sz[u]);
}
```
:::
### [牛客競賽 K短直徑](https://ac.nowcoder.com/acm/contest/69/E)
**解題心得** : 一題看起來超級可怕的題目，而且數字都很大，我在比賽中看到可能沒有勇氣解。
**解題想法** : 這題用到了樹DP一個重要的概念，如果每次將兩子樹合併，就相當於在這兩個子樹的所有點上建一條邊，而且每兩個點都只會在以他們的$LCA$為根時被合併。
所以當我們合併完成後，就會得到一張完全圖，我們都知道完全圖的邊數是$\frac{N(N-1)}{2}$。所以複雜度會是$O(N^2)$。
這題給了一個$K$，但從上面的概念延伸一下不難發現，這樣複雜度會是$O(NK)$。
所以我們可以放心的DP，把每棵子樹有經過此節點的前$K$大路徑都存下來。然後每次合併就丟到PQ裡，維護PQ的大小為$K$。
ps: 在紀錄DP陣列的時候可以使用一些 $merge\ sort$
:::success
AC Code
:::spoiler
```cpp=
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define sz(x) x.size()
#define pii pair<int, int>
#define pb emplace_back
#define F first
#define S second
#define ll long long
using namespace std;
const int N = 2e5 + 1;
int n, k, tot, h[N];
vector<ll> dp[N], tmp, ans;
priority_queue<ll, vector<ll>, greater<ll> > pq;
struct edge{
int v, w, next;
} e[(N - 1)* 2];
void add(int u, int v, int w){
e[tot] = {v, w, h[u]};
h[u] = tot++;
}
void dfs(int u, int p){
dp[u].pb(0LL);
//cout << "u = " << u << '\n';
for(int x = h[u]; x != -1; x = e[x].next){
int v = e[x].v, w = e[x].w;
if(v == p) continue;
dfs(v, u);
int nu = sz(dp[u]), nv = sz(dp[v]);
//cout << "nu = " << nu << " nv = " << nv << '\n';
for(int i = 0; i < nv; i++) dp[v][i] += w;
for(int i = 0; i < nu; i++){
for(int j = 0; j < nv; j++){
ll t = dp[u][i] + dp[v][j];
if(sz(pq) < k){
pq.push(t);
} else if(pq.top() < t){
pq.pop();
pq.push(t);
} else break;
}
}
tmp.clear();
int tot = min(k, nu + nv), i = 0, j = 0;
//dp[u].pb(-1LL);
//dp[v].pb(-1LL);
while(tot-- && (i < nu || j < nv)){
if((i < nu && dp[u][i] >= dp[v][j]) || j == nv) tmp.pb(dp[u][i++]);
else tmp.pb(dp[v][j++]);
}
dp[u] = tmp;
dp[v].clear();
}
return ;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
memset(h, -1, sizeof h);
for(int i = 1; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dfs(0, -1);
while(!pq.empty()){
ans.pb(pq.top());
pq.pop();
}
while(!ans.empty()){
cout << ans.back() << '\n';
ans.pop_back();
}
}
```
:::
## 樹上背包
因為發現之前寫的都是 worst case $O(n^3)$ 的解，所以現在來記錄一下真的 $O(n ^ 2)$ 的解。
1. $j$ 最多枚舉到 $sz(v)$
2. $i - j$ 要小於原本的 $sz(u)$ 不然子樹會和自己重複合併到
::: spoiler code
```cpp=
void dfs(int u) {
sz[u] = 1;
for (int v : g[u]) {
dfs(v);
for (int i = sz[u] + sz[v]; i >= 1; i--) {
for (int j = max(1ll, i - sz[u]); j <= i and j <= sz[v]; j++) {
dp[u][i] = min(dp[u][i], dp[u][i - j] + dp[v][j]);
}
}
sz[u] += sz[v];
}
}
```
:::
---
## 排列DP
其實有很多種方式都能寫出帶有排列的DP，例如用狀態壓縮的$O(2^N)$DP，或是利用一些組合數學的DP，但還有一種很特別的DP，好像沒有正式的名稱，之前有看到有人稱他為insertion DP，但上網查卻完全查不到資料。
### [T. Permutaion](https://atcoder.jp/contests/dp/tasks/dp_t)
這是At Coder DP Contest裡的一題，所以大家其實應該都不陌生，但一開始寫這題的時候完全沒有想法，去看完題解之後以為自己會了，但仔細想了想之後，卻發現不知道為甚麼這樣會對。
今天終於弄懂了，所以決定來記錄一下這題想法。
#### **解法**
$dp[i][j]$ 代表 $1$ ~ $i$ 的排列滿足前 $i-1$ 個限制，且第 $i$ 個數字是 $j$ 的數量。
但是要怎麼從 $1$ ~ $i$ 的排列轉移到 $1$ ~ $i+1$ 的排列呢?
我們可以想像要插入一個數字，如果插入的數字是 $x(x \le i)$，那我們就把原本排列中大於等於$x$ 的數都加上 $1$，這樣我們就可以得到新的一組排列了。
而且這樣做也不會影響到兩數字之間的大小關係。
轉移式如下
$dp[i][j] =
\begin{cases}
s[i] = ">", \ \sum_{k = j}^{k \leq i - 1}{dp[i - 1][k]} \\
s[i] = "<", \ \sum_{k = 1}^{k < j}{dp[i - 1][k]}
\end{cases}$
要注意的地方是，當 $s[i] = ">"$ 時，$dp[i][j]$ 可以從 $dp[i-1][j]$ 轉移。
如果樸素轉移的話是 $O(N^3)$ ，但很明顯可以用前綴和做到 $O(N^2)$。
### [ABC 209 Deforestation](https://atcoder.jp/contests/abc209/tasks/abc209_f)
和上面很像的一題
---
## 數位DP
一開始不太喜歡數位DP，因為我只會抄模板，但後來學了用迴圈寫才發現我之前根本沒有弄懂數位DP，這其實是個蠻有趣的DP。
### [windy數](https://www.luogu.com.cn/problem/P2657)
~~數位DP就是在數位上做DP~~，所以通常設計的狀態都以 **目前是幾位數** 和 **最高位數字** 為核心。
像是這題的狀態就是 $dp[i][j]$ 表示以 $j$ 為首位數字的 $i$ 位數中有多少 windy 數。
接下來DP的轉移應該就很好想了，但重點其實不是DP，而是要怎麼弄出答案。
因為題目要詢問的是一個區間 $[a, b]$，但這樣其實不太好做，我們可以改成用求出 $[1, a-1]$ 和 $[1, b]$ 的答案再相減。
這樣就容易多了，但還是有些細節要注意。
我們可以把它分成 3 類。
假設我們現在要求的是範圍 $[1, x]$，且 $x$ 的最高位數字為 $L_x$
#### 1. 最高位為0
這邊的最高位就是 $x$ 的最高位。
如果最高位為0，剩下的要怎麼選都沒問題。
(或是可以想成位數 $<$ $x$ 的位數 的情況)
#### 2. 最高位 $<$ $L_x$
這樣除了最高位其他位都不會被限制。
#### 3. 最高位為 $L_x$
這是最麻煩的部分，現在會有兩種情況。
第一是次高位**等於** $x$ 的次高位，這樣再下一位也會被限制。
第二是次高位**小於** $x$ 的次高位，這樣接下來就不會被限制。
所以接下來每一位都要這樣討論。
::: spoiler code
```cpp=
#define ll loli
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(all(x), v)
#define ub(x, v) upper_bound(all(x), v)
#define sz(x) (int)(x.size())
#define re(x) reverse(all(x))
#define uni(x) x.resize(unique(all(x)) - x.begin())
#define all(x) x.begin(), x.end()
#define mem(x, v) memset(x, v, sizeof x);
#define int long long
#define pii pair<int, int>
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define chmax(a, b) (a = (b > a ? b : a))
#define chmin(a, b) (a = (b < a ? b : a))
using namespace std;
void trace_() {cerr << "\n";}
template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); }
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
int a, b, dp[20][20];
inline void init() {
for (int i = 0; i <= 9; i++) dp[0][i] = 1;
for (int i = 1; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
if (abs(j - k) >= 2) dp[i][j] += dp[i-1][k];
}
}
}
}
inline int sol(int n) {
if (n <= 9) return n;
vector<int> lim;
while (n) {
lim.eb(n % 10);
n /= 10;
}
int res = 0, m = sz(lim);
// 最高位為 0
for (int i = 0; i < m - 1; i++) {
for (int j = 1; j <= 9; j++)
res += dp[i][j];
}
// 最高位小於 lim[m-1]
for (int i = 1; i < lim[m-1]; i++) {
res += dp[m-1][i];
}
// 最高位等於 lim[m-1]
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j < lim[i]; j++) {
if (abs(lim[i+1] - j) >= 2)
res += dp[i][j];
}
if (abs(lim[i] - lim[i+1]) < 2) break;
if (i == 0) res++; // n 本身也是windy數
}
return res;
}
signed main() {
IO;
cin >> a >> b;
init();
cout << sol(b) - sol(a - 1) << '\n';
}
```
:::
---
## 優化
### 單調對列優化
#### 1. [CF 1107F2](https://codeforces.com/contest/1077/problem/F2)
**解題心得** : 坑
### 矩陣快速幂優化
其實大部分的DP都可以寫成矩陣的形式，但因為如果用矩陣轉移的話通常複雜度都會變成 $O(N^3)$ 以上，所以會用到這種技巧的題目矩陣通常不大，但要轉移非常多次。
#### 1. [DMOJ 0-1](https://dmoj.ca/problem/canada21p5)
**解題心得** : 這題應該很明顯看出他是矩陣快速幂優化?因為$n$很小$K$卻很大，其實我也只寫過這一題😂😂。然後不難想到，狀態可以用 $dp[i][j]$ 經過 $j$ 次操作後，與 $t$ 相差 $i$ 個 bit 的狀況有多少種可能，然後轉移就是一些排列組合可以做到$O(n^2)$。但這樣轉移 $K$ 次的話就會變成 $O(n ^ {2}K)$ 很明顯不太優，主要是因為 $K$ 太大，所以就改用矩陣寫，轉移複雜度變 $O(n ^ 3)$ 但總時間複雜度降到 $O(n ^ {3}log K)$，就可以解決這題了。
::: spoiler code
```cpp=
#define ll loli
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(all(x), v)
#define ub(x, v) upper_bound(all(x), v)
#define sz(x) (int)(x.size())
#define re(x) reverse(all(x))
#define uni(x) x.resize(unique(all(x)) - x.begin())
#define all(x) x.begin(), x.end()
#define mem(x, v) memset(x, v, sizeof x);
#define int long long
#define pii pair<int, int>
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define chmax(a, b) (a = (b > a ? b : a))
#define chmin(a, b) (a = (b < a ? b : a))
using namespace std;
void trace_() {cerr << "\n";}
template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); }
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
const int mxN = 200;
int n, J[mxN], invJ[mxN], x, K;
bitset<mxN> s, t, tmp;
int fp(int a, int b, int p) {
int res = 1;
while(b) {
if(b&1) res = (res * a) % p;
a = a * a % p;
b >>= 1;
}
return res;
}
void build(int n) {
J[1] = J[0] = invJ[1] = invJ[0] = 1;
for(int i = 2; i <= n; i++) J[i] = J[i - 1] * i % mod;
invJ[n] = fp(J[n], mod - 2, mod);
for(int i = n - 1; i >= 2; i--) invJ[i] = invJ[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
if (n < m) return 0;
if(n == m or m == 0) return 1;
int res = J[n] * invJ[n - m] % mod * invJ[m] % mod;
return res;
}
struct mat {
int n;
vector<vector<int>> m;
mat(int _n): n(_n) {
m.resize(n, vector<int>(n, 0));
}
void init() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) m[i][j] = 0;
for(int i = 0; i < n; i++) m[i][i] = 1;
}
void clear() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) m[i][j] = 0;
}
mat operator * (mat &a) {
mat t(n);
for(int i = 0; i < a.n; i++)
for(int k = 0; k < a.n; k++)
for(int j = 0; j < a.n; j++)
t.m[i][j] = (t.m[i][j] + m[i][k] * a.m[k][j]) % mod;
return t;
}
mat operator ^ (int x) {
mat t(n), b = *this; t.init();
while (x) {
if (x & 1) t = t * b;
b = b * b;
x >>= 1;
}
return t;
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << m[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
}
};
signed main() {
IO;
build(200);
cin >> n >> x >> K >> s >> t;
tmp = s ^ t;
int d = tmp.count(), b = fp(C(n, x), K, mod), invb = fp(b, mod-2, mod);
mat a(n+1);
for (int i = 0; i <= n; i++) {
for (int j = i - x, k = 0; j <= i + x; j += 2, k++) {
if (j >= 0 and j <= n) {
a.m[j][i] += C(i, x - k) * C(n - i, k) % mod;
if (a.m[j][i] > mod) a.m[j][i] -= mod;
}
}
}
mat ans = a ^ K;
int res = ans.m[0][d];
cout << (res * invb) % mod << '\n';
}
```
:::
用了矩陣模板還有線性蓋$C$模板，所以code有點冗
Sign in with Wallet
Connect another wallet