misc - HackMD

<style> .reveal .slides { text-align: left; } </style> <div style="font-size: 30px"> # misc </div> Competitive programming 2 2021/11/08 ---- * 模運算 and 模逆元 * 均攤分析 * 旋轉卡尺 * 爆搜剪枝技巧 --- ### 模運算 <div style="font-size: 30px"> $a+b \pmod{p} \to$ (a+b)%p $a-b \pmod{p} \to$ ((a-b)%p+p)%p $a*b \pmod{p} \to$ (a*b)%p $a\ /\ b \pmod{p} \to$ ??? </div> ---- 要在 $mod$ 空間做除法運算好像有問題而我們先把除法運算 $/ x$ 表達成 $* \frac{1}{x}$ 如果我們找到 $x^{-1} (\frac{1}{x})$ 就可以直接用乘法了 ---- ### 模逆元 #### (Modular multiplicative inverse) <div style="font-size: 30px"> 模反元素也稱為模倒數，或者模反元素。 $a^{{-1}}\equiv b{\pmod {p}}$ 等價於下面的式子 $ab\equiv 1{\pmod {p}}$ 所以...我們要找的東西其實就是模逆元，找出 $a$ 的模逆元 $b$ 就可以把 $/\ a$ 變成 $*\ b$ 了! </div> ---- ### 費馬小定理 <div style="font-size: 30px"> 如果 $a, p$ 互質 (通常 $p$ 都一個很大的質數，所以一般題目都會互質) $a^p \equiv a \pmod{p}$ $\to a^{p-1} \equiv 1 \pmod{p}$ $\to a^{p-2} \equiv \frac{1}{a} \pmod {p} = a^{-1} \pmod{p}$ </div> ---- <div style="font-size: 35px"> 結論：$\frac{1}{a}\pmod{p} \equiv a^{p-2}$ 因此我們之後要求 $/\ a$ 時改成 $*\ a^{p-2}$ 就好 (記得使用快速冪計算) </div> ```cpp= ll mypow(ll x,ll y,ll m){ //x^y % m ll ret = 1 % m; while(y){ if(y&1) ret = ret * x % m; x = x * x % m y >>= 1; } return ret; } ``` ---- <div style="font-size: 35px"> 所以算出一個數字的模逆元，複雜度是 $O(lgN) (快速冪)$ Q 次詢問就會變 $O(QlgN)$ 雖然 $lgN$ 是常數(X 但有些毒瘤題目還是會卡你 </div> ---- ### 建表直接砸[模板](https://github.com/jakao0907/contest/blob/master/math/prefixInv.cpp) 可以做到 O(N) 建完 1~N的所有模逆元 ---- ### 求組合數 $\binom{n}{k} \pmod{p}$ <div style="font-size: 35px"> 方法1：建表 $\to O(N^2)$ 詢問 $O(1)$ 大家都會不用講但如果 $n, k \le 10^5 \to$ TLE QQ </div> ---- $\binom{n}{k} = \frac{n!}{(n-k)!k!}$ $\binom{n}{k} \pmod{p}$ = n! * inv((n-k)!) * inv(k!) $\pmod{p}$ ---- 一樣我們可以先 O(N) 建出所有1! ~ N! ```cpp= f[0]=1; // 0! = 1 for(int i=1;i<=n;i++){ f[i] = f[i-1] * i % mod; } ``` ---- 那如果要建 1! ~ n! 的模逆元呢? ```cpp= for(long long i=0;i<=n;i++){ inv[i] = pow(f[i], mod-2); } ``` $O(NlgN)$ 但還可以再快 ---- $\frac{1}{N!} * N = \frac{1}{(N-1)!}$ <div style="font-size: 35px"> 因此我們先算出 N! 的模逆元，就可以 O(N) 算出剩下階乘的模逆元了 </div> ```cpp= inv[n] = pow(f[n], mod-2); for(long long i=n-1;i>=0;i--){ inv[i] = inv[i+1] * (i+1) % mod; } ``` ---- <div style="font-size: 35px"> 因此我們就可以 O(N) 建表 O(1) 查表 </div> ```cpp= ll C(int n,int m){ return f[n] * inv[m] % mod * inv[n-m] % mod; } ``` --- ## 均攤分析 ### Amortized Analysis <div style="font-size: 30px"> 常用於動態資料結構複雜度分析最差情況下，單次複雜度會達到 O(N)，但經過平均下來，每次複雜度變為 O(1) </div> ---- ### stack 的均攤分析 <div style="font-size: 30px"> $Q(Q\le10^5)$筆操作，每次選以下一種操作 * push(x) 每次把一個元素x放進stack * pop() 把最頂端的元素pop掉 * multi-pop(k) pop掉最頂端k個元素 </div> ---- <div style="font-size: 30px"> * push(x) 每次把一個元素x放進stack * pop 把最頂端的元素pop掉 * multi-pop(k) pop掉最頂端k個元素前兩種均為 $O(1)$ 第三種最差為 $O(N)$ 而如果詢問每次都是第三種操作複雜度就會變成 O(NQ)? </div> ---- <div style="font-size: 30px"> 實際上，會發現最差的情況是 pop 掉所有元素並且此操作一定小於 push 操作的數量以下 $T(N)$ 為總複雜度， $C_i$為每次操作 $T(N) = \sum\limits_{i=1}^{n} C_i$            $= push + pop$            $\le 2 * push$            $\le 2 * n$ </div> ---- <div style="font-size: 30px"> 因此均攤後，單次操作複雜度平均為 $O(1)$ $T(N)/n = O(N)/n = O(1)$ </div> ---- ### 二進位計數 <div style="font-size: 30px"> | value | | $bit_3$ | $bit_2$ | $bit_1$ | $bit_0$ | | cost | | ----- |-| ------- | ------- | ------- | ------- |-| ---- | | 0 | | 0 | 0 | 0 | 0 | | 0 | | 1 | | 0 | 0 | 0 | <div style="color:red;">1</div> || 1 | | 2 | | 0 | 0 | <div style="color:red;">1</div> | <div style="color:red;">0</div> || 2| | 3 | | 0 | 0 | 1 | <div style="color:red;">1</div> || 1| | 4 | | 0 | <div style="color:red;">1</div> | <div style="color:red;">0</div> | <div style="color:red;">0</div> || 3| | 5 | | 0 | 1 | 0 | <div style="color:red;">1</div> || 1| | 6 | | 0 | 1 | <div style="color:red;">1</div> | <div style="color:red;">0</div> || 2| | 7 | | 0 | 1 | 1 | <div style="color:red;">1</div> || 1| | 8 | | <div style="color:red;">1</div> | <div style="color:red;">0</div> | <div style="color:red;">0</div> | <div style="color:red;">0</div> || 4| </div> ---- <div style="font-size: 30px"> 最差情況下，每個位元都會變動 $k$ 個位元， $n$次操作就變成 O(nk) 實際上? </div> ---- <div style="font-size: 30px"> $k$ 個位元，每個位元變動頻率為每 $2^k$ 會變動一次因此總複雜度為 $T(N) = \sum\limits_{i=1}^{k} (n / 2^k)$            $= n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + ...$            $\le 2 * n$ 均攤後，每筆操作複雜度為 $T(N) / N = O(1)$ </div> ---- ### 結論 <div style="font-size: 30px"> 很多看起來複雜度爆表的題目實際上好好的均攤分析，複雜度一定是好的而且通常不會太難做，只是考你會不會算複雜度而已 </div> --- ### [旋轉卡尺](https://hackmd.io/@jakao/2021winterTraining1) --- ## 爆搜 <div style="font-size: 30px">    by SUNGOD [![](https://i.imgur.com/STPp1QO.png =300x)](https://www.cnblogs.com/jaszzz/p/12722445.html) </div> ---- ### 例題1 [Grid Paths](https://cses.fi/problemset/task/1625) ---- ### 例題2 [CodeForces 1574D : The Strongest Build](https://codeforces.com/problemset/problem/1574/D) ---- ### 例題3 [UVA 10817 : Headmaster's Headache](https://vjudge.net/contest/464705#problem/B) --- ### 期中考 <div style="font-size: 30px"> 11/13 練習賽暫停一次 11/15 期中考周暫停上課一次好好準備期中考考完的星期六 11/20 繼續練習賽 </div> ---- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/467479) <div style="font-size: 30px"> 提交期限到 ICPC 前的星期三 11/24 23:59 截止 ~11/6 以前的練習賽補題也到 11/24 23:59截止 <div style="color:red;">HW 3、4 一樣延期到 11/24 23:59 截止</div> </div>