---
# System prepended metadata

title: 電資圈接力Challange

---

# 電資圈接力Challange
總之是被tag了吧
雖然我只是個上不去橘的小廢物
但還是來寫一下8
原本是想用DP寫學資的排組題
但我找不到我高一的學資，所以就算ㄌ
就寫一下最近戳到的題目好惹
然後只寫一題感覺好爛，畢竟我的程度能介紹的題目都不是那種太難的題目
所以多寫個幾題好惹

//結果我寫完第一題就開始做其他事忘ㄌ寫其他題了，我就拖

## [TIOJ 1927 同步sync](https://tioj.ck.tp.edu.tw/problems/1927)
這題我覺得滿有趣的，然後裡面的數學我真的不會，是查了才知道，也就是說我賽中肯定做不出來
但很酷，所以我還是寫寫看好了
### 題敘
有一個長度為 $n$ 的一維棋盤，每格上均寫了一個正整數 $a_i < 10^9 + 7$
而若 $(a_i\times a_j)^\frac{p-1}2 \equiv 1 \mod p (p = 10^9 + 7)$ 則稱點 $i,j$ 是同步的
若兩個人站在的點是同步的，則他們會一起前進一格，直到他們所在的點不再同步或是一個人走到了棋盤終點為止

接下來有 $q$ 筆詢問
每筆詢問問你兩個人分別從點 $a,b$ 開始，他們一共可以同步幾次
### Solution
:::spoiler 數學的部分
首先根據費馬小定理我們知道 $\forall n \in N, n ^ {p-1} \equiv 1 \mod p$
然後我們可以把同步的條件改寫成 ${a_i}^\frac{p-1}2 \times {a_j}^\frac{p-1}2 \equiv 1 \mod p$

這時候就是酷酷的事情了，我們可以證明$\forall n \in N, n^\frac{p-1}2 \equiv \pm 1 \mod p$
我覺得可以理解成在模p下開根號，但我不會數學，所以我還是不知道他為什麼是對的
但有了這件性質之後，我們就可以好好的對他做事了

阿這個部分因為我數學太爛，所以我是去看題解，看到第一行這樣講之後才會ㄉ
但因為真的很酷，所以我想寫他w
:::
::: spoiler 後面的部分
接著可以直接對每個點求他的 $\frac{p-1}2$ 次方，由於這個值一定是 $\pm1$
因此我們可以知道兩點同步的條件其實是兩點是否相等
所以對於每筆詢問，我們求的其實是以 $a,b$ 為起點的最大相同子字串為多少
這件事的作法應該很多（？
總之我的作法是rolling hash之後去二分搜最大的共同子字串
這部分就很容易ㄌ，總之我笨我不會數學，但我喜歡這題
:::
[AC code](https://pastebin.com/4D7tw0i8)


## [CF 1468 pD Firecrackers](https://codeforces.com/contest/1468/problem/D)
這題其實應該滿簡單的
但大概半年多前我第一次看到這題的時候我寫不出來，然後8e7覺得我怎麼會寫不出來
但我那時候就真的很笨咩噗（現在還是很笨咩噗
總之最近在USACO Guide Silver看到這題，所以就回去把這題寫掉了
順便譴責一下為什麼自己以前寫不出這題==

### 題敘
有一個長度為 $n$ 的一維走廊，有一個歹徒在第 $a$ 格，一個警衛在第 $b$ 格
歹徒手上有 $m$ 個鞭炮
其中第 $i$ 個鞭炮會在被引燃後 $s_i$ 秒爆炸

每秒鐘會依序發生三件事
1. 歹徒可以選擇動或不動，動的話可以往左或右移動一格，但不能離開邊界。如果不動，則可以引燃一個鞭炮
2. 若鞭炮 $i$ 在$T$ 秒時被引燃，則在 $T + s_i$ 秒的這個階段鞭炮會爆炸
3. 警衛會朝歹徒前進一格，如果警衛跟歹徒在同一格，則歹徒被抓到了

而題目求歹徒在被抓到前，最多可以看到幾個鞭炮爆炸

$n,a,b,s_i \leq 10^9, m \leq 2 \times 10^5$

### Solution
:::spoiler solution
首先，可以先假設 $a < b$，如果不是的話轉一下就好

接著可以知道，能放的鞭炮量是固定的 $b - a + 1$，而歹徒一定會在第 $b - 1$ 秒被抓到
因此只要考慮一個簡單的greedy，也就是將煙火由大到小排序
並且只要這個煙火爆炸看的到就放它並進到下一秒
看不到的話就換時間更快的煙火，直到煙火沒了或一定得跑了為止

[AC Submission](https://codeforces.com/contest/1468/submission/121396606)

喔然後附上我幹過最[愚蠢的WA法](https://codeforces.com/contest/1468/submission/121396504)ㄌ
我把`a = n - a + 1; b = n - b + 1;`寫成`a = n - a + a; b = n - b + a;`
重點是還過了7組測資，他甚至是多筆測資的題目欸？？？
害我以為我寫爛ㄌ

然後我半年前真的好笨，看來進不去選訓是活該（雖然現在再考一次大概還是進不去

:::


## [NHDK Ten Point Round 11 pC Gunjyo與骰子](https://codeforces.com/group/H0qY3QmnOW/contest/333897/problem/C)
滿有趣ㄉ題目，總之希望NHDK可以多出一點div. 1場，有固定的中文比賽可以打還不錯XD

### 題敘
總之有三個100面骰，然後把骰出來的結果排成一列之後
可以在兩個空隙分別塞一個 + 或 *
然後問你有幾種組合方式會使最後的結果是 $n$ （不同的運算子塞法算不同的組合方式etc. 1 * 1 + 1, 1 * 1 + 1 算兩種）

### Solution
:::spoiler solution
個人覺得直接看code就可以理解了
:::spoiler code
:::spoiler 你確定要看嗎
:::spoiler 你要確定欸
[好啦給你看](https://drive.google.com/file/d/11KRJRWVv_a0bQON4nd3Pq3h0Msuw-BGm/view?usp=sharing)，強烈建議使用電腦打開這份檔案
想必大家都會寫這題了吧，是不是很有趣呢
只要50000多行就能AC了ㄛ
喔然後附上我[本機打表的扣的](https://www.theraleighregister.com/nhdk11benjidabiao1.html)
:::

    
:::spoiler 欸不是
~~這哽484其實已經不好笑了咩噗~~
喔還有cf有檔案大小限制，所以其實根本傳不上去www
而且不止cf傳不上去，hackmd傳不上去、pastebin也傳不上去，我只好用drive XDD
:::
