---
tags: 109_FDCS
---
# FDforces Round #1 (Div. 1) Tutorial
## p1: a196. 競賽用hello world (600)
> [name=by fdhs107_KonChin_Shih][color=#1f1e33]
### code
```python=
print("hello, world")
```
---
## p2: a466. 國土大夢想家 (1200)
> [name=by fdhs107_KonChin_Shih][color=#1f1e33]
### 想法
看一堆人用`if`判所有么九牌，我整個panik
顯然用STL就好了，整個code不長
### code
```cpp=
#include<iostream>
#include<set>
#define endl '\n'
using namespace std;
inline void solve() {
string str;
set<string> s{"1m", "9m", "1p", "9p", "1s", "9s", "1z", "2z", "3z", "4z", "5z", "6z", "7z"};
for (int n = 13; n--;)
cin >> str, s.erase(str);
cout << (s.empty() ? 13 : s.size() > 1 ? 0 : 1) << endl;
}
main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--)
solve();
return 0;
}
```
:::spoiler code by fdhs109_GT
```cpp=
#include <bits/stdc++.h>
using namespace std;
inline void solve() {
set<string> ss{"1m", "9m", "1p", "9p", "1s", "9s", "1z", "2z", "3z", "4z", "5z", "6z", "7z"};
set<string> s; string tmp; int res = 0;
for (int i = 0; i < 13; i++) cin >> tmp, s.insert(tmp);
for (const auto& i : ss) res += s.count(i);
cout << (res == 13 ? res : res == 12 ? 1 : 0) << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
```
:::
---
## p3: a457. 就說期中考會考了，還敢不寫作業啊 (1500)
> [name=by fdhs109_GT][color=#c665f7]
### 想法
看到 `code` 自己想一想，
這是作業題，
也都說可以貼模板 (?) 了，
應該過吧 :poop:
反正就是 `.` 先判斷，
然後再用 `string` 的 `operator>` 來判斷就好了 ><，
看到好多人寫 $60$ 幾行，
還有人寫 $100$ 多行，
我就好爽 :poop: 。
### code
```cpp=
// from giver
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s1, s2;
while (cin >> s1 >> s2) {
string ts1 = s1, ts2 = s2;
if (s1.find(".") == -1) s1 += ".";
if (s2.find(".") == -1) s2 += ".";
int p1 = s1.find(".");
int p2 = s2.find(".");
if (p1 != p2) cout << (p1 > p2 ? ts2 : ts1) << "\n";
else cout << min(ts1, ts2) << "\n";
}
}
```
:::spoiler Python AC code by fdhs107_KonChin_Shih
```python=
from decimal import *
from sys import stdin
getcontext().prec = 1000005
for a in stdin:
a = Decimal(a)
b = Decimal(stdin.readline())
print(min(a, b))
```
:::
---
## p4: a433. KonChin走格子 (1600)
> [name=by fdhs108_38002][color=#FFD700]
~~此題的定位是水題~~
有寫作業的人，這題至少要拿$50\%$
### Subtask 1(20%) $x, y\leq10, q \leq \frac{xy}{2}$
先說個題外話
高中的程式競賽(TOI, 學科...)或是檢定(APCS)，基本上都是採IOI賽制，所以一題會有多個測資點讓你去解，基本上越後面的測資點越難拿，而前面的測資點大部分只要模擬、暴力解，都可以喇到。
爆搜其實算是比較基礎的解題想法(?)，比起其他演算法設計想法(DP, Greedy...)，其實比較容易做出來
那這邊就不贅述爆搜解了，相信大家都能想出來 XD
### Subtask 2(30%) $x, y\leq10^2, q \leq \frac{xy}{2}$
$O(xyq)$ 勉強能喇過，因為我詢問的點沒卡每次都是最右下角的點
有寫作業[a422: GT走格子](http://203.64.191.163/ShowProblem?problemid=a422)的人，至少該拿到這筆測資
#### 想法
可以用比較數學的想法去思考這題，對於一點(x, y)來說他被走到的次數會是$${x+y\choose x}{(q_x - x) + (q_y - y)\choose q_x - x}$$
所以對於每個詢問的答案會是$$\sum\limits_{i = 1}^{q_x}\sum\limits_{j = 1}^{q_y}{i+j\choose i}{(q_x - i) + (q_y - j)\choose q_x - i} \times weight(i, j)$$
::: spoiler code by revival0728 (33419 傅興)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int mxX = 2e3, mxY = mxY, M = 1000000007;
int x, y, q;
int dp[mxX][mxX], val[mxX][mxX];
long long ans;
int main()
{
cin.tie(0), ios_base::sync_with_stdio(0);
for(int i = 0; i < mxX; ++i){
dp[0][i] = 1;
}
for(int i = 0; i < mxX; ++i){
dp[i][0] = 1;
}
for(int i = 1; i < mxX; ++i){
for(int j = 1; j < mxX; ++j){
dp[i][j] = dp[i-1][j] + dp[i][j-1], dp[i][j] %= M;
}
}
while(cin >> x >> y >> q){
for(int i = 0; i < y; ++i){
for(int j = 0; j < x; ++j){
cin >> val[i][j];
}
}
int a, b;
while(q--){
ans = 0;
cin >> a >> b;
for(int i = 0; i < b; ++i){
for(int j = 0; j < a; ++j){
ans += (1LL * (dp[i][j] % M) * dp[b-i-1][a-j-1] % M) * val[i][j], ans %= M;
}
}
cout << ans << endl;
}
}
}
```
:::
### Subtask 3(50%) $x, y\leq 2\times10^3, q \leq \frac{xy}{2}$
再說一個題外話
只要題目不是那種超毒瘤的題目，通常都會先從測資範圍判斷該如何下手
例如這題$x, y\leq 2\times10^3$
input的複雜度是$O(xy)$, output是$O(1)$
也就是說這題的複雜度絕對不會比$O(xy)$還好，畢竟輸入就要$O(xy)$
再來詢問次數是$\frac{xy}{2}$，所以對於每次詢問要是$O(1)$，才可能使總複雜度為$O(xy)$
接下來就需要一點的經驗，來想出這題是dp
我們可以先假設$dp[i][j]$是以$(i, j)$為終點的所有路徑價值和
而對於點$(i, j)$而言，只可能從$(i - 1, j)$或$(i, j - 1)$過來
也就是說$dp[i][j]$，是$dp[i - 1][j] + dp[i][j - 1] +$從$(i - 1, j)或(i, j - 1)$過來的可能總數乘上該點的價值。
dp轉移式 : $$dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + {i + j\choose i} \times weight(i, j)$$
所以每次詢問就輸出$dp[q_x][q_y]$就好了，$O(1)$
總複雜度 $O(xy + q)$
又要再說一個題外話
如果你確定你code的複雜度是好的，但卻TLE，很有可能是常數太大 XD
雖然一般的題目都不會卡常數，但如果不小心被卡到的話，就盡量把不需要的操作省略，或是做其他優化(bitset, I/O, ...)
::: spoiler code by fdhs108_38002
```cpp=
const int N = 3000 + 5;
int cnt[N][N], dp[N][N];
inline void solve() {
int n, m, q; cin >> m >> n >> q;
ms(cnt, 0), ms(dp, 0);
cnt[1][1] = 1;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(i != 1 || j != 1)
cnt[i][j] = 1ll * (cnt[i - 1][j] + cnt[i][j - 1]) % MOD;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) {
ll tmp; cin >> tmp;
dp[i][j] = 1ll * (dp[i - 1][j] + dp[i][j - 1] + tmp * cnt[i][j] % MOD) % MOD;
}
while(q--) {
int a, b; cin >> a >> b;
cout << dp[b][a] << '\n';
}
}
```
:::
::: spoiler code by fdhs109_dylanoggy (✰いと爆死✰)
```cpp=
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define endl '\n'
#define _ cin.tie(nullptr),ios::sync_with_stdio(false);
using namespace std;
using ll=long long;
int main(){_
int x,y,q;
cin>>x>>y>>q;
vector<vector<ll>>v(y,vector<ll>(x,0));
for(int i=0;i<y;i++)for(int j=0;j<x;j++)cin>>v[i][j];
int ansx,ansy;
vector<vector<ll>>m(y,vector<ll>(x,0));
vector<vector<ll>>ans(y,vector<ll>(x,0));
m[0][0]=1;
ans[0][0]=v[0][0];
for(int j=1;j<x;j++){
m[0][j]=1;
ans[0][j]=(v[0][j]+ans[0][j-1])%1000000007;
}
for(int i=1;i<y;i++){
ans[i][0]=(ans[i-1][0]+v[i][0])%1000000007;
m[i][0]=1;
for(int j=1;j<x;j++){
m[i][j]=(m[i][j-1]+m[i-1][j])%1000000007;
ans[i][j]=(ans[i-1][j]+ans[i][j-1])%1000000007;
ans[i][j]=(ans[i][j]+m[i][j]*v[i][j]%1000000007)%1000000007;
}
}
for(int i=0;i<q;i++){
cin>>ansx>>ansy;
cout<<ans[ansy-1][ansx-1]<<endl;
}
}
```
:::
::: spoiler code by Fdhs109_qazwsx (33325劉承豐)
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll p[2005][2005], r[2005][2005];
int main()
{
memset(p, 0, sizeof(p)), memset(r, 0, sizeof(p));
cin.tie(0);
ios_base::sync_with_stdio(false);
int x,y,q;
cin>>x>>y>>q;
r[0][1]=1;
for(int i=1;i<y+1;i++)
{
for(int j=1;j<x+1;j++)
{
cin>>p[i][j];
p[i][j]=p[i][j]%mod;
r[i][j]=(r[i-1][j]+r[i][j-1])%mod;
p[i][j]=(p[i-1][j]+p[i][j-1]+r[i][j]*p[i][j])%mod;
}
}
for(int a=0;a<q;a++)
{
int qx,qy;
cin>>qx>>qy;
cout<<p[qy][qx]<<'\n';
}
}
```
:::
:::spoiler code by fdhs107_KonChin_Shih
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#define endl '\n'
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m, q, k, a, b; cin >> m >> n >> q;
vector<vector<int>> arr(n, vector<int>(m, 1));
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
arr[i][j] = (arr[i - 1][j] + arr[i][j - 1]) % mod;
vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> k, v[i + 1][j + 1] = (1LL * arr[i][j] * k + v[i][j + 1] + v[i + 1][j]) % mod;
while (q--)
cin >> b >> a, cout << v[a][b] << endl;
return 0;
}
```
:::
---
## p5: a465. Lelwen走迷宮 (1600)
> [name=by fdhs108_38002][color=#FFD700]
~~此題的定位是水題~~
在考試的時候，發現上課有上到類似題[b554: 5.貪吃龍遊戲](https://hackmd.io/@konchin/Brute-force#b554-5%E8%B2%AA%E5%90%83%E9%BE%8D%E9%81%8A%E6%88%B2)
所以更應該要寫出這題(?
跟上題補充的一樣，從測資範圍可看出爆搜沒問題
所以問題在於寫不寫得出來，那這就是看你練習量的多寡了
考試時測資太水被隨便唬爛過，已更新 XD
::: spoiler code by fdhs108_38002
```cpp=
const int N = 8;
int n, w[N][N], ans = 1e9;
bool v[N][N]; // 是否可走
const pii go[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //pair<int, int>
#define nx (x + go[i].F) // go[i].first
#define ny (y + go[i].S) // go[i].second
void dfs(int x, int y, int cnt = w[0][0]) {
if(cnt > ans) return; // 剪枝
if(x == n - 1 && y == n - 1) {
ans = cnt;
return;
}
for(int i = 0; i < 4; ++i)
if(nx >= 0 && nx < n && ny >= 0 && ny < n && !v[nx][ny]) {
v[x][y] = 1;
dfs(nx, ny, cnt + w[nx][ny]);
v[x][y] = 0;
}
}
inline void solve() {
cin >> n;
ms(v, 0), ms(w, 0); //memset(v, 0, sizeof(v))
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) {
char c; cin >> c;
v[i][j] = (c == 'X');
}
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
cin >> w[i][j];
dfs(0, 0);
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
```
:::
:::spoiler code by fdhs107_KonChin_Shih
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<tuple>
#define endl '\n'
using namespace std;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, res; cin >> n; string str;
vector<vector<int>> v(n, vector<int>(n));
for (int i = 0; i != n; i++) cin >> str;
for (auto& i : v) for (auto& j : i) cin >> j;
for (auto& i : v) replace(i.begin(), i.end(), 0, int(1e9));
auto check = [&](int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n && v[x][y] != 1e9;
};
const pair<int, int> arr[] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
function<int(int, int)> dfs = [&](int x, int y) {
if (x == n - 1 && y == n - 1) return v[x][y];
int minn = 1e9, tmp = v[x][y]; v[x][y] = 1e9;
for (const auto& i : arr) {
int a, b; tie(a, b) = i;
if (check(x + a, y + b))
minn = min(minn, dfs(x + a, y + b));
}
v[x][y] = tmp;
return min(int(1e9), minn + v[x][y]);
}; res = dfs(0, 0);
cout << (res == 1e9 ? -1 : res) << endl;
return 0;
}
```
:::
:::spoiler code by fdhs109_GT
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> mp;
vector<vector<bool>> vst;
int res = 1e9, n, ans = 0; string s;
void dfs(int y, int x, int sum = 0) {
sum += mp[y][x];
if (y == n && x == n) {
res = min(res, sum), ans = 1;
return;
}
if (x > 1 && mp[y][x - 1] && !vst[y][x - 1]) // left
vst[y][x] = 1, dfs(y, x - 1, sum), vst[y][x] = 0;
if (y > 1 && mp[y - 1][x] && !vst[y - 1][x]) // up
vst[y][x] = 1, dfs(y - 1, x, sum), vst[y][x] = 0;
if (x < n && mp[y][x + 1] && !vst[y][x + 1]) // right
vst[y][x] = 1, dfs(y, x + 1, sum), vst[y][x] = 0;
if (y < n && mp[y + 1][x] && !vst[y + 1][x]) // down
vst[y][x] = 1, dfs(y + 1, x, sum), vst[y][x] = 0;
}
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
int main() { _
cin >> n;
for (int i = 0; i < n; cin >> s, i++);
mp.resize(n + 1, vector<int>(n + 1));
vst.resize(n + 1, vector<bool>(n + 1));
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; cin >> mp[i][j++]);
dfs(1, 1), cout << (ans ? res : -1) << '\n';
}
```
:::
---
## p6: a458. 都說這題是水題了，還不趕快來解這題啊 (1700)
> [name=by fdhs109_GT][color=#c665f7]
### 想法
- 水題 ✅
阿我都把解法打在題敘中了，
應該要 `AC` ✅。
$p_{l}\times p_{(l+1)}\times p_{(l+2)}\times\dots\times p_r\\=質數乘積表[r]\div 質數乘積表[l-1]$
所以，
只要建好質數乘積表，
對於每次查詢就可以快速得到 $[L,\ R]$ 的質數乘積，
但是模運算不適用於乘法，
所以要用模逆元 `inv(x) = fastpower(x, mod - 2, mod)`，
所求$\implies 質數乘積表[r]\times inv(質數乘積表[l-1])\mod 998244353$，
### 模逆元
結論簡單，
用背的就可以，
但身為教學組，
還是來寫一下 $證明(?)$ 好了 :poop:
by `Fermat's little theorem` :
$a^p-a$ 是 $p$ 的倍數 (for p is a prime number)，
$\implies a^p\equiv a\mod p$
$\implies a^{(p-1)}\equiv1\mod p$, where $a \ne pk, k\in N$
$\implies a\times a^{(p-2)}\equiv1\mod p$, where $, where $a \ne pk, k\in N$
概念同於 $a\times\frac{1}{a}\equiv1(\mod p)$
$\implies a^{(p-2)}\mod p$ 就是 $a$ 的乘法反元素，
### code
```cpp=
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
vector<int> v{2}, fac(1000001, 1); // v 質數表, fac 質數乘積表
int fpow(int a, int b, int m) { // fast power 快速冪
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % m)
if (b & 1) ret = 1LL * ret * a % m;
return ret;
}
int inv(int x) { // inverse, 乘法反元素
return fpow(x, mod - 2, mod);
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
// 質數表, 順便建質數乘積表
for (int i = 2; i <= 1000000; i++) {
bool f = 1;
for (const auto& j : v) {
if (j * j > i) break; // 只要判斷到 sqrt 就好了
if (i % j == 0) { f = 0; break; }
}
if (f) v.push_back(i), fac[i] = 1LL * fac[i - 1] * i % mod;
else fac[i] = fac[i - 1];
}
for (int l, r; cin >> l >> r;) {
// 所求 = fac[r] / fac[l - r]
// 但因為模運算不適用於除法
// 所以要用乘法反元素 fac[r] * inv(fac[l - 1])
cout << 1LL * fac[r] * inv(fac[l - 1]) % mod << '\n';
}
}
```
:::spoiler code by fdhs107_KonChin_Shih
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define endl '\n'
using namespace std;
constexpr int mod = 998244353;
long long fpow(long long a, long long b) {
long long ret = 1;
for (a %= mod; b; b >>= 1, a = a * a % mod)
if (b & 1) ret = ret * a % mod;
return ret;
}
inline long long rev(long long a) {return fpow(a, mod - 2);}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
vector<bool> table(1000001, true);
for (int i = 2, end = sqrt(1000000); i <= end; i++)
if (table[i])
for (int j = i << 1; j <= 1000000; j += i)
table[j] = false;
vector<int> prime, prefix{1};
for (int i = 2; i <= 1000000; i++)
if (table[i]) prime.emplace_back(i);
for (auto& i : prime)
prefix.emplace_back(1LL * i * prefix.back() % mod);
int l, r;
while (cin >> l >> r) {
int a = lower_bound(prime.begin(), prime.end(), l) - prime.begin();
int b = upper_bound(prime.begin(), prime.end(), r) - prime.begin();
cout << prefix[b] * rev(prefix[a]) % mod << endl;
}
return 0;
}
```
:::
::: spoiler code by fdhs108_38002
其實可以多建一個模逆元的表，使複雜度從
$O(n\ln\ln n + q\log k)$ 變成 $O(n\ln\ln n + q)$
其中$O(n\ln\ln n)$是Eratosthenes質數篩法的複雜度，q是詢問次數
```cpp=
inline ll power(ll a, ll b) {
ll ret = 1;
for(; b; a = 1ll * a * a % mod, b >>= 1)
if(b & 1)
ret = 1ll * ret * a % mod;
return ret;
}
const ll N = 1e6;
vector<ll> fact, infact;
vector<bool> flag;
void build() {
infact = fact = vector<ll>(N + 1);
flag = vector<bool>(N + 1, 0);
fact[0] = fact[1] = 1;
for(ll i = 2; i <= N; i++) if(!flag[i]) {
for(ll j = i * i; j <= N; j += i)
flag[j] = 1;
}
for(int i = 2; i <= N; ++i) {
if(!flag[i])
fact[i] = fact[i - 1] * i % mod;
else
fact[i] = fact[i - 1];
}
infact[N] = power(fact[N], mod - 2);
for(int i = N - 1; i >= 0; --i)
infact[i] = infact[i + 1] * (!flag[i + 1] ? i + 1 : 1) % mod;
}
inline void solve() {
build();
int l, r;
while(cin >> l >> r) {
cout << fact[r] * infact[l - 1] % mod << '\n';
}
}
```
:::
---
## p7: a464. 你懂海嗎 (1800)
> [name=by fdhs107_KonChin_Shih][color=#1f1e33]
### 想法
這題是DP，主要的目標就是維護會出現的所有可能
最直覺的想法就是拿map存價格跟海產的編號
然後每個月複製那個map之後把價格加上$d_i$再放回去
並判斷`m.count(k)`就能找出所有的可能
不過map在存取插入都有一個log存在
時間應該會不夠(?)(有沒有人想試可以試試看
所以需要更快的做法
可以開一個整數dp陣列存1~10000目前可以從哪個海產經過波動後達到
然後每個月就只要用以下式子轉移(邊界自己判)
如果$dp[j]$存在海產的編號則$dp_[j+d_i]=dp_i[j]$
### code
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
vector<int> v(10000, 0);
int n, m, k, d, t = 0, tmp;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
cin >> tmp, v[tmp - 1] = i;
if (v[k - 1]) goto result;
for (t = 1; t <= m; t++) {
cin >> d;
if (d > 0)
for (int i = 9999; i >= 0; i--)
v[min(9999, i + d)] = v[i] ? : v[min(9999, i + d)];
if (d < 0)
for (int i = 0; i <= 9999; i++)
v[max(0, i + d)] = v[i] ? : v[max(0, i + d)];
if (v[k - 1]) goto result;
}
cout << -1 << endl;
return 0;
result:
cout << t << ' ' << v[k - 1] << endl;
return 0;
}
```
Sign in with Wallet
Connect another wallet