寒假复习之各种课程笔记（2）
2026-02-06 09:12:09
发布于：北京
9阅读
0回复
0点赞
有点太多了。
堆不下了。喵。
我们来讲讲快速幂。
链接描述
事情是这样的：
给出 a b p
需要你求出 a^b % p的数值。
做法是这样的：
已知： 3^50 = 3^32 * 3^16 * 3^2
将50（b）分解成 3 的幂次。
即可。
实现：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=1;
int main(){
ll a,b,p;
cin>>a>>b>>p;
ll now=a;
ll s=0;
if(1&b){
ans=a;
s++;
}
for(int i=1;;i++){
now=((now%p)*(now%p))%p;
now%=p;
if((1ll<<i)>b)break;
if((1ll<<i)&b){
ans=((ans%p)*(now%p))%p;
s+=i;
}
if(s==b)break;
}
cout<<a<<"^"<<b<<" "<<"mod"<<" "<<p<<"="<<ans;
return 0;
}
今天上午考试去了。
拉完了。
为什么我T1爆零？
T1：
链接描述
镜面质数
这题纯sb。
空间卡的很严很。非常不通人性。
我就是空间开大了。
爆零了。
真服了。
就这么对我啊。
以后现在平台上过一次。
T2：
链接描述
这道题还挺难的。
大概是黄题吧。
是 双指针 + STL 的结合体。
T4：一直在你身旁 下位紫
这道题用的是一个区间DP+单调队列优化
dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k+1][j])+a[k]);
如果说，不对其进行优化，那么时间复杂度是在O(n^3)级别。有85分。
我们的目标是将其时间复杂度降低到O(n^2)级别，获得100分。
那么如何对其进行优化呢？
是这样的，区间DP有一个基础的框架，外面的两层一般是舍不掉的。
那么能够优化的，就是最后的那一层O(n)级别的。
如何优化？
根据观察可以发现：dp[i][k] 和 a[k] 会随着时间的推移逐步递增。
而每一次选择，我们都是在dp[i][k]和dp[k+1][j]中选择一个更大的去与dp[i][j]进行比较。
那么不难得出，每一次循环，都会有一个中位值mid。使得dp[i][mid-1]<dp[mid][j] 并且 dp[i][mid]>=dp[mid+1][j]的。
而所有会被选择的dp[i（固定）][k（>mid)]中，最小的就是dp[i][mid]。
这里空空如也
有帮助，赞一个