今天写的很水,因为时间全拿来背模版了。
今日主要学习了单调队列,快速幂,数论。
中午记得重新过链接描述。(已重过)
一.单调队列
单调队列和单调栈从理论上而言其实差不多。
不过单调队列更灵活,更好玩。
单调队列可以辅助DP,将O(n2)O(n^2)O(n2)优化成O(n)O(n)O(n)。
一般优化的是跳跃型,区间型DP。
区间跟传统的区间不一样,更滑动窗口的窗口更像。
单调队列模版:
二.快速幂&数论
说实话,数论有点恶心,我为了背二元一次方程的模版下午多喝了一袋咖啡,但愿我今晚能有好的睡眠。
二元一次方程:
快速幂:
逆元: