关于倍增 学习博客 前几天\(lyk\)给我们讲了倍增但是\(emmmm\)他说话声音也太小了，坐在后排根本听不清楚诶，前边一群大佬还在叽叽喳喳的说话，上课效率低得一批。 \[\color{purple}{我太难了}\] 顾名思义倍增就是倍增，用\(dsr\)大佬的话来说就是\(wuwu\)腻。 我们有一个数组\(f[i][j]\)表示从\(i\)开始的长度为\(2^j\)的区间即区间\([i,i+2^j]\) 递推公式： 预处理ST表 \(f[i][j]=max(f[i][j-1]),f[i+2^{j-1}][j-1]\) 说句闲话： 为什么这么写？我之前第一遍自己学的时候，看其他人的博客，...

首先请允许我吐槽一下这个题面 这个题面透露出血腥与暴力，电影院里还藏汽油 所以情侣们，要是想看电影就在家里看吧 毕竟出来容易被烧 在家里看虽然观影效果不如在电影院里 但是， 起码咱生命安全啥的有保障啊 题面 思路： tarjan 注意方案数是乘法原理  #include <cstdio> #include <iostream> using namespace std; const int N = 1e6+7; const int md = 1e9+7; int n, head[N << 1], cnt, w[N], m, dfn[N], low[N], to...

费马小定理 他是欧拉定理的一种特殊情况 内容： 对于质数\(p\),任意整数\(a\)，均满足\(a^{p-1}=1(mod \ p)\) 证明： 在\(p\)为素数时，\(\varphi(p)=p-1\) 我们也已经知道了\(a^{\varphi(n)} \equiv 1\) 所以把\(\varphi(n)=n-1\)带进去就好啦 应用： 求乘法逆元 谢谢收看，祝身体健康！（话说这么短我为什么还要开一篇......可能是为了凑篇数

\[\text{乘法逆元}\] 学习博客 定义： 这是来自大佬博客的： 对于缩系中的元素，每个数\(a\)均有唯一的与之对应的乘法逆元\(x\)，使得\(ax \equiv 1 (mod \ n)\)，一个数有逆元的充分必要条件是\(gcd(a,n)=1\)，此时逆元唯一存在 求逆元的几种方法 1.扩展欧几里得算法 设\(a\)的逆元是\(x\) ，\(x\)满足\(ax\equiv1\)（这是上边定义里已经说了的），因为除法的实质是减法所以，方程也可以写为\(ax-my=1\)，求得一组解之后判断\(gcd(x,y)\)是否是一，如果不是则说明不是，因为我们用\(exgcd\)求得就是一组最...

学习博客 欧拉定理: 内容： 若正整数\(a,n\)\(\color{red}{互质}\)，则\(a^{\varphi (n)}\)\(\equiv\) $1(mod $ \(n)\) 其中\(\varphi (n)\)是欧拉函数$(1 $~ \(n)\)与\(n\)互质的数 证明： 设\(x_1,x_2,x_{\varphi (n)}\)是\(1\)到\(n\)中与\(n\)互质的数 这些数有如下性质： \(1\).任意两个数模\(n\)余数不同。因为这些数比\(n\)小，且互不相同，所以他们模完之后是本身，那么余数一定互不相同。 \(2\).对于任意的\(ax_i(mod\) \(n)\)...

排列： 从\(n\)个人中选出\(m\)个人来排队，他的做法是\(A_{n}^{m}\) 第一个位置可以放\(n\)个中的一个，第二个位置可以放\(n-1\)个中的一个......第\(m\)的位置可以放\(n-m+1\)个中的一个 所以可得：\(A_{n}^{m}=\frac{n!}{n-m!}\) 组合： 上面的问题我们可以分两步来看 1.选出\(m\)个人 2.这\(m\)个人排队 所以\(A_{n}^{m}=X*A_{m}^{m}\) 这个X就是从\(n\)个人中选出\(m\)个人来的方案数 所以\(X=C_{n}^{m}=\frac{A_{n}^{m}}{A_{m}^{m}}=\fr...

搓牌 顾名思义就是搓牌，我们要搓牌，就要知道一些常识，下面来介绍一下 定义： 现在我们有\(a\)数组存储了\(1-n\)这几个数，要求任意一项都满足\(a[i] != i\)，求有多少种排列方式 公式： \(f(n)=(n-1)[f(n-1)+f(n-2)]\) 简单证明： 设\(a\)装入\(B\) 则有两种情况 \(1.\)\(b\)装入\(A\)则剩下\(n-2\)个物品就是\(f(n-2)\) \(2.\)\(b\)不装入\(A\)则就是\(f(n-1)\) 除讨论\(a\)外我们还可讨论\(b、c、d......\)共有\(n-1\)种情况 所以\(f(n)=(n-1)[f(n-1...

秦九韶公式 作为语文课代表我当然要为大家科普一下一些常识~ 秦九韶（约公元1202年－1261年），字道古，南宋末年人，出生于鲁郡（今山东曲阜一带人）早年曾从隐君子学数术，后因其父往四川做官，即随父迁徙，也认为是普州安岳（今四川安岳县）人秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家。（安岳县于1998年9月正式开工建设秦九韶纪念馆，2000年12月竣工落成。）秦九韶聪敏勤学，宋绍定四年（公元1231），秦九韶考中进士，先后担任县尉、通判、参议官、州守等职。先后在湖北、安徽、江苏、浙江等地做官。南宋理宗景定元年（公元1260年）出任梅州太守，翌年卒于梅州。据史书记载，他“性及机巧，星象、音律、算...

题目 x和\(a_0\)的最大公约数是\(a_1\) x和\(b_0\)的最小公倍数是\(b_1\) \(gcd(x,a_0)=a_1\) \(gcd(x/a_1,a_0/a_1)=1\) \(\tag{1}\) \(lcm(x_1,b_0)=b_1\) \(\frac{x*b_0}{gcd(x,b_0)}=b_1\) \(gcd(x,b_0)=\frac{x*b_0}{b_1}\) \(gcd(x/\frac{x * b_0}{b_1},b_0/\frac{x*b_0}{b_1})=1\) 化简可得 \(gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1\) \(\ta...

快速幂 这个先上Code吧 int power(int x, int y) { int sum = 1; while(y) { if(y & 1) sum *= x; x *= x; y >>= 1; } return sum; } 众所周知\(p^a * p^b=p^{a+b}\) 我们现在需要求\(x^y\) 举个栗子，我们求\(3^5\) 我们把\(5\)拆成二进制\(101\) 可以发现正正好的在二进制下的位数只要是\(1\)的乘起来就是答案 emmmm，可能我说的不是特别的严密 就是\(3^5=3^{1*2^0+0*2^1+1*2^2}\) 把有\(0\)的一项直...

内容： \(gcd(a,b)=gcd(b,a\% b)\) 用途： 这不废话嘛，当然是用来求最大公约数啊 证明：(这还是四月份的时候cdx巨佬给我讲的qwq) 设\(d=gcd(a.b)\) 则有\(a=md,b=nd\), \(\Rightarrow\) \(a-b=(m-n)d\) \(\because\) \(m\)与\(n\)互质 \(\therefore\) \((m-n)\)与\(n\)互质 \(\therefore\) \(gcd((m-n)d,nd)=d\)即\(gcd(a-b,b)=d\) \(\therefore\) \(gcd(a,b)=gcd(a-b,b)\) \(\t...

题目 树形dp 设f[i][j]表示走到第i号节点的最大权值 j为0/1表示这个点选或者不选 如果这个点不选 就从他的子树里的选或者不选选最大 如果这个点选 就加上他子树的不选 f[x][0] += max(f[to][1], f[to][0]); f[x][1] += f[to][0]; 注意第二维要开到2 Code:  //设f[i][j]表示选到第i号节点的最大权值  #include <cstdio> #include <iostream> using namespace std; const int N = 500010; int f[N][2], n, he...

我现在才开始整理这个不算晚吧...... 望轻喷 学习博客 我们需要四个程序 1.暴力 2.“正解” 3.数据生成器 4.检查程序 暴力: 就是暴力 eg：  #include <cstdio>#include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a + b << endl; return 0; }  正解： 你觉得挺对的程序  #include <cstdio>#include <io...

题目 打死我也没想到是贪心 虽然是lkx写了贪心题解让我去点赞我才写的这道题 神仙思路 首先排好序 假设我们现在只有一块木板 我们做一个差分数组 对这个差分数组排序之后 一次断开最长的区间 m-1次之后 便可以得到最小的啦 需要注意的是 此题有坑点需要特判提供的木板数比牛棚数还多的情况 那种情况直接就输出牛棚的数量就好啦  #include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int N = 2100; int cow[N], m, s, c...