逆元与笛卡尔树

碎碎念

小屁孩什么的最讨厌了

Day2

今天教小孩写选择结构，有些小孩大括号怎么也理不清emm

晚上给提高班整了场模拟赛（我白天才刚学会）

结果正常提高的难度，最高分才100+，大部分的连暴力分都拿不到

怎么说呢，一言难尽，才发现比赛经验真的是一个选手实力的重要组成

Day3

选择之后自然是循环了，emmm，这届小孩真难带

不是很理解四五年级的小学生，天赋也不是很高，为啥硬要来学编程

一个判断区间内6的倍数能写大半个小时...

Day4

今天份满级小孩...我给大家复刻一下他的代码，保证原汁原味无修改

#include <bits/stdc++.h>
using namespace std;
int main (){
	int n;
	scarf ("%d",&n&;
	while (i>=n)
	i+=i
	
		if (n%2=a);
		printf ("%d",a);
}
	return 0;
}

一想到我还要教他九天，直接玉玉了我

有没有一种可能，打完这次工，我直接患上恐娃症

之前说到的那个大一新生竟然叫我老师哎，直接飘飘然~

--------碎碎念到此结束，下面是正文（手动分割线）--------

Day2白天学的线性求逆元与线性求笛卡尔树

逆元

inv[1]=1;
for(int i=2;i<=n;++i)
  inv[i]=MOD-(long long)MOD/i*inv[MOD%i]%MOD;

首先当 MOD 为质数时一定有 MOD = a * i + b，1 < i < MOD，0 < b < i

此时在 %MOD 意义下有 a * i + b = 0 即 b = - a * i

等式两边同时除以 b * i 得 1 / i = - a / b 即 inv[i] = - a * inv[b]

其中 a = MOD / i，b = MOD % i

整理一下就得到了线性逆元递推式 inv[i]=MOD-MOD/i*inv[MOD%i]

笛卡尔树

int st[N], ls[N], rs[N], n, A[N];// ls代表笛卡尔树每个节点的左孩子，rs代表笛卡尔树每个节点的右孩子
int top = 0;

for (int i = 1; i <= n; ++i) 
{
    while (top && A[st[top]] > A[i]) ls[i] = st[top--]; //栈顶元素为当前元素的左孩子
    if (top) rs[st[top]] = i; //当前元素为栈顶元素的右孩子
    st[++top] = i;
}