---
tags: 進階班
---
# 10th 上學期進階班期中考題解
## A. 果然我的高一平凡生活搞錯了。完
#### NA 30%
我們可以知道：$Hank$ 若經歷第 $i$ 個事件，他前一個事件必定是第 $(i - n - 1)$ ~ $(i - 1)$ 個事件。
而且他必經歷第 $0$ 個事件$\implies dp[0] = 1$
因此：
$\displaystyle \begin{cases} dp[0] = 1\\dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[1] + dp[0]\quad\quad if\quad 1\leq i\leq n + 1\\dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[i - n - 1]\quad\quad if\quad i > n + 1\\ \end{cases}$
然後用複雜度很高的遞迴寫(不包含$DP$ )
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL fib(int n, int k) {
if (n == 1) {
if (k < 0) return 0;
else if (k <= 1) return 1;
return (fib(n, k - 1) + fib(n, k - 2)) % mod;
}
else if (n == 2) {
if (k < 0) return 0;
else if (k <= 1) return 1;
else if (k == 2) return 2;
return (fib(n, k - 1) + fib(n, k - 2) + fib(n, k - 3)) % mod;
}
return 0;
}
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int t, n, k;
cin >> t;
while (t--) {
cin >> n >> k;
cout << fib(n, k) << '\n';
}
}
```
:::
#### NA 60%
在 $dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[1] + dp[0]\quad\quad if\quad 1\leq i\leq n + 1$ 時
我們可以發現：
$dp[0] = 1 = 2^0,dp[1] = 1 = 2^0, dp[2] = dp[0] + dp[1] = 2 = 2^1\implies dp[i] = 2^{i - 1}$
然後這次用迴圈做：
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL arr[100001];
LL sum(int l, int r) {
LL ret = 0;
for (; l <= r; l++) ret = (ret + arr[l]) % mod;
return ret;
}
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
for (int x = 0; x <= n; x++) arr[x] = pow(2, x);
for (int x = n + 1; x < k; x++)
arr[x] = sum(x - n - 1, x - 1);
cout << arr[k - 1] << '\n';
}
}
```
:::
#### NA 90 %
$i>n+1$ 時
$dp[i] = dp[i - 1] + dp[i - 2] + .............. + dp[i - n - 1]$
$dp[i-1] = \quad\quad\quad\; dp[i - 2] + dp[i - 3] + ... + dp[i-n-1]+dp[i - n - 2]$
兩式相扣
$\implies dp[i] - dp[i - 1] = dp[i - 1] - dp[i - n - 2]$
$\implies dp[i] = dp[i - 1]\times 2 - dp[i - n - 2]$
實作可以兩種：
1. 把空間滾動，只開長度為 $n + 2$ 的陣列
2. 開一個長度 $10^7$ 的陣列，不過注意資料型態要是 $int\implies$每次運算都要 $mod\;10^9 + 7$
注意 $(dp[i - 1]\times 2 - dp[i - n - 2]) \% mod$ 可能是負的。(因為 $dp[i - 1]$ 取完餘數後可能很小)
:::spoiler `code_1`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
LL arr[n + 2];
for (int x = 0; x <= n; x++) arr[x] = pow(2, x);
arr[n + 1] = 1;
for (int x = n + 1; x < k; x++) {
arr[x % (n + 2)] -= arr[(x - 1) % (n + 2)] * 2;
arr[x % (n + 2)] *= -1;
arr[x % (n + 2)] = (arr[x % (n + 2)] + mod * 2) % mod;
}
cout << arr[(k - 1) % (n + 2)] << '\n';
}
}
```
:::
:::spoiler `code_2`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int arr[10000001];
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
arr[0] = 1;
for (int x = 1; x <= n + 1; x++) arr[x] = pow(2, x - 1);
for (int x = n + 2; x <= k; x++)
arr[x] = ((2 * arr[x - 1] - arr[x - n - 2]) % mod + mod) % mod;
cout << arr[k] << '\n';
}
}
```
:::
#### AC
把前面幾個轉移式的條件整合一下：
$M = \left [ \begin{array}{ccc} 2^0 & 2^1 & 2^2 & ... & 2^n\end{array}\right]\left [ \begin{array}{ccc} 0 & 0 & 0 & 0 & ... &0& 1\\1 & 0 & 0 & 0 & ... & 0&1\\0 & 1 & 0 & 0 & ... & 0&1\\ 0&0&1&0&... & 0&1\\⋮\\0 & 0& 0& 0& ... & 1&1\end{array}\right]^{k - 1}$
(右陣列是一個大小為 $(n + 1)\times (n + 1)$ 的陣列)
然後用矩陣的方式運算，答案為 $M[0]$
:::spoiler `code_進階班`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr LL m = 1e9 + 7;
LL n;
vector<vector<LL>> I(21, vector<LL> (21, 0));
vector<vector<LL>> mat(const vector<vector<LL>> &x, const vector<vector<LL>> &y) {
vector<vector<LL>> ret(n + 1, vector<LL> (n + 1, 0));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
ret[i][j] = (ret[i][j] + x[i][k] * y[k][j]) % m;
}
}
return ret;
}
vector<vector<LL>> mpow(vector<vector<LL>> x, LL y) {
vector<vector<LL>> ret = I;
for (; y; y >>= 1, x = mat(x, x)) {
if (y & 1) ret = mat(ret, x);
}
return ret;
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
LL T, k;
cin >> T;
while (T--) {
cin >> n >> k;
vector<vector<LL>> A(n + 1, vector<LL> (n + 1, 0));
vector<vector<LL>> B(n + 1, vector<LL> (n + 1, 0));
for (int x = 0; x <= n; x++) {
A[0][x] = pow(2, x), I[x][x] = 1;
if (x < n) B[x + 1][x] = 1;
B[x][n] = 1;
}
A = mat(A, mpow(B, k - 1));
cout << A[0][0] << '\n';
}
return 0;
}
```
:::
:::spoiler `code_初階班`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int m = 1000000007;
int main() {
LL T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
k--;
LL A[21][21], B[21][21], I[21][21], tmp[21][21];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
A[i][j] = B[i][j] = I[i][j] = 0;
}
for (int x = 0; x <= n; x++) {
A[0][x] = pow(2, x), I[x][x] = 1;
if (x < n) B[x + 1][x] = 1;
B[x][n] = 1;
}
while (k != 0) {
if (k % 2 == 1) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + I[i][k] * B[k][j]) % m;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
I[i][j] = tmp[i][j];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + B[i][k] * B[k][j]) % m;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
B[i][j] = tmp[i][j];
}
k /= 2;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + A[i][k] * I[k][j]) % m;
}
}
cout << tmp[0][0] << '\n';
}
return 0;
}
```
:::
## B. 從零開始的程設班生活
這題根據提示，可以類推成：$\cfrac{(str.size())!}{n('a')!\;n('b')!\;n('c')!\;\;...}$
也就是字串長度階乘除以各個字元的重複次數階乘。
由於答案需要 $mod\;10^9 + 7$，且 $10^9 + 7\in prime$，因此可以使用費馬小定理求得模逆元。
值得注意的是，由於計算階乘的複雜度是 $O(N)$，且本題會常常用到，因此建表可以壓低複雜度
($O(TN)\Rightarrow O(N)$)。
而階乘的模逆元表可以不用建，因為複雜度為 $O(lgN)$，比 $O(N)$ 快非常多，
直接求與建表的時間差距不會太大。
得分依據：
#### NA 20% 不用 $mod$
#### NA 40% 只算分子且有 $mod\; 10^9 + 7$
#### NA 70% 沒建階乘表
#### AC 有建階乘表且使用 $IO$ 優化
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;
constexpr int m = 1e9 + 7;
const int maxn = 1e5;
LL inv[maxn + 1], fac[maxn + 1];
LL fpow(LL x, int y = m - 2) {
LL ret = 1;
for (; y; y >>= 1, x = x * x % m) {
if (y & 1) ret = ret * x % m;
}
return ret;
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T;
string str;
cin >> T;
fac[0] = inv[0] = 1;
for (int x = 1; x <= maxn; x++)
fac[x] = fac[x - 1] * x % m, inv[x] = fpow(fac[x]);
while (T--) {
cin >> str;
LL ans = fac[str.size()];
int tmp[123]; mem(tmp);
for (auto & i : str) tmp[i]++;
for (auto & i : tmp) ans = ans * inv[i] % m;
cout << ans << '\n';
}
}
```
:::
## C. 小青蛙的夢想
跟[無限階梯](http://203.64.191.163/ShowProblem?problemid=a650)很類似。
前進$a, b$階的方法數相加就好了。
### 轉移式
#### NA 20%
另$dp[i][j]\implies$ 在第`i`次抽卡且執行結束後在長度為$j$的方法數
{$$\displaystyle \begin{cases} dp[0][0] = 1\\dp[i][j] \equiv dp[i - 1][j -a ] + dp[i - 1][j - b]\;\;mod (10^9 + 7)\end{cases}$$
}
時間複雜度$O(NM)$
空間複雜度$O(NM)$
#### AC
空間複雜度在$N, M$都為$10^4$空間複雜度會爆掉。
所以需要把它改成滾動的。
::: spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define ll long long
#define pii pair<int,int>
const int mod = 1e9 + 7;
int main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M;
cin >> N >> M;
V<V<int>> dp(2, V<int> (N, 0));
dp[1][0] = 1; //dp[~0&1][0] = 1;
for(int i = 0, a, b; i < M; i++) {
cin >> a >> b;
a %= N;
b %= N;
for(int j = 0; j < N; j++) {
int cur_pos_a = (j - a + N) % N;
int cur_pos_b = (j - b + N) % N;
dp[i&1][j] = (dp[~i&1][cur_pos_a] + dp[~i&1][cur_pos_b]);
dp[i&1][j] %= mod;
}
}
cout << dp[~M&1][0] << endl;
}
```
:::
## D. 追番科高校的劣等生
這題的重點在於**溫馨提示**，
他說「既然是追番，那當然不能跳集看對吧?」，
這時波司淺雪一定是從第一集、第二集，到最後一集這樣看。
因此 **淺雪得到的分數 = 看到第幾集$\times 10$**。
這時就會有 **NA**$50\%$ 的解法，
就每次都遍歷所有的集數的時數並加總，
直到大於等於淺雪所擁有的時間為止。
`Time Complexity:` $O(QN)$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int n, q;
cin >> n;
vector<int> vt(n);
for(auto& i : vt)
cin >> i;
cin >> q;
while(q--) {
int m, ans = 0, sum = 0;
cin >> m;
for(int i = 0; i < n; ++i) {
sum += vt[i];
if(sum <= m)
++ans;
else
break;
}
cout << 10*ans << '\n';
}
}
```
:::
如果要拿到 **AC** 的話，
只要把線性搜尋改成二分搜尋就好，
因為遍歷加總其實就是前綴和，
而在 $T_i\ge 1$ 的情況下，
前綴和必呈現嚴格遞增，
所以可以用二分搜尋解。
`Time Complexity:` $O(Q\log N)$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int n, q;
cin >> n;
vector<int> t(n);
for(auto& i : t)
cin >> i;
for(int i = 1; i < n; ++i)
t[i] += t[i-1];
cin >> q;
while(q--) {
int m;
cin >> m;
auto it = lower_bound(t.begin(), t.end(), m);
if(*it == m)
cout << 10*(it-t.begin()+1) << '\n';
else
cout << 10*(it-t.begin()) << '\n';
}
}
```
:::
## E. 樹語國和旭誠國之間的愛恨情仇
這一題沒有安排部分分數，
基本上拿到部分分的就是剛好喇到:poop:。
這題的重點其實就是在凱能的位置，
題目說他正對著 $(0, 0)$，
而且能看到兩排，
所以很顯然的他的位置會是與最中間的斜角重和。
知道這點後轉移式就出來了
$$
dp_{i, j} = dp_{i-1, j} + dp_{i, j-1} + dp_{i-1, j-1}
$$
這裡的 $i$ 和 $j$ 的意義是要綁在一起看的，
意思是在第 $i$ 列、第 $j$ 行的**敵人的編號**，
而 $dp_{i, j}$ 代表的是**受到的傷害**。
但是這裡如果直接打成程式碼的話會錯，
因為除非使用大數運算，
不然沒有資料結構存的了受到的傷害 ($1 \leq D_i\leq 100$ 在經過轉移式的疊加後會超大)。
這時要用到一點的數論，
由於 $DP$ 裡面的每一格都是正整數，
所以相加只會愈來愈大，
也就是說如果這一格的傷害殺的掉 Hank，
那從這格連鎖的敵人所受到的傷害也一定殺的掉 Hank。
所以轉移式可以改成
$$
dp_{i, j} = min(H,\quad dp_{i-1, j} + dp_{i, j-1} + dp_{i-1, j-1})
$$
或著是
$$
dp_{i, j} = min(10^9,\quad dp_{i-1, j} + dp_{i, j-1} + dp_{i-1, j-1})
$$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mxH = 1e9, mxN = 500, mxM = 500;
ll dp[mxN][mxM];
void solve() {
int m, n, e, h, qx, qy;
cin >> n >> m >> e >> h >> qx >> qy, --qx, --qy;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < e; ++i) {
ll x, y, d;
cin >> x >> y >> d, --x, --y;
dp[x][y] += d;
}
for(int i = 1; i < n; ++i)
dp[i][0] = min(mxH, dp[i][0] + dp[i-1][0]);
for(int j = 1; j < m; ++j)
dp[0][j] = min(mxH, dp[0][j] + dp[0][j-1]);
for(int i = 1; i < n; ++i) {
for(int j = 1; j < m; ++j) {
dp[i][j] = min(mxH, dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]);
}
}
cout << (dp[qx][qy] >= h ? "Yes" : "No") << '\n';
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
int T;
cin >> T;
while(T--)
solve();
}
```
:::
Sign in with Wallet
Connect another wallet