---
# System prepended metadata

title: 110學年度上學期初階班期中考
tags: [初階班]

---

---
tags: 初階班
---
# 110學年度上學期初階班期中考
## 考試須知
### 時間
考試開始時間:$2021/11/5\; 17:00\; (GMT+8)$
考試結束時間:$2021/11/5\; 20:30\; (GMT+8)$

### 範圍
- 輸入輸出 ~ 陣列
### 配分
- 基本輸入輸出 : $1*100$
- 資料型態 : $1*100$
- if、迴圈 : $4*100$
- 陣列 : $3*100 +1*90$
- 防破台 : $1*10$
- 共 $1000$ 分
### 注意事項
- 考試期間會切網路且不可以使用手機等3C產品
- 可以使用紙筆、計算機
- 考試期間不可以和他人討論考試內容
- 如果對題目內容有問題都可以問幹部
- 吃飯時間可以使用手機但不能查程式相關東西
## 題解
考完應該就會公布，如果我來得及打完 :poop:
### 競賽用hello world
[.](http://203.64.191.163/ShowProblem?problemid=a196)
老樣子，送分題
:::spoiler `c`
```c=
#include<stdio.h>
int main() {
    printf("hello, world\n");
    return 0;
}
```
:::
:::spoiler `c++`
```cpp=
#include <iostream>
using namespace std;
int main() {
    cout << "hello, world\n";
    return 0;
}
```
:::
:::spoiler `python`
```python=
print("hello, world")
```
:::
### I. 為各位的期中考獻上祝福
這題就只是輸入$a, b$
輸出$a + b$
不過有個陷阱
$a, b\in int$不代表$a+b \in int$
所以要用$long\; long$存
不然會$59$% :poop: 
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
    long long a, b;
    cin >> a >> b;
    cout << a + b;
}
```
:::
### H. 空間向量
[.](http://203.64.191.163/ShowProblem?problemid=a692)
就是簡單的 if 跟 while
有上課應該就會寫
公式我都很好心的附上了
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int m, x1, y1, z1, x2, y2, z2;
	while (cin >> m >> x1 >> y1 >> z1 >> x2 >> y2 >> z2) {
		if (!m) cout << (x1 * x2) + (y1 * y2) + (z1 * z2) << '\n';
		else cout << (y1 * z2) - (y2 * z1) << ' ' << (z1 * x2) - (z2 * x1) << ' ' << (x1 * y2) - (x2 * y1) << '\n'; 
	}
}
```
:::
### G. 哭啊，無情沒收
[.](http://203.64.191.163/ShowProblem?problemid=a703)
這一題也是簡單的 if 跟 for
有很多種方法
我自己是將放學時間和睡覺時間都轉為分鐘
那就比較方便計算
只是如果睡覺時間是0點以後
記得分鐘數要加$1440$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int h1, m1, h2, m2, n, t;
	cin >> h1 >> m1 >> n >> h2 >> m2;
	int min1 = h1 * 60 + m1;
	for (int i = 0; i < n; i++) {
		cin >> t;
		min1 += t;
	}
	int min2 = 0;
	if (h2 < 6 || (h2 == 6 && m2 == 0)) min2 += h2 * 60 + m2 + 1440;
	else min2 += h2 * 60 + m2;
	if (min2 - min1 > 0) cout << min2 - min1;
	else cout << "那我也要睡啦";
	return 0;
}
```
:::
### F. さあ、ゲームを始めよう！
[.](http://203.64.191.163/ShowProblem?problemid=a706)
這題是本次考試最需要動腦的題目
~~其實只是簡單的數論~~
![](https://i.imgur.com/Oj5yqy2.jpg)
防止考試時你們看不到照片，我把照片丟上來了

如果看懂題目
你可以先把總天數轉為二進位
轉為二進位就很好理解了
例如$7$轉為二進位就是
$0111$
那如果要將2付出去，需要找回1
如果要將4付出去，需要找回3，也就是2加1
以此類推
公式就是$\log_2 總天數$，然後向下取整

:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int n;
	while (cin >> n) cout << __lg(n) << '\n';
}
```
:::
### E. 所謂曖昧
[.](http://203.64.191.163/ShowProblem?problemid=a690)
~~這題應該是初階教學暈船時出的題目~~
就是需要閱讀理解的題目
看懂以後用很多 if 就可以過了

**若此時 k 超出範圍則回到端點值進行下次運算**

然後$1 \leq k \leq 9$
所以這句會的意思是說
當$k$小於$1$時，把$k$設為$1$
當$k$大於$9$時，把$k$設為$9$

:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int n;
	while (cin >> n) {
		int m, t = 0, k = 5;
		int plus = 0, minus = 0;
		while (n--) {
			cin >> m;
			k += (m - 5);			
            if (k > 3 && k < 7) plus++;
			else minus++;
			if (plus >= 3) t++, plus -= 3;
			else if (minus >= 3) t--, minus -= 3;
			if (k > 9) k = 9;
			else if (k < 1) k = 1;
		}
		cout << t << '\n';
	}
}
```
:::
### D. 拿餐大作戰
[.](http://203.64.191.163/ShowProblem?problemid=a685)
這一題就是簡單的二維陣列
可是要小心題目有陷阱
便當位置的表示是

**從上數下來第幾排，從右數到左第幾個**

不是從左到右 :poop: 
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	int arr[n][m];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) 
			cin >> arr[i][j];
	cout << arr[x - 1][m - y];
}
```
:::
### C. 一筆畫問題
[.](http://203.64.191.163/ShowProblem?problemid=a695)
這一題是用到陣列
~~很佛心了吧，一筆畫規則都給你說了~~
就是開一個陣列
存這個點被通過的次數
最後再判斷是否符合條件
::: spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
	int t;
	cin >> t;
	while (t--) {
		int m, n;
		cin >> m >> n;
		int arr[m + 1] = {0};
		for (int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			arr[x]++, arr[y]++;
		}
		bool flag = false;
		int ans = 0;
		for (int i = 1; i <= m; i++) {
			if (arr[i] % 2 != 0) ans++;
			else if (arr[i] == 0) {
				flag = true;
				break;
			}
		}
		if (!flag && (ans == 0 || ans == 2)) cout << "yes\n";
		else cout << "no\n";
	}
}

```
:::

### B. 吳乙己
[.](http://203.64.191.163/ShowProblem?problemid=a681)
這一題就只是區間和
~~只是被我用很油的題序包裝~~
![](https://i.imgur.com/iQkyoIf.png)
一樣怕你們看不到照片

就是給你一串數字
問你某一段的數字總和
然後答案記得用 unsigned long long 存

然後這題有一個很機車的東西
因為它會詢問很多次
用for迴圈慢慢跑會只有80%
想要AC的話要用```前綴和```

一般來說
陣列是用來存每一項題目給你的數字
但```前綴和```是把前n項的和存在第n格陣列
這樣就會快上不少

::: spoiler `一般解 (80%)`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int main () {
	int n, m;
	cin >> n >> m;
	ULL arr[n + 1];
	int a;
	cin >> a;
	arr[0] = 0, arr[1] = a;
	for (int i = 2; i < n + 1; i++) {
		cin >> arr[i];
	}
	int x, y;
	for (int i = 0; i < m; i++) {
		ULL ans = 0;
		cin >> x >> y;
		for (int i = x; i <= y; i++) ans += arr[i];
		cout << ans << '\n';
	}
}
```
:::

~~然後80%的解如果加上io優化就可以到90%~~

::: spoiler `前綴和 (AC)`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int main () {
	int n, m;
	cin >> n >> m;
	ULL arr[n + 1];
	int a;
	cin >> a;
	arr[0] = 0, arr[1] = a;
	for (int i = 2; i < n + 1; i++) {
		cin >> a;
		arr[i] = arr[i - 1] + a;
	}
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		cout << arr[y] - arr[x - 1] << '\n'; 
	}
}

```
:::

### A. 果然我的高一平凡生活搞錯了。完
[.](http://203.64.191.163/ShowProblem?problemid=a680)
這一題就是防破台題
能30%的，為什麼要用遞迴ㄚㄚㄚ
能60%的，還算不錯
能90%的，非常電 ~~或有認真聽我之前的題解~~
能100%的，我嚴重懷疑你平常在裝弱，~~因為這題也是進階班的防破台題~~

**以下題解來自進階教學**
#### 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_1`
```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';
	}
}
```
:::
:::spoiler `code_2`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
int main () {
	ios::sync_with_stdio(0), cin.tie(0);
	int m;
	cin >> m;
	while (m--) {
		ll n, k;
		cin >> n >> k;
		vector <ll> vec(k + 1, 0);
		vec[0] = 1;
		for (ll i = 1; i < k + 1; i++) {
			for (ll j = 1; j < min(i, n + 1) + 1; j++) {
				vec[i] += vec[i - j];
				vec[i] %= mod;
			}
		}
		cout << vec[k] << '\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 & 1 & 0 & 0 & 0 & ...\\0 & 0 & 1 & 0 & 0 & ...\\0 & 0 & 0 & 1 & 0 & ...\\ ⋮\\1 & 1& 1& 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;
}
```
:::
::: spoiler `code_副初階教學`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
vector <vector <ll>> quick (vector <vector <ll>> vec1,vector <vector <ll>> vec2, int n) {
	vector <vector <ll>> tmp (n, vector<ll>(n, 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] + (vec1[i][k] * vec2[k][j])) % mod;
	return tmp;
}
int main () {
	ios::sync_with_stdio(0), cin.tie(0);
	int m;
	cin >> m;
	while (m--) {
		ll n, k;
		cin >> n >> k;
		vector <vector <ll>> base (n + 1, vector<ll>(n + 1, 0));
		vector <vector <ll>> pro (n + 1, vector<ll>(n + 1, 0));
		for (int i = 0; i < n; i++) 
			base[0][i] = 1, base[i + 1][i] = 1, pro[i][i] = 1;	
		base[0][n] = 1, pro[n][n] = 1;
		ll x = k - n - 1;
		if (x <= 0) {
			ll ans = 1;
			for (int i = 0; i < k - 1; i++) 
				ans = ans * 2 % mod;
			cout << ans << '\n';
		}
		else {
			while (x != 1) {
				if (x % 2 == 0) {
					base = quick (base, base, n + 1);
					x /= 2;
				} 
				else {
					pro = quick (pro, base, n + 1);
					x--;
				}
			}
			base = quick (base, pro, n + 1);
			ll ans = 0;
			for (int i = 0; i < n + 1; i++) {
				ans = (ans + base[0][i] * (ll)pow(2, n - i)) % mod;
			}
			cout << ans << '\n';
		}
	}
}
```
:::
