【TOI2019 二模 pA】吠市數列

題目敘述

給定一質數$p$和$a_0$, $a_1$，定義數列$\{a\}$滿足遞迴式
$$a_n=a_{n-1}+a_{n-2}+1,\, \forall n \ge 2$$
現在我們知道$x$, $a_x$, $y$, $a_y$, $k$，求$a_k$。若無解輸出$-1$，若有超過一解輸出$-2$
$x$, $y$, $k$都在long long範圍內，$p$在int範圍內

作法

首先根據簡單的運算我們有
$$a_n=F_{n-2}a_0+F_{n-1}a_1+F_{n}-1$$
其中$\{F\}$為費波那契數列（$F_0=F_1=1$），且$F_{-1}=0$, $F_{-2}=1$
令$a=F_{x-2}\%p$, $b=F_{x-1}\%p$, $c=F_{y-2}\%p$, $d=F_{y-1}\%p$, $e=F_{k-2}\%p$, $f=F_{k-1}\%p$ （用矩陣快速冪等方法求得）
我們有
$$ag_0+bg_1 \equiv a_x -(F_{x}-1) \pmod p$$
$$cg_0+dg_1 \equiv a_y -(F_{y}-1) \pmod p$$
然後想要知道
$$eg_0+fg_1$$
是多少
二元一次聯立方程式式國中課程內容，但如果套用到模運算下會很麻煩，尤其我們並不是真的要求$g_0$, $g_1$，而只要$eg_0+fg_1$。以下提供一個暴力分case的方法，雖然應該存在簡短的方式，但這種直覺的作法應該不容易漏case。

首先有個簡單的Lemma説對於所有質數$p$，不存在$i$使得$F_i$, $F_{i+1}$都是$p$的倍數，證明會在後面補。所以不會發生$a=0$且$b=0$，也不會發生$c=0$且$d=0$的情況。接下來就是分類了：

$\mathbf{a=0}$

      首先我們可以用$bg_1 \equiv a_x -(F_{x}-1)$求出$g_1$，然後代入第二條式子得到
$$cg_0 \equiv a_y -(F_{y}-1)-dg_1 \pmod p$$
  1. 若$c=0$
    • $a_y -(F_{y}-1)-dg_1 \equiv 0$，則無限多組解
    • 否則無解
  2. 若$c\neq 0$，直接計算出$g_0$然後算出$eg_0+fg_1$，唯一解

$\mathbf{c=0}$

      同上，但在程式實作時如果使用else if，那我們知道$a\neq 0$，所以可以少一個case

$\mathbf{a\neq 0}$且$\mathbf{c\neq 0}$

  1.  $ad\equiv bc$
    • 若兩直線方程式重疊，則看看$eg_0+fg_1$是不是和剛剛兩條方程式平行，若平行則唯一解，否則無限多解（個人認為這個case最容易漏）
    • 若兩直線方程式平行，則無解
  2. $ad\not\equiv bc$
    • 直接算出唯一的$g_0$,$g_1$，此時一定唯一解

Lemma證明

若$p \mid F_{i}$且 $p\mid F_{i-1}$，則$p\mid F_{i-2}=F_{i}-F_{i-1}$，同理$p\mid F_{i-3}$。用數學歸納法可得$p\mid F_{1}=1$，矛盾。


最後附上程式碼，因為是賽中寫的code，所以可能會有多餘的判斷式>_<

後記

比賽中解出這題的人只有我和baluteshih，相信應該不少人花很多時間仍然掉case QQ

留言

張貼留言

這個網誌中的熱門文章

【TOI2019 三模 pD】自助餐

圖片
題目敘述 題目連結： https://tioj.ck.tp.edu.tw/problems/2077 Output only題。 給定正整數$n$, $k$, $d$, $T$，找出$T$個集合$S_1,S_2,...,S_T$滿足  $S_i \subset \{0,1,2,...,n-1\}$  $|S_i | = k$  $\forall i \neq j,\, | S_i \cap S_j | \le d$ Subtask $n=5$, $k=3$, $d=2$, $T=10$ $n=8$, $k=5$, $d=3$, $T=8$ $n=20$, $k=12$, $d=7$, $T=16$ $n=64$, $k=32$, $d=16$, $T=125$ $n=65$, $k=32$, $d=17$, $T=125$ $n=49$, $k=7$, $d=3$, $T=2401$ $n=121$, $k=11$, $d=4$, $T=161051$ $n=1369$, $k=37$, $d=2$, $T=50653$ $n=49$, $k=7$, $d=5$, $T=117649$ 作法 大致上可以把這些subtask分成三類：  Subtask 1~3是小測資。  Subtask 4~5是$n$為二的冪次的測資，我們可以注意到把Subtask 4的全部集合補上一個65就是Subtask 5的答案了。 Subtask 6~9都滿足特定的規律：$n=k^2$, $T=k^{d+1}$ 接著一個一個說明每一類的作法： Subtask 1~3 $n=5$直接枚舉所有5取3就可以了，$n=8$也可以自己手構一下 而$n=20$就得跑程式爆搜了，一個作法是從$S_1$慢慢選擇到$S_T$，要選擇$S_t$時，random產生1000個候選集合$s_1,s_2,...,s_{1000}$，把那些不符合條件（aka $\exists j<t,\, |S_j \cap s | > d$）的篩掉，然後找 $$\sum _{i=0}^{t-1} |S_i \cap s |$$ 最大的$s$，然後讓$S_t=s$。 這個作法跑十秒鐘大概10輪內就有結果了(?
閱讀完整內容

【TOI2019 三模 pA】圓的最佳覆蓋

圖片
題目敘述 平面上有$n$個點，請問一個半徑為$r$的圓內部最多可以有幾個點？（圓周視為內部） $n\le 1000$, 值域和$r$都在$10^4$內 作法 一個很直覺的想法是如果有一個最佳狀況的圓，我們總是能稍微調整讓這個圓貼住其中至少兩個點，也就是說圓周上至少會有兩個點。這樣枚舉所有$\binom{n}{2}$個點對，畫一個半徑$r$且經過這兩點的圓，然後檢查每個點是不是在這個圓的內部，複雜度為$O(n^3)$，賽中只能拿到60分。 只要枚舉點對複雜度就已經$O(n^2)$了，後面檢查應該沒什麼機會更快，這代表枚舉點對行不通。所以我們試試看只枚舉一個點，然後看所有經過這個點的圓內部有幾個點。 假設現在固定圓要經過一個點$A$，那這個圓的圓心$O$必須在$A$為圓心，$r$為半徑的圓上。 一個重要的觀察是：對於其他的點$P$，當圓心在某個夾角內的時候，這個點才會在圓的內部裡面，如下圖所示。 有了這個觀察，題目就變成環狀區間加值，最後問最大值的問題，簡單做個差分就解決了。 那要怎麼計算一個點貢獻什麼區間呢？這可以用簡單的三角函數計算，如圖 如果$P$剛好在圓$O$上時，$OP=OA=r$，所以$\alpha=cos^{-1}(\frac{d}{2r})$，所以假設向量$AP$的幅角是$\theta$，那區間就是$[\theta-\alpha,\theta+\alpha]$。 實作上，因為是環狀的，所以先計算圓心角度為$0$的答案，然後繞一圈去更新答案即可。複雜度為$O(n^2logn)$（枚舉固定點$O(n)$，排序和差分$O(nlogn)$）。 附上程式碼
閱讀完整內容