三角形
数据结构
$$ \mathcal{ST}$$
像某个 $Cbh$ 一样 $st$ 表都不会写还是不好的。所以写一篇 $st$ 表。
$ST$ 表支持维护区间问题,并且要求静态。可以达到预处理 $O(n\log n)$,而单词查询 $O(1)$ 的恐怖效率。空间复杂度 $O(n\log n)$ ,想比于线段树其应用范围稍显狭窄。
$\mathcal{But...}$ $\mathcal{ST}$ 的单词查询是 $O(1)$ 的。
下面主要以 $\min$ 操作为例介绍
$\mathcal{ST}$ 的思想主要基于倍增。
先要 $Init(log2)$ 当然如果你不嫌弃 $C++$ 的大常数 $\log_2$ 的话也不是不行。
只需要 $Init([1-n])$ 的 $\log_2$ 就好了。这一步主要是为了应付后面倍增要求。显然,$\log_2(x)=log_2(\left[\frac{x}{2}\right])+1$ 理由不想多说。按照这个步骤初始化即可。
$$\mathcal{STEP . 1}$$
然后就是预处理。可以得到一个 $\min$ 特有的关系式,大概就是这个相貌:
$$\min_{i=l} ^r a[i] = \min\{\min _{i=l} ^{k\leq r} a[i],\min_{k\geq l} ^r a[i]\}$$
等式右边的两项可以通过刚刚的方法求得。
这样就可以开始推导推导了:设 $dp[i][j]$ 表示 $\min _{k=l} ^{l+2^j} a[k]$,这里就可以出来一个转移方程:
$$dp[i][j]=\min\{dp[i][j-1],dp[i+2^{j-1}][j-1]\}$$
理由如上。
$$\mathcal{STEP.2}$$
查询操作。
$$\min_{i=l} ^r a[i] = \min\{dp[l][k],dp[r-2^k][k]\}$$
其中 $k=\log_2(r-l+1)$
理由还是如上。
$$\mathcal{STEP.3}$$
吸取了某个叫 $\mathcal{CBH}$ 同学的教训,我们可以知道 $k$ 就是 $k$ ,不要 $k-1.$
上代码。
// here is Init
void init(){
lg[0]=-1;
FOR(i,1,n) lg[i]=lg[i>>1]+1;
FOR(i,1,n) dp[i][0]=a[i];
int lim=lg[n];
FOR(k,1,lim)
FOR(s,1,n+1-(1<<k))
dp[s][k]=max(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
}
// here is Query
l=read();r=read();
int k=lg[r-l+1];
cout<<max(dp[l][k],dp[r-(1<<k)+1][k])<<'\n';
那么除了 $\min$ 之外 $\mathcal{ST}$ 还可以维护 $\mathcal{GCD,MAX,OR,LCM}$ 之类的东西。
$$\mathcal{O(n\log n)+O(n \log n)+O(1)}$$
数论
数学是科学的女皇,数论是数学的女皇。 ——高斯
$$\Huge{\Large{}}\mathcal{Q\!\!\!X}$$
$\text{Gcd} \& \text{Lcm}$
最大公因数和最小公倍数,基本上都是一些杂题。这里有一个性质:
$$\text{lcm}(a,b) = \frac{ab}{\gcd{(a,b)}}$$
这个东西是可以证明的。
设有可重集合 $A,B$ 满足
$$a=\prod A_i,b=\prod B_i$$
而
$$\gcd(a,b) = \prod A\cap B,\text{lcm}(a,b) =\prod A\cup B ,ab=\prod (A+B) \Large{\circ} \small \! \! \! \! 1$$
根据集合论,
$$A\cup B=(A+B) - A\cap B$$
则
$$\prod A\cup B = \frac{\prod A+B}{\prod A\cap B}$$
将 $\Large{\circ} \small \! \! \! \! 1$ 式代入上式,可以得到
$$\text{lcm}(a,b) = \frac{ab}{\gcd{(a,b)}}$$
证明完毕。
还有一个 $\text{lcm} (a,b)$ 是 $a,b$ 的分解质因数结果的并集之积这个性质,因为这个太过简单所以在这里不证明了。
例题
- 根据这个性质有一道 $\color{black}{P4626}$ 的题,可以用上面的定理进行推导,把每一个质数筛出来,然后找到一个最大的 $k$ 满足 $p_i ^{k_i} \leq n$ 将答案乘上一个 $p_i ^{k_i}$ 就好了,可以证明只有 $p_i ^{k_i}$ 这些以 $p_i$ 为底的质数在 $[1,n] \cup \mathcal{Z}$ 这种的分解质因数结果。
$Euler's\ Sotient\ Function$
这个是欧拉筛法 $/$ 欧拉函数。
首先给出欧拉函数的定义,也就是经典的 $\varphi(n)=\sum _{i=1} ^n [gcd(i,n)=1]$
人话就是在 $n$ 以内与 $n$ 互质的数的数量。
那么这个鬼畜玩意有什么性质呢?
下面用了《算法竞赛》上面的一堆东西。
欧拉函数是一个积性函数,当然并不是完全积性函数。也就是对于两个互质的两个数 $p,q$ 存在 $\varphi(p)\varphi(q)=\varphi(pq).$
对于任意一个正整数 $n$ 一定满足 $n=\sum _{d|n} \varphi (d).$ 至于证明可以参考《算法竞赛》。
欧拉定理:$a^{\varphi(m)} \equiv 1 \pmod m.$ 要求 $a,m$ 互素。
一个鬼畜的常用性质:设 $n$ 的质因数分解是 $\prod p_i ^{k_i}$
$$\varphi(n) =n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_r}\right)=n\prod ^{r} _{i=1} \left( 1-\frac{1}{p_i}\right)$$
这个公式有两个特殊情况:当 $n\in P$ 时 $\varphi(n)=n-1.$ 当 $n=p^k$ 时 $\varphi(n)=p^{k-1}\varphi(p)$
所以可以用试除去找到单个 $\varphi(x).$ 复杂度仅有 $\Theta (\sqrt x).$ 奇怪的 $\sqrt x$ 算法又增加了。
欧拉筛可以用 $O(n)$ 的复杂度求出 $[1,n]\cap Z$ 的欧拉函数值。
$$\mathcal{QXDATA}$$
inline void Init(void){
phi[1]=1;
for(int i=2;i<=n;++i){
if(!vis[i]) prime[++cnt]=i,phi[i]=i-1,vis[i]=true;
for(int j=1;j<=cnt;++j){
if(i*prime[j]>n) break;
vis[i*prime[j]]=true;
if(!(i%prime[j])){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
例题 $1$ 求
$$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$
根据上面欧拉函数的性质 2. 可以将原式等量代换成
$$\sum _{i=1} ^n\sum _{j=1} ^n\sum _{d|gcd(i,j)} \varphi (d)$$
然后如果 $d|gcd(i,j)$ 就有 $[d|i][d|j].$ 将 $d$ 的贡献提前,得原式可化为
$$\sum _{d=1} \varphi(d) \sum _{i=1} ^n \sum _{j=1} ^n [d|i][d|j]$$
根据 $\sum$ 的性质原式可化为
$$\sum _{d=1} \varphi(d) \sum _{i=1} ^n [d|i] \sum _{j=1} ^n [d|j]$$
根据数论的性质原式可化为
$$\sum _{d=1} \varphi(d) \left[\frac{n}{d}\right]$$
上面的中括号是高斯函数,也就是向下取整。
这个公式可以 $Euler$ 求出 $\varphi$ 然后秒杀。我都会写。
$Chinese\ Remainer\ Thoerem$
先提出一种很简单的问题:
$$\begin{cases} x \equiv 2\pmod 3\\ x \equiv 3\pmod 5\\ x \equiv 2\pmod 7\\ \end{cases}$$
求解 $x_{\min}$ 。这个问题在公元 $3$ 世纪就提出了,答案显然是 $23$。
那么如果这个问题推广又应该怎么做啊?
$$\begin{cases} x \equiv a_1\pmod {m_1}\\ x \equiv a_2\pmod {m_2}\\ \qquad \ \ \ \ \vdots \\ x \equiv a_3\pmod {m_3}\\ \end{cases}$$
其中 $\{a_i\},\{m_i\}$ 是常数。求解最小的 $x$。
我们考虑扩展 $crt$ (因为普通 $crt$) 我也不会证啊。。
$Extend\ Chinese\ Remainer\ Thoerem$
考虑对同余式子进行合并。
由 $x \equiv a_1\pmod {m_1}$ 得,$x=km_1+a_1.$
代入 $x \equiv a_2\pmod {m_2}$ ,得 $km_1+a_1 \equiv a_2 \pmod{m_2}.$
解方程得 $k\equiv \frac{a_2-a_1}{m_1} \pmod{m_2}.$
这个 $k$ 可以通过逆元求解,则 $x\equiv \frac{a_2-a_1}{m_1} \pmod{m_2}.$
依次合并,然后注意一下 $n=1$ 的情况, $\mathcal{SOLVED.}$
$\mathcal{QX\ DATA}$
LL CRT(void){
LL x,y;
LL m1=dt[1].m,a1=dt[1].a;
LL ans=0;
for(int i=2;i<=n;++i){
LL a2=dt[i].a,m2=dt[i].m;
LL a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
LL d=exgcd(a,b,x,y);
if(c%d!=0) return -1;
x = x*c/d%(b/d);
ans = a1+x*m1;
m1=m2/d*m1;
ans=(ans%m1+m1)%m1;
a1=ans;
}
return ans;
}
$Fermat's\ Little\ Theorem$
费马小定理可以求解 $\frac{b}{a} \bmod p.$ 要求 $p$ 是质数。
公式如下 $\frac{b}{a} \bmod p = b\times inv(a).$
其中 $inv(a)\equiv a^{-1} \equiv a^{p-2} \pmod p.$
其中 $a^{p-2}$ 可以快速幂。
例题 $:$
- $\color{black}{}P5431$. 可以对 $\{a\}$ 同分然后输出 $ans$,然后莫名其妙就 $AC$ 了。其中计算 $\frac{S}{a_i}$ 可以预处理前缀后缀积。
$Mobius\ Function$
了解到了一种奇怪的函数:莫比乌斯函数。
$$\mu(n) = \begin{cases} 1 &n=1\\ (-1)^r & n=\prod p (i\not =j,p_i \not = p_j) \\ 0 & Otherwise\end{cases}$$
这个函数好像很奇怪,并且用处也好像没有,虽然一眼看去这个肯定是一个系数,但是用处就很古怪了。
先给出一些关于它的性质:
$$\sum _{d|n} =\begin{cases} 1 &n=1 \\ 0 & n>1\end{cases}$$
证明省略。
那么这个看起来很鬼畜的东西有什么用呢?
有一个算术函数 $f$ , 还有一个函数 $F(n)=\sum _{d|n} f(d)$ ,那么 $F$ 是和 $f$ 有关的。显然我们可以通过带入消元法在了解 $f$ 的情况下求出 $F$ ,而且复杂度并不见得很高昂。
在列了一堆方程之后可以发现 $f(i)$ 总是由 $\sum _{d|n} \pm F(d)$ 得到。这样的话就要引出 $F$ 前面的系数了。可以经过观察得到
$$f(n) = \sum _{d|n} \mu (d) F(\frac{n}{d})$$
嗯,这样就有价值了啊 ~
但是这样还是不够。
还需要知道一个东西 $[\gcd(a,b)=1] = \sum _{d|a,b} \mu(d)$
原因是上面莫比乌斯函数的一个性质,也就是 $\sum _{d|n}$ 的性质。由此可以得到 $\sum _{d|n} \mu (d) = [n=1]$
这样的话带入一下就好了。这样带有 $\gcd$ 的方程就可以巧妙地用 $\mu$ 来求解了。
例题 $1$ 求解
$$\sum _{i=1} ^n \sum _{j=1} ^m [\gcd(i,j)=1]$$
人话就是 $n,m$ 以下的有序可重复数对互质的方案总数。
这个式子可以根据上面的式子化为
$$\sum _{i=1} ^n \sum _{j=1} ^m \sum _{d|\gcd(i,j)} \mu (d)$$
计算每一个 $d$ 的贡献,把最后一个 $\Sigma$ 放到前面,可化为
$$\sum _{d=1} ^{\max \{n,m\}} \mu (d) \sum _{i=1} ^n [i|n] \sum _{j=1} ^m [j|n]$$
然后观察后面两个 $\Sigma$ ,发现计算的是 $i$ 的倍数在 $[1,n]$ 区域内出现的频数。原式可化为
$$\sum _{d=1} ^{\max\{n,m\}} \mu(d) \left[\frac{n}{d}\right] \left[\frac{m}{d}\right] $$
这里可以暴力计算了。当然也可以数论分块优化,还要用前缀和优化优化。
例题 $2$ 求解
$$\sum _{i=1} ^n \sum _{j=1} ^m [\gcd(i,j)=k]$$
暴力除法,原式 $=$
$$\sum _{i=1} ^{\left [ \frac{n}{k}\right]} \sum _{j=1} ^{\left [ \frac{m}{k}\right]} [\gcd(i,j)=1]$$
这样就变成熟悉的认知了。
- 例题 $3$ 求解
求
$$\sum _{i=1} ^n \sum _{j=1} ^m lcm(i,j)$$
$n,m \leq 10^7 ,\ T\leq 10^4$
经过简单的莫比乌斯反演化简最后可以得到
$$\sum _{d=1} ^n d\sum_{k=1} ^{\left[\dfrac{n}{d}\right]} \mu(k)k^2 \sum_{i=1} ^{\left[\dfrac{n}{dk}\right]} i \sum_{j=1} ^{\left[\dfrac{m}{dk}\right]} j$$
好了然后注意到后面的是等差序列,可以丢尽分块处理,所以考虑 设 $T=dk, f(x)=\dfrac{x(x+1)}{2}$
代入进去得到:
$$\sum _{d=1} ^n d\sum_{k=1} ^{\left[\dfrac{n}{d}\right]} \mu(k)k^2 f(\left[ \dfrac{n}{T}\right])f(\left[ \dfrac{m}{T}\right]) $$
把后面两个 $f$ 往前面扔。枚举 $T.$ 就像之前 $cbh$ 同学往前枚举 $pd$ 是同样的道理。得到
$$\sum_{T=1}^{n} f(\left[ \dfrac{n}{T}\right])f(\left[ \dfrac{m}{T}\right]) \sum_{d|T} d\mu(d) T$$
设 $F(T) = \sum_{d|T} d\mu(d) T.$
那么原式就可以直接暴力二维整除分块了。
至于 $F$ 函数在 $\texttt{Euler}$ 筛法中处理。
$BSGS$
一种求解奇怪的同余方程的算法。先给一个题面。
给定常数 $b,n,p$ ,求 $b^l \equiv n \pmod p$ 的 $l$ 的最小整数解。
首先设 $t=sqrt(p)+1.$ 然后再设一个 $l=kt-m$,那么原式可化为
$$b^{kt-m}\equiv n \pmod p$$
根据幂的基本性质原式可化为
$$\frac{b^{kt} }{b^m} \equiv n \pmod p$$
去分母,得
$$b^{kt} \equiv b^m \times n \pmod p$$
前面的 $kt-m$ 的 $-m$ 项也可以写作 $+m$ 但是会求一个逆元,消耗了 $O(\log_2 n)$ 的复杂度,显然是不可取的。所以这里用到了一个人为的优化。
这里考虑维护一个 $Hash$ 池标记满足 $b^m \times n \equiv x$ 的 $m$ ,方便后期处理。
然后由于 $t$ 是常数,可以枚举 $k\in [0,t] \cap Z$,然后当 $b^{kt}$ 在哈希池子里面有值的时候就扯出来处理处理就完事了。
这个东西好像还是很不好调试的。中文名:大步小步算法。
inline ll BSGS(void){
n%=p,t=ceil(sqrt(p));
ll res=1;
for(int i=0;i<=t;++i)
lake[n*res%p]=i,(res*=b)%=p;
for(int k=0;k<=t;++k){
ll value=qpow(b,k*t),M=lake[value];
if(M&&k*t-M>0)
return k*t-M;
}
return -1ll;
}
其中 qpow
的部分还是可以优化的。下面是优化的版本:
lake.clear();
t=ceil(sqrt(p));
ll res=1;
for(int i=0;i<=t;++i)
lake[res*b%p]=i,(res*=a)%=p;
ll bs=Qpow(a,t);
res=1;
for(int k=0;k<=t;++k){
ll m=lake[res%p];
if(m&&t*k>=m) return t*k-m;
(res*=bs)%=p;
}
这样做还可以省去一只 $\log$。
例题:
1. $\color{black}{}P4884$。这道题可以考虑将 $111...1(n\rightarrow 1)$ 化为 $\frac{10^n-1}{9}$ 然后原式可化为
$$\frac{10^n-1}{9}\equiv K \pmod p$$
去分母,得
$${10^n-1}\equiv 9K\pmod p$$
移项得
$$10^n\equiv 9K+1 \pmod p$$
然后就可以快乐的套模板了。所以多这一个憨憨公式就可以评紫对吗