简单的 代码优化（竞赛）
图论中：
节点度是指和该节点相关联的边的条数，又称关联度。
特别地，对于有向图，
节点的入度 是指进入该节点的边的条数；
节点的出度是指从该节点出发的边的条数。
入度
入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和。
入度的常见情况：
入度为0，顾名思义，入度为0指有向图中的点不作为任何边的终点，也就是说，这一点所连接的边都把这一点作为起点。
度的相关定理：
定理1 无向图中所有顶点的度之和等于边数的2倍，有向图中所有顶点的入度之和等于所有顶点的出度之和。
定理2 任意一个无向图一定有偶数个（或0个）奇点（度为奇数的顶点）。
定理3 无论无向图还是有向图，顶点数n，边数e和度之间又如下关系：
$E=(d[v1]+d[v2]+…+d[vn])/2$;
最短路计数
增加一个cnt数组，表示到达这个点的最短路总方案
在松弛操作中 如果大于就继承，如果等于就 +=
注意如果有重边的话则使用邻接矩阵
void Dijkstra(){
priority_queue<node> q;
mem(dis,127);
q.push((node){1,0});
dis[1] = 0;
ans[1] = 1;
while(!q.empty()){
node u = q.top();
q.pop();
if(u.dis != dis[u.num]) continue;
for(...){
if(dis[it->v] > u.dis + it->val){
dis[it->v] = u.dis + it->val;
ans[it->v] = ans[u.num];//继承这个点的最短路数
q.push((node){it->v , dis[it->v]});
}
else if(dis[it->v] == u.dis + it->val){
(ans[it->v] += ans[u.num]) %= mod ;// 相等就表示我们已经找到一条最短路边 +=
}
}
}
}
负环
开个cnt在vis里 计入入栈次数 >= N 就是负环
int SPFA(){
mem(dis,127);
nodeq q;
q.push(1);
dis[1] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
if(cnt[u] >= n) return 1;
vis[u] = 0;
for(int i = head[u] ; i ;i = edge[i].u){
int v = edge[i].v;
if(dis[v] > dis[u] + edge[i].val){
dis[v] = dis[u] + edge[i].val;
if(!vis[v]){
vis[v] = 1;
++cnt[v];//在这里++
if(cnt[v] >= n ) return 1;
q.push(v);
}
}
}
}
return 0;
}
严格次短路
更新 dis1[v] >= dis[u]+val;// 记住大于等于 更新最短路
不然就更新 dis2[v] > dis[u] + val;//如果小于就 用次短路更新
最后再判断 dis2[v] > dis2[u] + val;对次短路更新最短
更新前令div2[v]=dis[v]；这样就能保证没有曾经的最优解传递给了div2
void Dijkstra(){
priority_queue<node> q;
mem(dis,127);
q.push(node(1,0));
dis[1][0] = 0;
while(!q.empty()){
node u = q.top();
q.pop();
if(u.dis > dis[u.num][0]) continue;
for(int i = head[u.num] ; i; i = edge[i].u){
int v = edge[i].v;
if(dis[v][0] >= u.dis + edge[i].val){
dis[v][0] = u.dis + edge[i].val;
q.push(node(v,dis[v][0]));
}
else if(dis[v][1] > u.dis + edge[i].val){
dis[v][1] = u.dis + edge[i].val;
q.push(node(v,dis[v][0]));
}
if(dis[v][1] > dis[u.num][1] + edge[i].val)
dis[v][1] = dis[u.num][1] + edge[i].val;
}
}
}不严格K短路
int n,m,head[maxn],ans[maxn];
struct e
{
int u,v,val;
}edge[maxn],edgex[maxn];
struct node
{
int num,dis;
node(int x,int y) : num(x),dis(y) {}
bool operator < (const node &ano) const{
return dis == ano.dis ? num > ano.num : dis > ano.dis;
}
};
int tot;
void add(int u,int v,int val){//Dijkstra反向连边
edge[++tot].v = u;
edge[tot].u = head[v];
edge[tot].val = val;
head[v] = tot;
}
int headx[maxn],totx,dis[maxn];
void addx(int u,int v,int val){
edgex[++totx].u = headx[u];
edgex[totx].v = v;
edgex[totx].val = val;
headx[u] = totx;
}
void Dijkstra(){
priority_queue<node> q;
q.push(node(n,0));
mem(dis,127);
dis[n] = 0;
while(!q.empty()){
node u = q.top();
q.pop();
if(u.dis != dis[u.num]) continue;
for(int i = head[u.num] ; i ; i = edge[i].u){
int v = edge[i].v;
if(dis[v] > u.dis + edge[i].val){
dis[v] = u.dis + edge[i].val;
q.push(node(v , dis[v]));
}
}
}
}
struct nodeA
{
int u,val;
nodeA(int uu ,int vall) : u(uu) , val(vall) {}
bool operator < (const nodeA &ano) const{
return val + dis[u] > dis[ano.u] + ano.val;//注意重载反向是反的
}
};
int cnt[maxn];
int Ax(int k){
priority_queue<nodeA> Q;
Q.push(nodeA(1,0));//从起点开始 为val = 0
while(!Q.empty()){
nodeA u = Q.top();
Q.pop();
cnt[u.u]++;
if(cnt[u.u] == k && u.u == n) return u.val;
if(cnt[u.u] > k) continue;
for(int i = head[u.u] ; i ; i = edge[i].u){
Q.push(nodeA(edge[i].v , edge[i].val + u.val));
}
}
return -1;
}
int main(int argc, char const *argv[])
{
n = read() , m = read();
fors(i,1,m){
int u = read() , v = read(), w = read();
add(u,v,w);
add(v,u,w);
addx(u,v,w);
addx(v,u,w);
}
Dijkstra();
cout<<Ax(k)<<endl;
return 0;
}
严格k短路
//使用Maps
struct Maps
{
struct line
{
int u,v,val;
}edgeh[maxn];
int hs[maxn],tot;
Maps(){mem(hs,0);tot=0;}
void insert(int key,int val){
edgeh[++tot].u = hs[key % maxn];
edgeh[tot].v = key;
edgeh[tot].val = val;
hs[key % maxn] = tot;
}
int find(int x){
for(int i = hs[x % maxn]; i ;i = edgeh[i].u){
if(x == edgeh[i].v) return edgeh[i].val;
}
return -1;
}
}maps;
int Astar(int st, int ed, int k){
Q.push( (Node){ st, 0} );
while( !Q.empty() ){
Node u= Q.top(); Q.pop();
if(u.x == ed) {
if(maps.find(u.val) == -1){
maps.insert(u.val , 1);
++kkk;
}
}
if(k == kkk && u.x == ed) return u.val;
if(kkk > k) continue;
for(int i=head_hx[u.x];i;i=edge_hx[i].u){
int v= edge_hx[i].v, w= edge_hx[i].val;
Q.push((Node){v, u.val + w});
}
}
return -1;
}k短路 路径字典序
后我们考虑bfs A* 的时候每次几率下整条路径，暴力转移，应为路径长度是由小逐渐变大的（用了小根堆）
int n,m;
struct e{
int u,v,val;
}edge[maxn],edge_hx[maxn];
int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
edge[++tot].v = u;//反向建边
edge[tot].u = head[v];
head[v] = tot;
edge[tot].val = val;
edge_hx[++toth].v = v;
edge_hx[toth].u = head_hx[u];
head_hx[u] = toth;
edge_hx[toth].val = val;
}
int dis[maxn];
struct node{
int num,dis;
bool operator < (const node &ano) const{
return dis==ano.dis ? num > ano.num : dis > ano.dis;
}
};
void Dijkstra(int ed){
priority_queue<node> q;
memset(dis,127,sizeof dis);
dis[ed]=0;
q.push((node){ed,0});
while(!q.empty()){
node u=q.top();q.pop();
if(u.dis != dis[u.num]) continue;
for(int i=head[u.num];i;i=edge[i].u){
int v=edge[i].v;
if(dis[v] > u.dis+edge[i].val) {
dis[v]=u.dis+edge[i].val,q.push((node){v,dis[v]});
}
}
}
}
struct nodea{
int u,val,v[60];
vector<int> path;
bool operator < (const nodea &rhs) const{
return val + dis[u] > rhs.val + dis[rhs.u] || (val + dis[u] == rhs.val + dis[rhs.u] && path > rhs.path);
}
}now,cur;
int cnt=0;
priority_queue<nodea> q;
void Ax(int s , int t , int k){
now.u=s,now.v[s]=1,//注意初始化 vis[s] = 1；
//并且加入到路径
now.path.push_back(s);
q.push(now);
while(!q.empty()){
now=q.top();
q.pop();
if(now.u==t){
if(++cnt == k){//当到这个点已经是 k 次的时候结束
int num=now.path.size();
for(int i=0;i<num;++i)
printf("%d",now.path[i]),
printf("%c",i < num-1?'-':'\n');
return ;
}
}
else{
int u=now.u;
for(int i=head_hx[u];i;i=edge_hx[i].u){
int v=edge_hx[i].v;
if(now.v[v]) continue;//在nodeA里套个vis，判断是否入栈
cur=now;
cur.val +=edge_hx[i].val;
cur.v[v] = 1,//类似SPFA
cur.u=v;
cur.path.push_back(v);//每次记录入边，因为已经小根堆排序所以已经是字典序了
q.push(cur);
}
}
}
puts("No");
}
int k,s,t;
int main(int argc, char const *argv[])
{
n = read() , m = read() , k = read() , s = read() , t = read();
fors(i,1,m){
int u = read() , v = read() ,w = read();
add(u,v,w);
}
Dijkstra(t);
Ax(s,t,k);
return 0;
}图论转化
给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。
乘法问题 - 》 log !!！
使用po[][2] 第一个空间存路径，第二个存权值,注意每次递归到1
for(int i=head[u.num];i;i=edge[i].u){
int v=edge[i].v;
if(dis[v] > u.dis+edge[i].val) {
dis[v]=u.dis+edge[i].val,q.push((node){v,dis[v]});
po[v][0] = u.num;//记录当前节点
po[v][1] = edge[i].val;//记录边权
}
}
Dijkstra(1);
int ans=1,pos=n,mod = 9987;
while(pos!=1){//注意到1结束，不用mem
ans*=po[pos][1];//路径的权值
ans%=mod;
pos=po[pos][0];//路径
}
字符串DP ： 子串
有两个仅包含小写英文字母的字符串 $A$ 和$ B$。
现在要从字符串 $A$ 中取出$ k$ 个互不重叠的非空子串，然后把这 $k $个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？
注意：子串取出的位置不同也认为是不同的方案。
首先 这道题看上去是一道字符串匹配题
可是不是
我们想到了 $DP$
考虑当前匹配成功与匹配不成功
定义状态dp[i][j][k][0/1]表示字符串$A$的前$i$个字符和字符串$B$的前$j$个字符用了$k$个子串，第四维为$1$表示$A$字符串的第$i$个字符必须被选出，为$0$表示$A$字符串的第$i$个字符不能被选出。
那么很容易得出转移：
1、对于任意一个0<=i<=n0<=i<=n，$f[i][0][0][0]=1$
2、$f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]$
3、$f[i][j][k][1]=f[i-1][j-1][k][1]+f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]$
最后结果即为$f[n][m][K][0]+f[n][m][K][1]$。
const int maxn = 1e7+7;
int n , m ,kk, cnt;
#define int LL//请认真判断 LL 是否需要 ， 空间 + 精度 ！！！$
int dp[2][205][205][2];
char a[maxn] , b[maxn];
const int mod = 1000000007 ;
#undef int
int main(int argc, char const *argv[])
{
//freopen("1.in","r",stdin);
n = read() , m = read() , kk = read();
scanf("%s",a+1);
scanf("%s",b+1);
dp[0][0][0][0] = 1;
fors(i,1,n){
int len1 = min(i,m);
dp[cnt][0][0][0] = 1;
fors(j,1,len1){
int len2 = min(j , kk);
fors(k , 1 ,len2){//注意边界
dp[cnt ^ 1][j][k][0] = dp[cnt ^ 1][j][k][1] = 0;
(dp[cnt ^ 1][j][k][0] = dp[cnt][j][k][1] + dp[cnt][j][k][0]) %= mod;
if(a[i] == b[j])
(dp[cnt ^ 1][j][k][1] = dp[cnt][j-1][k][1] + dp[cnt][j-1][k-1][0] + dp[cnt][j-1][k-1][1]) %= mod;
}
}
cnt ^= 1;//每次滚动
}
writen((dp[cnt][m][kk][1] + dp[cnt][m][kk][0]) % mod);
return 0;
}
使用数据结构普通的维护
$1~. ~l~ r~ x : $把区间$[l,r]$中所有x的倍数$/x$$2~ .l~ r~ :$ 查询区间$[l,r]$的和
操作$1$每次都要找出操作区间中$x$的倍数并除$x$ 对此如果直接爆力操作肯定挂，所以我们使用 $vector$ 初始化 每个数的因子，以此来方便删除
将元素的所有出现位置都按升序存在一个数组中，之后回答每次询问$[l,r]$只需要在每个元素对应的数组中二分出那些恰好在$l$和$r$内的元素，从而得到该元素$A[i]$在区间$[l,r]$内的出现次数，即$num=upper_bound(A[i],r)-lower_ b ound(A[i],l)$
数组$T[i]$存的是所有是$i$的倍数的数在原数组中的下标
同时我们保证每一个$T$数组内部都是有序（升序）的
我们直接在x对应的$T$数组内部进行二分查找，找到那些恰好处于$[l,r]$的元素，直接将他们除掉$x$(即$A[*it]/=x)$，同时对于这些除掉$x$的新数，如果发现它不再是$x$的倍数(也可以理解成$x$不再是新$A[*it]$的因子)就将新$A[*it]$从$x$所对应的T数组中删去
但是要注意$vector.erase()$函数删掉一个数之后原其后剩下的数回会整体向$0$方向平移一个单位(下标会变）所以正向删数就会出问题，再回来考虑这道题，我们已经保证了每一个$T$数组内部都是有序（升序）的
因此我们不能正向删数，但是反向删数就没问题
const int maxn = 5e5+7 ;
int n,m,a[maxn];
vector<int> T[maxn];
vector<int> :: iterator pos1,pos2,it;
vector< vector<int> :: iterator > dela;
namespace ZKW
{
ll tree[maxn],N;
void init(){
for(N = 1; N <= n; N <<= 1)
;
}
void modify(int x,int k){
for(x += N; x ; x>>=1)
tree[x] += k;
}
ll query(int s,int r){
ll ans=0;
for(s += N-1 , r += N + 1 ; s ^ r ^ 1 ; s >>= 1 , r >>= 1){
if(~ s & 1) ans += tree[s ^ 1];
if(r & 1) ans += tree[r ^ 1];
}
return ans;
}
};
namespace Drive{
ll belong[maxn],block,val[maxn],tag[maxn];
void init(){
block = sqrt(n);
fors(i,1,n){
val[i]=a[i];
belong[i] = (i-1)/block+1;
tag[belong[i]] += val[i];
}
}
void modify(int x,int k){
val[x] += k;
tag[belong[x]] += k;
}
ll query(int x,int y){
ll ans=0;
int len = min(y , block * belong[x]);
fors(i,x,len){
ans += val[i];
}
if(belong[x] != belong[y]){
fors(i,(belong[y]-1) * block+1,y)
ans+=val[i];
}
fors(i,belong[x] + 1, belong[y]-1)
ans+=tag[i];
return ans;
}
};
namespace BIT{
ll tree[maxn];
void modify(int x,int k){
while(x <= n){
tree[x] += k;
x += x & -x;
}
}
ll sum(int x){
ll ans = 0 ;
while(x){
ans += tree[x];
x -= x & -x;
}
return ans;
}
ll query(int l,int r){
return sum(r) - sum(l-1);
}
};
namespace SEG{
struct node
{
int ls,rs;
ll val;
}tree[maxn];
void build(int cur,int l,int r){
tree[cur].ls = l,tree[cur].rs =r;
if(l == r) {
tree[cur].val=a[l];
return ;
}
int mid = (l+r) >> 1;
build(cur<<1,l,mid);
build(cur<<1|1,mid+1,r);
tree[cur].val = tree[cur<<1].val + tree[cur<<1|1].val;
}
void modify(int cur,int now,int k){
if(tree[cur].ls == tree[cur].rs){
tree[cur].val+=k;
return ;
}
int mid=(tree[cur].ls + tree[cur].rs) >> 1;
if(now <= mid)
modify(cur<<1,now,k);
else
modify(cur<<1|1,now,k);
tree[cur].val = tree[cur<<1].val + tree[cur<<1|1].val;
}
ll query(int cur,int l,int r){
ll ans=0;
if(tree[cur].ls >= l && tree[cur].rs<=r){
return tree[cur].val;
}
int mid=(tree[cur].ls + tree[cur].rs)>>1;
if(l <= mid)
ans+=query(cur<<1,l,r);
if(r > mid)
ans+=query(cur<<1|1,l,r);
return ans;
}
}
using namespace SEG;
void work(int pos,int x){
int len = sqrt(x);
fors(i,1,len){
if(x % i) continue;
T[i].push_back(pos);
if(x / i != i)
T[x / i].push_back(pos);
}
}
void clean(){
vector<vector<int> :: iterator > v;
swap(v , dela);
}
void chang(int l,int r,int k){
if(k == 1 || T[k].empty()) return ;
pos1 = lower_bound(T[k].begin() , T[k].end() ,l);
pos2 = upper_bound(T[k].begin() , T[k].end() ,r);
clean();
for(it = pos1 ; it != pos2 ; ++it){
if(a[*it] % k) continue;
modify(1, *it , -(a[*it] - a[*it]/k)) , a[*it] /= k;
if(a[*it] % k)
dela.push_back(it);
}
if(dela.empty())
return ;
for(int i = dela.size()-1;i>=0; --i)
T[k].erase(dela[i]);
}
int main(int argc, char const *argv[])
{
n=read(),m=read();
fors(i,1,n){
a[i]=read();
work(i,a[i]);
}
build(1,1,n);//SEG建树 ，如果使用 其他数据结构 需要修改
while(m--){
int op=read(),a=read(),b=read();
if(op == 1){
int k=read();
chang(a,b,k);
}
else if(op == 2){
write(query(1,a,b));
puts(" ");
}
}
return 0;
}
单调栈
最后一次出栈的栈顶元素就是当前入栈元素可以向左拓展到的最大距离。
int main()
{
int i,n,top; //top指向栈顶
stack<int> st; //栈用于保存矩形的编号，即位置
LL tmp,ans,a[100010]; //tmp为临时变量，记录面积的值，ans为结果，记录最大面积值
while(~scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
ans=0;
a[n]=-1; //最后一个元素设为最小值，以最后清空栈
fors(i,0,n){
if(st.empty() || a[i]>=a[st.top()]){ //如果栈为空或入栈元素大于等于栈顶元素 ，则入栈
st.push(i);
}
else{
while(!st.empty()&&a[i]<a[st.top()]){ //如果栈非空且入栈元素小于栈顶元素，则将栈顶元素出栈
top=st.top();
st.pop();
tmp=(i-top)*a[top]; //在出栈过程中计算面积值
if(tmp>ans) ans=tmp; //更新面积最大值
}
st.push(top); //只将可以延伸到的最左端的位置入栈
a[top]=a[i]; //并修改该位置的值
}
}
printf("%lld\n",ans);
}
return 0;
}
int a[8000008];
ll ans;
stack <int> sta;
int main(){
int n = read();
fors(i,1,n) a[i] =read();
sta.push(a[1]);
fors(i,1,n){
while(!sta.empty()){
if(a[i] >= sta.top()) sta.pop();
else{
//将比栈顶元素的值小的进栈，并统计
sta.push(a[i]),ans+=sta.size() - 1;
break;
}
}
if(sta.empty()) sta.push(a[i]);
}
cout<<ans<<endl;
return 0;
}求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点。
int main()
{
int i,n,pos1,pos2; //pos1和pos2记录区间的开始和结束位置
//tmp为临时变量，记录区间内的和；top指向栈顶元素；ans为结果；sum为前缀和
LL tmp,top,ans,a[100010],sum[100010];
stack<int> st; //单调栈，记录元素位置
while(~scanf("%d",&n)){
while(!st.empty()) st.pop(); //清空栈
sum[0]=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i]; //计算前缀和
}
a[n+1]=-1; //将最后一个设为最小值，以最后让栈内元素全部出栈
ans=0;
for(i=1;i<=n+1;i++){
if(st.empty()||a[i]>=a[st.top()]){
//如果栈为空或入栈元素大于等于栈顶元素，则入栈
st.push(i);
}
else {
while(!st.empty()&&a[i]<a[st.top()]){
//如果栈非空并且入栈元素小于栈顶元素，则将栈顶元素出栈
top=st.top();
st.pop();
tmp = sum[i-1]-sum[top-1]; //计算区间内元素和
tmp *= a[top]; //计算结果
if(tmp>=ans)
{ //更新最大值并记录位置
ans=tmp;
pos1=top;
pos2=i;
}
}
st.push(top); //将最后一次出栈的栈顶元素入栈
a[top]=a[i]; //将其向左向右延伸并更新对应的值
}
}
printf("%lld\n",ans);
printf("%d %d\n",pos1,pos2-1);
}
return 0;
}单调队列
int askmax(int l,int r){//查询区间最大值
nows = l;
qmax.clear();//每次都要清空
while(nows <= r){
while(!qmax.empty() && a[qmax.back()] <= a[nows])
qmax.pop_back();
qmax.push_back(nows);
++nows;
}
while(!qmax.empty() && qmax.front() < l) qmax.pop_front();
return a[qmax.front()];
}
struct deques//由于不用插入元素到队首，所以可以直接手写。。
{
int a[maxn],l,r;
deques(){ mem(a,0);l=0,r=0;}
void push_back(int x){
a[++r] = x;
}
void pop_back(){
--r;
}
void pop_front(){
++l;
}
int front(){
return a[l];
}
int back(){
return a[r];
}
bool empty(){
return l > r;
}
}qmax,qmin;
int nows;
int askmax(int l,int r){
while(nows != r){//本题采用
++nows;//单调队列存的是 下标注意！！
while(!qmax.empty() && a[qmax.back()] <= a[nows])
qmax.pop_back();// 当CZ 比你强的就把你出队 qwq（梗）
qmax.push_back(nows);//然后让他进队
}//如果还比你小，你再出队
while(!qmax.empty() && qmax.front() < l) qmax.pop_front();
return a[qmax.front()];
}
int askmin(int l,int r){
while(nows != r){
++nows;
while(!qmin.empty() && a[qmin.back()] >= a[nows])
qmin.pop_back();//当队列不为空切队尾元素不符合要求 弹出队尾
qmin.push_back(nows);//将now入到队尾
}//当队头元素小于（不符合区间最值） 弹出
while(!qmin.empty() && qmin.front() < l) qmin.pop_front();
return a[qmin.front()];
}
#undef int
int main(int argc, char const *argv[])
{
n = read() , m = read();
fors(i,1,n){
a[i] = read();
}
m--;
nows = 0;
for(int i = 1 ; i + m <= n ; ++i){
writes(askmin(i,i + m));
}
puts(" ");
nows = 0;
for(int i = 1 ; i + m <= n ; ++i){
writes(askmax(i , i + m));
}
puts(" ");
return 0;
}
逆序队数量求法
- Ans1: (数据量小 , 你不会写归并，)
考虑根据值来建树状数组 , 初始树状数组为全 $0$。现在按照序列从左到右将数据的值对应的位置的数加一，代表又有一个数出现。因此，在循环到第 $i$ 项时，前 $i-1$ 项已经加入到树状数组内了 , 树状数组内比 $a_i$大的都会与$a_i$构成逆序对，因为它们一定出现的更早，所以产生的逆序对数量为$i-query(a_i)$
int n , m ;
int ans ;
int T[maxn];
struct node
{
int val,num;
bool operator < (const node &ano) const{
return val == ano.val ? num < ano.num : val < ano.val;
}
}a[maxn];
int b[maxn];
void add(int x,int k){
while(x <= n){
T[x] += k;
x += x & -x;
}
}
int query(int x){
int ans = 0;
while(x){
ans += T[x];
x -= x & -x;
}
return ans;
}
#undef int
int main(){
n = read();
fors(i,1,n){
a[i].val = read();
a[i].num = i;
}
sort(a+1,a+1+n);
fors(i,1,n){
b[a[i].num] = i;
}
fors(i,1,n){
add(b[i] , 1);
ans += i - query(b[i]);
}
writen(ans);
return 0;
}- 归并排序解法
首先你需要知道什么是归并排序。然后，我们可以这样想：（时空都很好）
如果我们想要将一个序列排成从小到大有序的，那么每次划分后合并时左右子区间都是从小到大排好序的，我们只需要统计右边区间每一个数分别会与左边区间产生多少逆序对即可。
不懂的话看栗子：
//在某个时候，左区间： 5 6 7 下标为i
// 右区间： 1 2 9 下标为j
//
//这个时候我们进行合并：
//step 1：由于 5>1，所以产生了逆序对，这里，我们发现，左区间所有还没有被合并的数都比 1 大，所以1与左区间所有元素共产生了 3 个逆序对(即tot_numleft-i+1对)，统计答案并合并 1
//step 2：由于 5>2，由上产生了3对逆序对，统计答案并合并 2
//step 3：由于 5<9, 没有逆序对产生，右区间下标 j++
//step 4：由于 6<9, 没有逆序对产生，右区间下标 j++
//step 5：由于 7<9, 没有逆序对产生，右区间下标 j++
//step 6：由于右区间已经结束，正常执行合并左区间剩余，结束
//PS： tot_numleft=3，即左区间总元素个数
int val[maxn],t[maxn];
void msort(int l , int r){
if(l == r) return ;
int a = l , mid = (l+r) >> 1, b = mid + 1 , c = 1;
msort(a , mid) , msort(b , r);//二分归并
//找到最小区间开始计算
while(a <= mid && b <= r){
if(val[a] > val[b]) t[c++] = val[b++] , ans += mid - a + 1;
//不是逆序就直接赋值，不然就赋值大的，更新ans
else t[c++] = val[a++];
}
while(a <= mid) t[c++] = val[a++];//全部复制（在 l,r范围内）
while(b <= r) t[c++] = val[b++];//记住都是变量 ++ （在数组里）
fors(i,1,r-l+1) val[l+i-1] = t[i];
}
#undef int
int main(){
n = read();
fors(i,1,n){
val[i] = read();
}
msort(1,n);
writen(ans);
return 0;
}
树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度需要处理的问题：
- 将树从x到y结点最短路径上所有节点的值都加上z
- 求树从x到y结点最短路径上所有节点的值之和
- 将以x为根节点的子树内所有节点值都加上z
- 求以x为根节点的子树内所有节点值之和
1. dfs1()
这个dfs要处理几件事情：
- 标记每个点的深度$depth[]$
- 标记每个点的父亲$fa[]$
- 标记每个非叶子节点的子树大小(含它自己)
- 标记每个非叶子节点的重儿子编号$son[]$
void dfs1(int x,int f,int dep){
depth[x] = dep;
fa[x] = f;
siz[x] = 1;
int maxson = -1;//记录重儿子的儿子数
for(int i = head[x] ; i; i=edge[i].u){
int v = edge[i].v;
if(v == f) continue;//若为父亲则continue
dfs1(v,x,dep+1);//dfs其儿子
siz[x] += siz[v];//把它的儿子数加到它身上
if(siz[v] > maxson) son[x] = v,maxson = siz[v];
//标记每个非叶子节点的重儿子编号
}
}2. dfs2()
- 标记每个点的新编号
- 赋值每个点的初始值到新编号上
- 处理每个点所在链的顶端
- 处理每条链
- 顺序：先处理重儿子再处理轻儿子，理由后面说
void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点
id[x] = ++cnt;
dis[cnt] = w[x];//把每个点的初始值赋到新编号上来
top[x] = topf;//这个点所在链的顶端
if(!son[x]) return ;
dfs2(son[x] , topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
for(int i=head[x];i;i=edge[i].u){
int v = edge[i].v;
if(v == fa[x] || v == son[x]) continue;
dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
}
}
}处理问题
$Attention$重要的来了！！！
前面说到$dfs2$的顺序是先处理重儿子再处理轻儿子
我们来模拟一下：
因为顺序是先重再轻，所以每一条重链的新编号是连续的
因为是$dfs$，所以每一个子树的新编号也是连续的
现在回顾一下我们要处理的问题
- 处理任意两点间路径上的点权和
- 处理一点及其子树的点权和
- 修改任意两点间路径上的点权
- 修改一点及其子树的点权
1、当我们要处理任意两点间路径时：
设所在链顶端的深度更深的那个点为$x$点
$ans$加上$x$点到$x$所在链顶端 这一段区间的点权和
把$x$跳到$x$所在链顶端的那个点的上面一个点
不停执行这两个步骤，直到两个点处于一条链上，这时再加上此时两个点的区间和即可
这时我们注意到，我们所要处理的所有区间均为连续编号(新编号)，于是想到分块，用分块处理连续编号区间和
int qrange(int x,int y){
int ans = 0;
while(top[x] != top[y]){//当两个点不在同一条链上
if(depth[top[x]] < depth[top[y]]) swap(x,y);//把x点改为所在链顶端的深度更深的那个点
res = 0;
query(id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
ans += res;
ans %= mod;//按题意取模
x = fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
}
//直到两个点处于一条链上
if(depth[x] > depth[y]) swap(x,y);//把x点深度更深的那个点
res = 0;
query(id[x],id[y]);//这时再加上此时两个点的区间和即可
ans+=res;
return ans % mod;
}2、处理一点及其子树的点权和：
想到记录了每个非叶子节点的子树大小(含它自己)，并且每个子树的新编号都是连续的
于是直接分块区间查询即可
时间复杂度为$O(sqrt(n))$
int n,m;
const int inf = (unsigned int)(1<<31) - 1;
struct node
{
int v,u;
}edge[maxn];
int head[maxn],w[maxn],dis[maxn],tot;
void add(int u,int v){
edge[++tot].v= v;
edge[tot].u = head[u];
head[u] = tot;
}
int res,mod;
namespace SEG{
int a[maxn],laz[maxn];
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
#define ls rt<<1
#define rs rt<<1|1
void push_down(int rt,int lens){
laz[ls] += laz[rt];
laz[rs] += laz[rt];
a[ls] += laz[rt] * (lens - (lens>>1));
a[rs] += laz[rt] * (lens>>1);
a[ls] %= mod;
a[rs] %= mod;
laz[rt] = 0;
}
void build(int rt = 1,int l = 1 ,int r = n){
if(l == r){
a[rt] = dis[l];
if(a[rt] > mod) a[rt]%= mod;
return ;
}
build(lson);
build(rson);
a[rt] = (a[ls] + a[rs]) % mod;
}
void update(int L,int R ,int k,int rt=1,int l=1,int r=n){
if(L <= l && r <= R){
laz[rt] += k;
a[rt]+= k*len;
}
else {
if(laz[rt])
push_down(rt,len);
if(L <= mid)
update(L,R,k,lson);
if(R > mid)
update(L,R,k,rson);
a[rt] = (a[ls] + a[rs] ) % mod;
}
}
void query(int L ,int R ,int rt=1,int l=1,int r=n){
if(L <= l && r <= R){
res += a[rt];
res %= mod;
return ;
}
else {
if(laz[rt])
push_down(rt,len);
if(L <= mid)
query(L,R,lson);
if(R > mid)
query(L,R,rson);
}
}
};
namespace Divers{
int belong[maxn],block,tag[maxn],val[maxn],sum[maxn];
void build(){
block = sqrt(n);
fors(i,1,n){
val[i] = dis[i];
if(val[i] >= mod) val[i]%=mod;
belong[i] = (i-1)/block+1;
sum[belong[i]] += val[i];
if(sum[belong[i]] > mod) sum[belong[i]] %= mod;
}
}
void update(int x,int y,int k){
int lens = min(y,block * belong[x]);
k %= mod;
fors(i,x,lens){
val[i]+=k;
if(val[i] >= mod) val[i]%=mod;
sum[belong[x]] += k;
}
sum[belong[x]] %= mod;
if(belong[x] != belong[y]){
fors(i,(belong[y]-1)*block+1,y){
val[i]+=k;
if(val[i] >= mod) val[i]%=mod;
sum[belong[y]]+=k;
}
}
sum[belong[y]] %= mod;
fors(i,belong[x]+1,belong[y]-1)
tag[i]+=k,tag[i]%=mod;
}
int query(int x,int y){
int ans = 0 , lens = min(y , block*belong[x]);
fors(i,x,lens){
ans += val[i] + tag[belong[x]];
}
ans %= mod;
if(belong[x]!=belong[y]){
fors(i,(belong[y]-1)*block+1,y)
ans += val[i] + tag[belong[y]];
ans %= mod;
}
fors(i,belong[x]+1,belong[y]-1){
ans += sum[i] + block*tag[i];
ans %= mod;
}
res = ans;
return res;
}
}
using namespace Divers;
namespace LCT{
int son[maxn],id[maxn],fa[maxn],cnt,depth[maxn],top[maxn],siz[maxn];
int qrange(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(depth[top[x]] < depth[top[y]]) swap(x,y);
res = 0;
query(id[top[x]],id[x]);
ans += res;
ans %= mod;
x = fa[top[x]];
}
if(depth[x] > depth[y]) swap(x,y);
res = 0;
query(id[x],id[y]);
ans+=res;
return ans % mod;
}
void uprange(int x,int y,int k){
k%=mod;
while(top[x] != top[y]){
if(depth[ top[x] ] < depth[ top[y] ]) swap(x,y);
update(id[top[x]] , id[x] , k);
x = fa[top[x]];
}
if(depth[x] > depth[y]) swap(x,y);
update(id[x],id[y], k);
}
int qson(int x){
res = 0;
query(id[x],id[x] + siz[x] -1);
return res;
}
void upson(int x,int k){
update(id[x] , id[x] + siz[x] - 1, k);
}
void dfs1(int x,int f,int dep){
depth[x] = dep;
fa[x] = f;
siz[x] = 1;
int maxson = -1;
for(int i = head[x] ; i; i=edge[i].u){
int v = edge[i].v;
if(v == f) continue;
dfs1(v,x,dep+1);
siz[x] += siz[v];
if(siz[v] > maxson) son[x] = v,maxson = siz[v];
}
}
void dfs2(int x,int topf){
id[x] = ++cnt;
dis[cnt] = w[x];
top[x] = topf;
if(!son[x]) return ;
dfs2(son[x] , topf);
for(int i=head[x];i;i=edge[i].u){
int v = edge[i].v;
if(v == fa[x] || v == son[x]) continue;
dfs2(v,v);
}
}
}
using namespace LCT;
int root;
int main(int argc, char const *argv[])
{
n=read(),m=read(),root=read(),mod=read();
fors(i,1,n){
w[i]=read();
}
fors(i,1,n-1){
int a=read(),b=read();
add(a,b);
add(b,a);
}
dfs1(root,0,1);
dfs2(root,root);
build();
while(m--){
int k,x,y,z;
k = read();
if(k == 1){
x=read(),y=read(),z=read();
uprange(x,y,z);
}
else if(k == 2){
x=read(),y=read();
write(qrange(x,y));
puts(" ");
}
else if(k == 3){
x = read() ,y=read();
upson(x,y);
}
else {
x=read();
write(qson(x));
puts(" ");
}
}
return 0;
}跳转 Chtholy Tree + HPD
#define fors(i,a,b) for(int i=(a);i=(b);--i)
#define mem(x,val) (memset((x),(val),sizeof (x)))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define swap(x,y,tmp) ((tmp)=(x),(x)=(y),(y)=(tmp))
//注意使用的时候在前面多定义一个temp
#define forvit(i) for(vector :: iterator it=(i).begin();it!=(i).end();++it)
#define v *it
//注意定义之后，如果定义了一个v的变量会Error，因为已经被v替换成了*it
#define link(x , y) x##y //神奇的拼接，可以将两个int拼在一起
#define Tostring(x) #x
//例如 x=24,y=16 ;int a = link(x,y); a=2416
//但注意不要超出int 的范围;
//或者你可以使用long long 这样就有18位数字了 ll-inf ~=9e18;
// Tostring 就相当于 给x加上一个""号 但是如果x是个变量的话，那就不行,
// a=12; cout<<Tostring(a)< a 直接输出了变量名，好像没什么用啊 2333 QAQ 如果有dalao发现了这玩意的技巧请告诉我 QwQ
#define pr(...) printf(__VA_ARGS__);
//__VA_ARGS__相当于一个可变参数宏(无关重点
// 主要是 可以这么用 pr("QVQ %d\n" , 1231);就当作printf啦
#define I_O(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout);
// 用于读入文件 ， 使用时注意"的位置 ， I_O（文件名） 不用加后缀 2333
#define Debug(...) fprintf(stderr,__VA_ARGS__)
// Debug 就是用来调试的 fprintf 和 stderr -> cerr，具体和printf一个用法
// 可以在使用freopen的时候将 Debug 输出到屏幕
// 调试时用fprintf(stderr, "%d", clock())更方便
// Debug("Ans = %d Time: %d",Ans,clock());
ll mul(ll a,ll b,ll p){
a=a%p,b=b%p;
return ((a*b - (ll)(( (long double)a * b + 0.5 ) / p) * p )%p +p)%p;
}//防止精度爆炸的乘
字符串
KMP && hash 给定一个字符串 $A$ 和一个字符串 $B$，求 $B$ 在 $A$ 中的出现次数。
//下标从1开始，如果从0开始 就i-1
const int maxn = 1e6+7;
char s[maxn],kmp[maxn];
int nexts[maxn],n,lens,len;
int make_k(){
len=strlen(kmp+1);
int j=0,ans=0;
fors(i,2,len){//从第二位开始匹配，保持j+1
while(j && kmp[i]!=kmp[j+1]) j=nexts[j];
nexts[i] = kmp[i] == kmp[j+1] ? ++j : 0;
}
j=0;
lens=strlen(s+1);
fors(i,1,lens){
while(j && s[i] != kmp[j+1]) j=nexts[j];
j += s[i] == kmp[j+1] ;
if(j == len) ++ans;
}
return ans;
}
int main(int argc, char const *argv[])
{
scanf("%s%s",s+1,kmp+1);
writen(make_k());
return 0;
}
// hash
const ull hashs=23333333;
ull pows=1,sum[maxn];
int main(int argc, char const *argv[])
{
scanf("%s%s",s+1,kmp+1);
lens=strlen(s+1),lenb=strlen(kmp+1);
fors(i,1,lenb) pows=pows*hashs;
fors(i,1,lens){
sum[i]=sum[i-1] * hashs + (ull) (s[i] - 'a' + 1);
}
ull now = 0;
for(int i=1;i <= lenb; ++i){
now = now * hashs + (ull) (kmp[i] - 'a' + 1);
}
int ans=0;
for(int i=0; i + lenb <= lens;++i){
if(now == sum[i + lenb] - sum[i] * pows)
++ans;
}
writen(ans);
return 0;
}
Manacher 求S中最长回文串的长度.
Manacher利用回文对称的性质，来简化求以一个字符为对称轴的最大的回文长度
int n,m,hw[maxn];
char a[maxn],s[maxn<<1];
void manacher(){
int maxr = 0 , mid = 0 ;//maxr，表示已经触及到的最右边的字符
fors(i,0,n){
if(i < maxr)//i关于mid的对称点为j - > mid*2-i，
hw[i] = min(hw[mid * 2 - i] , hw[mid] + mid - i);
else //当i在maxr右边时，我们无法得知关于hw[i]的信息，只好从1开始遍历，然后更新maxr和mid
hw[i] = 1;
while(s[i + hw[i]] == s[i - hw[i]])//扩展回文长度
++hw[i];
if(hw[i] + i > maxr){
maxr = hw[i] + i;
mid = i;
}
}
}
//回文串长度的奇偶性造成了对称轴的位置可能在某字符上，也可能在两个字符之间的空隙处，要对两种情况分别处理
void chage(){
s[0] = s[1] = '#';//加入'#'使得长度为偶数就解决了
fors(i,0,n){
s[i*2 + 2] = a[i];
s[i*2 + 3] = '#';
}
n = n + n + 2;
s[n] = 0;
}
int main()
{
scanf("%s",a);
n = strlen(a);
chage();
manacher();
int ans = 1;
fors(i,0,n){
ans = max(ans , hw[i]);
}
writen(ans-1);//回文要-1 qwq
return 0;
}
图论
并查集
int f[maxn],ans,n,m,tot,k[maxn];
const int mod=998244353;
int find(int x){
return f[x] == x ? x : (f[x] = find(f[x]));
}
int main(int argc, char const *argv[])
{
n=read(),m=read();
fors(i,1,n)
f[i]=i;
fors(i,1,m){
int op=read(),u=read(),v=read();
if(!op){
int a=find(u),b=find(v);
if(a!=b) {
f[b]=a;
}
}
else{
ans=ans<<1|(find(u) == find(v));
ans%=mod;
}
}
writen(ans);
return 0;
}最短路
首先简单的
// floyd 多源最短路 计算类似矩阵乘法
int edge[2505][2505];
void floyd(){
fors(k,1,n)
fors(i,1,n)
fors(j,1,n)
edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
}
int main(int argc, char const *argv[])
{
n=read(),m=read(),s=read(),t=read();
mem(edge,63);
edge[p][p]=0;
fors(i,1,m){
int a=read(),b=read(),c=read();
edge[a][b]=edge[b][a]=min(edge[a][b],c);
}
floyd();
writen(edge[s][t]);
return 0;
}
//SPFA 加优化更慢！！！
struct node
{
int u,v,val;
}edge[maxn];
void add(int u,int v,int w){
edge[++tot].v=v,edge[tot].u=head[u],head[u]=tot,edge[tot].val=w;
}//链式前向星
void spfa(){
mem(dis,127);
vis[s]=1;
q.push(s);
dis[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int v,i=head[u];i;i=edge[i].u){
v=edge[i].v;
if(dis[v] > dis[u] + edge[i].val){
dis[v] = dis[u] + edge[i].val;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
优秀的Dijkstra算法
然而我写不来Fib 优化。。。点多的用zkw，点少的stl
// 暴力
void dijkstra(){
mem(dis,63);
int u=s;
dis[u]=0;
while(!vis[u]){
vis[u] = 1;
for(int v,i=head[u];i;i=edge[i].u){
v=edge[i].v;
if(!vis[v] && dis[v] > dis[u] + edge[i].val){
dis[v] = dis[u] + edge[i].val;
}
}
int mins=1<<30;
fors(i,1,n){
if(!vis[i] && mins > dis[i]){
mins = dis[i];
u = i;
}
}
}
}
// 堆优化
struct node{
int num,dis;
friend bool operator < (node a,node b){
if(a.dis==b.dis) return a.num>b.num;
return a.dis>b.dis;
}
};
inline void add(int u,int v,int w){
e[++tot]=(cp){head[u],v,w};
head[u]=tot;
}
priority_queue<node> q;
void Dijkstra(){
memset(dis,63,sizeof dis);
dis[s]=0;
q.push((node){s,0});
while(!q.empty()){
node u=q.top();q.pop();
if(u.dis!=dis[u.num])
continue;
for(int i=head[u.num];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>u.dis+e[i].val)
dis[v]=u.dis+e[i].val,q.push((node){v,dis[v]});
}
}
}
//ZKW 线段树
int n,m,s,t,N,tree[maxn<<1],dis[maxn],vis[maxn],tot,head[maxn];
struct node
{
int u,v,val;
}edge[maxn<<1];
void build(){
for(N = 1 ; N < n;N <<= 1)
;
--N;
fors(i,1,n)
tree[i+N] = i;
for(int i=N; i ; --i)
tree[i] = dis[ tree[i<<1] ] < dis[ tree[i<<1|1] ] ? tree[i<<1] : tree[i<<1|1];
}
void update(int x){
for(int i=(x + N) >> 1 ; i ; i>>=1)
tree[i] = dis[ tree[i<<1] ] < dis[ tree[i<<1|1] ] ? tree[i<<1] : tree[i<<1|1];
}
void add(int u,int v,int w){
edge[++tot].v=v,edge[tot].u=head[u],head[u]=tot;edge[tot].val=w;
}
void Dijkstra(){
mem(dis,127);
dis[s]=0;//先赋值 再建树
build();
mem(vis,0);
fors(i,1,n){
int u=tree[1];//以最小的初始化
//tree[]存的是dis最小节点的编号，出队最小节点
vis[u]=1;
tree[u + N] = 0;//默认0号节点dis为无穷大，相当于出队x
update(u);
for(int i=head[u] ; i ; i=edge[i].u){
int &v=edge[i].v;
if(!vis[v] && dis[v] > dis[u] + edge[i].val){
dis[v] = dis[u] + edge[i].val;
update(v);//每次更新
}
}
}
}最小生成树
//Kruskal
// 并查集+sort b不需要连反向边之类的因为 主要是对边权排序
struct node
{
int u,v,val;
bool operator < (const node &ano) const {
return val < ano.val;
}
}edge[maxn];
int m,n;
int f[maxn];
int find(int x){
return f[x]==x ? x : (f[x] = find(f[x]));
}
int tot;
ll ans;
void kroual(){
fors(i,1,n)
f[i]=i;
sort(edge+1,edge+tot+1);
fors(i,1,m){
int a=find(edge[i].u),b=find(edge[i].v);
if(a!=b){
f[b]=a;
ans+=edge[i].val;
}
}
}
int main(int argc, char const *argv[])
{
n=read(),m=read();
fors(i,1,m){
int a=read(),b=read(),c=read();
edge[++tot]=(node){a,b,c};
}
kroual();
writen(ans);
return 0;
}
// Prim + priority //需要连反向边
struct node
{
int u,v,val;
}edge[maxn];
int n,m,head[maxn],tot,vis[maxn],dis[maxn];
ll ans;
void add(int u,int v,int val){
edge[++tot].v=v,edge[tot].u=head[u],head[u]=tot;edge[tot].val=val;
}
typedef pair<int,int> pii;
priority_queue<pii , vector<pii> , greater<pii> > q;
void prim(){
mem(dis,127);
dis[1] = 0;
int cnt=0;
q.push(make_pair(0,1));
while(!q.empty() && cnt < n){
int tmpd=q.top().first,u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
++cnt;
ans+=tmpd;
for(int v,i=head[u] ; i ;i=edge[i].u){
v=edge[i].v;
if(edge[i].val < dis[v]){
dis[v] = edge[i].val;// 对边的大小判断
q.push(make_pair(dis[v],v));
}
}
}
}负环判定
在SPFA里跑最短路记录每个点出现的次数，一个位置入队次数不小于n次,那它一定位于环上
莫名奇妙，被luogu的模板题卡常了，明明和别人算法一样 迷qwq~~
int SPFA(){
mem(dis,127);
nodeq q;//这里手写队列 qwq
q.push(1);
dis[1] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
if(cnt[u] >= n) return 1;//当这是出队的点 出现次数大于N 为负环
vis[u] = 0;
for(int i = head[u] ; i ;i = edge[i].u){
int v = edge[i].v;
if(dis[v] > dis[u] + edge[i].val){
dis[v] = dis[u] + edge[i].val;
if(!vis[v]){
vis[v] = 1;
++cnt[v];//在vis满足条件的里面 ++ 再判断
if(cnt[v] >= n ) return 1;
q.push(v);
}
}
}
}
return 0;
}LCA最近公共祖先
听说树链剖分写LCA省时间（当时没学树剖，惊呆.avi）
然后一学，哇，什么都写树剖qwq（我写树剖比倍增快多了qwq）
每次求$LCA(x,y)$的时候就可以判断两点是否在同一链上
如果两点在同一条链上我们只要找到这两点中深度较小的点输出就行了
如果两点不在同一条链上
那就找到深度较大的点令它等于它所在的重链链端的父节点即为$x=f[top[x]]$
直到两点到达同一条链上，输出两点中深度较小的点
struct node
{
int u,v;
}edge[maxn];
int head[maxn],tot;
void add(int u,int v){
edge[++tot].u = head[u];
edge[tot].v = v;
head[u] = tot;
}
int siz[maxn],son[maxn],fa[maxn],tops[maxn],depth[maxn];
int n,m;
void dfs1(int u,int f,int dep){
fa[u] = f;//dfs1处理深度，父亲，Size，儿子
depth[u] = dep;
siz[u] = 1;//记得初始化为1,不然会超时
int maxson = -1;//标记重儿子
for(int i = head[u];i;i=edge[i].u){
int v = edge[i].v;
if(v == f) continue;
dfs1(v,u,dep+1);//先dfs完再处理儿子
siz[u] += siz[v;//加上Siz
if(maxson < siz[v]) maxson = siz[v] , son[u] = v;
}
}
void dfs2(int u,int topf){//dfs2处理祖先
tops[u] = topf;
if(!son[u]) return;
//没有儿子直接return，不然就遍历其儿子
dfs2(son[u],topf);//祖先是topf不是u qwq
for(int i = head[u];i;i=edge[i].u){
int v = edge[i].v;
if(v == son[u] || v == fa[u]) continue;
dfs2(v,v);//每一v都有一条顶端为自己的链
}
}
int main(int argc, char const *argv[])
{
n = read() , m = read();
int s = read();
fors(i,1,n-1){
int u = read() ,v = read();
add(u,v);
add(v,u);
}
dfs1(s,0,1);//一定要预处理 qwq
dfs2(s,s);
fors(i,1,m){
int x = read() ,y = read();
while(tops[x] != tops[y]){//先判断祖先是否相同
if(depth[tops[x]] < depth[tops[y]]) swap(x,y);//将x换到祖先深度大的点
x = fa[tops[x]];//从祖先的父亲开始跳
}
writen(depth[x] < depth[y] ? x : y);//输出深度小的
}
return 0;
}二分图匹配
对于一个图G=（V,E），若能将其点集分为两个互不相交的两个子集X、Y，
使得X∩Y=∅，且对于G的边集V，若其所有边的顶点全部一侧属于X，
一侧属于Y，则称图G为一个二分图。
- 当且仅当无向图G的回路个数为偶数时，图G为一个二分图。
无回路的图也是二分图。 - 在二分图G中，任选一个点V，使用BFS算出其他点相对于V的距离（边权为1）对于每一条边E，枚举它的两个端点，若其两个端点的值，一个为奇数，一个为偶数，则图G为一个二分图。
- 对于一个二分图G的子图M,若M的边集E的的任意两条边都不连接同一个顶点，则称M为G的一个匹配。
- 对于二分图G的一个子图M，若M为其边数最多的子图，则称M为G的最大匹配。
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
int dfs(int u){
for(int i = head[u] ; i ; i = edge[i].u){
int v = edge[i].v;
if(!vis[v]){//如果相邻顶点已经被染成同色了,说明不是二分图
vis[v] = 1;//如果相邻顶点没有被染色,染成c,看相邻顶点是否满足要求
if((!point[v]) || dfs(point[v])){
point[v] = u;
return 1;
}
}
}
return 0;
}
int main(){
n = read() , m = read() , e = read();
fors(i,1,e){
int x = read() , y = read();
if(x>n||y>m) continue;
add(x,y+n);
add(y+n,x);
}
fors(i,1,n){
mem(vis,0);
if(dfs(i)) ++ans;
}
writen(ans);
return 0;
}
k短路
由于不会 k 短路的正解，只能靠着A* 水水 qwq
先上一个 A* 求 k短路 的过程
算法过程：
- 将图反向，用Dijstra+heap求出t到所有点的最短距离，目的是求所有点到点t的最短路，用dis[i]表示i到t的最短路，其实这就是$A*$的启发函数，显然：$h(n)<= n$到t的实际代价。
- 定义估价函数。我们定义$g(n)$为从s到n所花费的代价，$h(n$)为$dis[n]$，显然这符合$A*$算法的要求。
- 初始化状态。状态中存放当前到达的点$i,f_i,g_i$。显然，$f_i=g_i+dis[i]$。初始状态为$(S,dis[S],0)$，存入优先级队列中。
- 状态转移。假设当前状态所在的点v相邻的点u，我们可以得到转换：$(V,fv,gv)$-->$(U,fu+w[v][u],gv+w[v][u])$。
- 终止条件。每个节点最多入队列$K$次，当$t$出队列$K$次时，即找到解。
int n,m;
struct e{
int u,v,val;
}edge[maxn],edge_hx[maxn];//edge_hx表示 求解的正向边 , edge[]求Dijkstra的反向最短路
int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
edge[++tot].v = v;//如果不是双向边，一定要反向啊qwq
edge[tot].u = head[u];
head[u] = tot;
edge[tot].val = val;
edge_hx[++toth].v = v;//正向图跑A*
edge_hx[toth].u = head_hx[u];
head_hx[u] = toth;
edge_hx[toth].val = val;
}
struct node{
int num,dis;
bool operator < (const node &ano) const{
return dis==ano.dis ? num > ano.num : dis > ano.dis;
}
};
priority_queue<node> q;
int dis[maxn];
void Dijkstra(int ed){
memset(dis,127,sizeof dis);
dis[ed]=0;
q.push((node){ed,0});
while(!q.empty()){
node u=q.top();q.pop();
if(u.dis != dis[u.num]) continue;
for(int i=head[u.num];i;i=edge[i].u){
int v=edge[i].v;
if(dis[v] > u.dis+edge[i].val)
dis[v]=u.dis+edge[i].val,q.push((node){v,dis[v]});
}
}
}
struct Node
{
int x,val;
bool operator< (const Node &a)const{
return val+dis[x] > a.val+dis[a.x];
}//用于计算优先队列 ， 估价函数 由于优先队列默认从大到小，所以重载也要反着来
};
priority_queue<Node>Q;//用于A*
int cnt[maxn];//计算次数
int Astar(int st, int ed, int k){
Q.push( (Node){ st, 0} );
while( !Q.empty() ){
Node u= Q.top(); Q.pop();
++cnt[u.x];
if(cnt[u.x] == k && u.x == ed) return u.val;//如果出现次数为k，且为重点的话，返回第k短路的值
if(cnt[u.x] > k) continue;
for(int i=head_hx[u.x];i;i=edge_hx[i].u){
int v= edge_hx[i].v, w= edge_hx[i].val;
Q.push((Node){v, u.val + w});//将每个状态加入优先队列
}
}
return -1;
}
int main()
{
n = read(),m=read();
fors(i,1,m){
int u = read(),v = read() , w = read();
add(u,v,w);
add(v,u,w);
}
int st=read(), ed=read(), k=read();
if( st==ed ) ++k;//st == ed 默认存在一条最短的边
Dijkstra(ed);
writen(Astar( st, ed, k ));
return 0;
}
严格k短路我们就去掉重复的值（set！！）
每次当到达终点的时候就将值加入set，判断set的size == k就可以了，给出完整代码 qwq
set<int> dis_kth;
int Astar(int st, int ed, int k){
Q.push( (Node){ st, 0} );
while( !Q.empty() ){
Node u= Q.top(); Q.pop();
if(u.x == ed) dis_kth.insert(u.val);//如果到达终点就加到set
if(k == dis_kth.size() && u.x == ed) return u.val;//大小相同并且是终点则直接返回这个值
if(dis_kth.size() > k) continue;
//如果大于 k 的话，就直接continue
for(int i=head_hx[u.x];i;i=edge_hx[i].u){
int v= edge_hx[i].v, w= edge_hx[i].val;
Q.push((Node){v, u.val + w});
}
}
return -1;
}
数论
乘法逆元
数学 ： 一个数 x的倒数，称乘法逆元，是指一个与 x相乘的积为1的数，记为 $1/x$ 或者 $x ^{-1}$
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int k=exgcd(b,a%b,y,x);//注意顺序
y-=a/b*x;
return k;
}
int main(int argc, char const *argv[])
{
n=read(),p=read();
inv[1]=1;
inv[0]=1;//线性递推注意初始化
fors(i,2,n){
inv[i]=(ll)(p - p/i)*inv[p % i] % p;
}
fors(i,1,n){
writen(inv[i]);
}
/*exgcd
fors(i,1,n){
int x,y,a=i;
exgcd(a,p,x,y);
writen((x%p+p)%p);
}
*/
return 0;
}
数论分块
$[n/i]$取值有$O(sqrt(n))$个
对于每一段连续相等的$[n/i]$,直接用该值与对应$i$的和相乘即可
// 问题转化 这个约数 在 1~n 中出现了多少次，
const int maxn = 1e7+7;
int n,m,k,sum[maxn],tot,prime[maxn],vis[maxn];
const int mod = 1e9+7;
int pows(int a,int b){
int r=1;
while(b){
if(b & 1) r=(r * 1ll * a) % mod;
a = a * 1ll * a % mod; // 注意精度问题
b >>= 1;
}
return r;
}
void init(){
sum[1]=1;//注意初始化
fors(i,2,n){
if(!vis[i]){
prime[++tot] = i;//筛因子
sum[i]=pows(i,k);//计算
}
int maxns=n/i;
for(int j=1;j<=tot && prime[j] <= maxns ; ++j){
vis[i * prime[j]] =1;
sum[i * prime[j]] = sum[prime[j]] * (ll) sum[i] % mod;
//预处理
if(i % prime[j] == 0) break;
}
}
}
int main(int argc, char const *argv[])
{
n=read(),k=read();
ll ans=0;
init();
fors(i,1,n){
ans=(ans + 1ll * sum[i]*(n/i) % mod) % mod;
}
writen(ans);
return 0;
}素数
#define INF ~0ull //ull的最大值 ，只能 ull
ll mul(ll a,ll b,ll p){
a=a%p,b=b%p;
return ((a * b - (ll)( ((long double) a * b + 0.5) / p) * p) % p + p ) % p;
}
ll pows(ll a,ll b,ll p){
ll ret=1;
while(b){
if(b & 1) ret =mul(ret , a , p);
a = mul(a , a , p);
b >>= 1;
}
return ret;
}
const int primes[] = {2,3,5,7,11,13,17,19,23,29};
int isprime(ll n){
fors(i,0,5){
if(primes[i] == n) return 1;
if(primes[i] > n || n % primes[i] == 0) return 0;
ll tmpn = n - 1 , tmps = pows(primes[i] , tmpn , n);
if(tmps != 1) return 0;
while(tmps == 1 && !(tmpn & 1)){
tmpn >>= 1;
tmps = pows(primes[i] , tmpn , n);
if(tmps != 1 && tmps != n-1) return 0;
}
}
return 1;
}
int isprime2(int n){
if(n==1) return 0;
if(n == 2 || n== 3 || n == 5) return 1;
if(n % 6 != 1 && n % 6 != 5) return 0;
int len=sqrt(n);
for(int i=5;i<=len;i+=6){
if(n % i == 0 || n % (i+2) == 0) return 0;
}
return 1;
}
int isprim[maxn],tot,vis[maxn];
void isprime3(int maxns){
vis[1]=1;
fors(i,2,maxns){
if(!vis[i]){
isprim[++tot] = i;
}
for(int j=1;j<=tot && (i * isprim[j] <= maxns); ++j){
vis[i * isprim[j] ] = 1 ;
if(i % isprim[j] == 0) break;
}
}
}
int main() {
ll n=read(),m=read();
isprime3(n);
//while(~scanf("%d,n))/ scanf("") != EOF 对于多组数据的读取
while(m--){
ll k=read();
if(!vis[k]){
puts("Yes");
}
else puts("No");
}
return 0;
}反素数 ：任何小于 $n$ 的正数的约数个数都小于 $n$ 的约数个数
设$p_i$ 严格递增 并且$k_i=0$也算在内，则如果则如果$k_x < k_y$ 并且$x<y$，那么显然这个数不可能是反素数，因为交换$k_x$ 和$k_y$会更好。
所以当$p_i$ 递增时k_i$ 是递减的，这个数$x$才可能是反素数
因为前$12$个素数的积 $>2*10^9$ 所以最多用到$12$个素数，手动打表。
const int prime[]={0,2,3,5,7,11,13,17,19,23,29,31,37};
ll sc[20],tc[20],tt[20],n,ansx,ansy;
void dfs(ll x){
tt[x] = 1;
sc[x] = sc[x-1] * prime[x] ;
tc[x] = tc[x-1] << 1;
while(tt[x] <= tt[x-1] && sc[x] <= n){
if(ansx < tc[x]) ansx = tc[x],ansy = sc[x];
else if(tc[x] == ansx) ansy=min(ansy,sc[x]);
dfs(x+1);
++tt[x],tc[x]+=tc[x-1],sc[x] *= prime[x];
}
}
int main() {
sc[0]=1;
tc[0]=1;
tt[0]=233333333;
ansx = ansy = 1;
n=read();
dfs(1);
writen(ansy);
return 0;
}给定一个正整数$n$，输出最小的整数，满足这个整数有$n$个因子
对于每个数m来说，他都能分解成形如
$m=2^p1 *3^p2 *5^p3 * 7^p4 * 11^p5......$
所以m的因子的个数为 $(p1+1) * (p2+1) * (p3+1) * (p4+1)……$
所以我们对每个质因子进行$dfs$，去把所有的情况都遍历。。。
但是因为有因数个数为$n$这个条件，所以可以相应的进行剪枝。
而且因为求的是满足条件的$m$的最小的那个，所以又可以进行剪枝了。
而且因为n很小（$<1000$）所以极限情况是每个质因子的指数都是1这样的话，这个数的因子个数为$2$的$10$次方所以说最多准备10个素数就行。
const int prime[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,57,59};
ll ans;
int n ;
void dfs(ll temp,ll num,ll p){
if(num > n) return;
if(num == n ){
if(temp < ans)
ans = temp;
return;
}
for(int i = 1;i <= 64;i++){
temp *= prime[p];
if(temp >= ans)break;
if(num < n){
dfs(temp,num*(i+1),p+1);
}
}
}
int main(int argc, char const *argv[])
{
ans=1e18;
n=read();
if(n==1){
puts("1");
return 0;
}
dfs(1ll,1ll,1ll);
writen(ans);
return 0;
}三分法
给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值
double Check_QJZ(double x){
double sum = 0;//初始为0；
for(int i = n ; i >= 0 ;--i){
sum = sum * x + w[i];//秦九昭算法，sum求和从高次项 每次*x + 这一项的系数
}
return sum;
}
const double epxs = 1e-7;
int main(int argc, char const *argv[])
{
n = read();
double l , r ;
cin>>l>>r;
for(int i = n ; i >= 0; --i){
cin>>w[i];//题意是从高次项到低次项 读入，所以这里反向存取
}
while(r - l > epxs){
double mid = (l+r)/2.0;//三分，每次 mid + - 一个epxs 记住不是1 是 0.00000001 ~~！！！
if(Check_QJZ(mid - epxs) > Check_QJZ(mid + epxs)){
r = mid;//二分基本操作
}
else l = mid;
}
printf("%0.5lf\n",r);
return 0;
}Exgcd : $ a* x ≡ ~c ~(~mod ~b) -> a*x + b*y =c $
- 若$gcd(a, b) = 1$，则方程$a*x ≡ c (~mod~ b)$在$[0, b-1]$上有唯一解。
存在整数$x$和y使$a*x_1 + b*y_1 = gcd(a, b) = 1$，即我们可以求出$a x ≡ 1 (~mod~b)$的解$x0$。加上或减去若干倍$b$都是该方程的解.
- 若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。
如果得到$ax ≡ c (~mod ~b)$的某一特解$X$，那么令$g = b/gcd(a, b)$，可知$x$在$[0, g-1]$上有唯一解，所以$x = (X ~mod~ g + g) ~mod~ g$就可以求出最小非负整数解$x$ , $X mod ~ g$可能是负值就加上$g$,再模一下$g$就在 $[0, g-1] $内了。
int Exgcd(int a, int b , int &x , int &y){
if(!b){
x = 1;
y = 0;
return a;
}
int tmp = Exgcd(b , a%b , y ,x);
y -= a/b*x;
return tmp;
}
x = (x + b/gcd(a,b)) % (b/gcd(a,b));ExCRT 用于求解同余方程组
- $~~~~~~~~~~~~~~~~~~~~~~~~~~~~x ≡ b_1 (~mod ~a_1 )$
- $~~~~~~~~~~~~~~~~~~~~~~~~~~~~x ≡ b_2 (~mod ~a_2 )$
- $~~~~~~~~~~~~~~~~~~~~~~~~~~~~x ≡ b_3 (~mod ~a_3 )$
int a[maxn] , b[maxn] , n , m , ans ;
int Exgcd(int a, int b , int &x , int &y){
if(!b){
x = 1;
y = 0;
return a;
}
int tmp = Exgcd(b , a%b , y ,x);
y -= a/b*x;
return tmp;
}
int mul(int a,int b,int mod){
a %= mod , b %= mod;
return ((a * b - (LL)(((long double) a * b + 0.5)/mod ) * mod) + mod) % mod;
}
int Excrt(){
int ans = b[1] , fir = a[1] , x = 0, y=0;
fors(i,2,n){
int lastx = fir;//先保存上一个的值 ， 只用来 求exgcd
int st = a[i];
int bs = (b[i] - ans % st + st) % st;// 被模数的差值
int tmp = Exgcd(lastx , st , x , y);//a[i-1] , a[i] ， 求解
if(bs % tmp != -1) return -1;// 如果差值不能 整除gcd return -1;
int lcms = st/tmp;
x = mul(x , bs/tmp , lcms);// * （b2 - b1） 为最小非负数解
ans += fir * x;
fir *= lcms; //对上一个a[]乘以lcm
ans = (ans + fir) % fir;//每次mod 上一次 fir 求最小非负数解
}
return ans;
}
signed main()
{
n = read();
fors(i,1,n) a[i] = read() , b[i] = read();
cout<<Excrt()<<endl;
return 0;
}BSGS
已知数$a,p,b$，求满足$a^x≡b~( ~mod~ p)$的最小自然数$x$ 。当$p$质数时
$(a^i)^m≡a^j$ $×b~mod~p$ ------$m=$⌈$sqrt(p)$⌉
LL BSGS(LL a , LL b , LL p){
int block = sqrt(p) + 0.5;//类似分块 不过要 ceil
int base = 1;//初始base = 1,先模拟 存 b * a^j
map<LL , LL> maps;
int tmp = 0;//保留上一个的值 ，计算a ^ block
fors(i,0,block){//从 幂 0 开始
maps[mul(base , b , p)] = i+1;//保留 i+1 当求解的时候，要-1
tmp = base;
base = mul(base , a , p);//每次直接乘以a,免去快速幂
}
base = tmp;//保留上一个的值
fors(i,1,block){//开始查询 从 幂 1 开始
if(maps[base]){//他、如果存在这个值则直接返回 ，要记得i 乘以 block
return i * block - (maps[base] - 1);
}
base = mul(base , tmp , p);//每次计算 (a^m) ^i
}
return -1;//无解则返回 -1；
}ExBSGS
处理 p 不为质数的情况 ， 主要是使用gcd 对式子同除以 gcd 使 p 为质数 qwq
注意保留其中的答案
int ExBSGS(int a,int b,int p){
a %= p , b %= p ;
if(b == 1) return 0;
//特判 ， 如果 b == 1 那么a ^ 0 = 1
int t = 1 , cnt = 0;
while(1){
int g = gcd(a,p);
if(g == 1) break;//如果 a, p 没有最大公约数，表示已经是质数了
if(b % g != 0) return -1;//是b % gcd !!! b不整除gcd 则无解
p /= g , b /= g , t = mul(t , a / g , p);
++cnt;// 表示已经
if(b == t) return cnt;
}
Maps maps;
maps.clear();
int block = sqrt(p)+0.5;
int nows = t ;
int base = 1;
int tmp = 1;
fors(i,0,block){//从 幂 0 开始
maps.insert(mul(base , b , p) , i);
tmp = base;
base = mul(base , a , p);
}
base = tmp;
fors(i,1,block){
nows = mul(nows, base , p);//注意要使用 gcd中的保存的幂 作为底，每次 *a^m
if(maps.query(nows) != -1){
return i * block - maps.query(nows) + cnt;//记得加上gcd中的次数
}
}
return -1;
}杨辉三角形
１
１ １
１ ２ １
１ ３ ３ １
１ ４ ６ ４ １
１ ５ 10 10 ５ １
１ ６ 15 20 15 ６ １
１ ７ 21 35 35 21 ７ １
１ ８ 28 56 70 56 28 ８ １
- 由1开始，正整数在杨辉三角形出现的次数为：∞,1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4...
- 杨辉三角每一行的平方和在杨辉三角出现奇数次
- 杨辉三角每一行的和是2的幂。
- 第 n 行的数字个数为 n 个。
- 第$ {\displaystyle n} $ 行的第$ {\displaystyle k} $个数字为组合数$ {\displaystyle C_{n-1}^{k-1}} $。
- 第 ${\displaystyle n}$ 行数字和为${\displaystyle 2^{n-1}}$。
- 除每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和（也就是说，第 ${\displaystyle n} $行第${\displaystyle k}$ 个数字等于第 ${\displaystyle n-1} $行的第$ {\displaystyle k-1}$ 个数字与第 $k$ 个数字的和）。这是因为有组合恒等式：$ {\displaystyle C_{n+1}^{i+1}=C_{n}^{i}+C_{n}^{i+1}} $。可用此性质写出整个杨辉三角形
int C[201][201];
C[0][0] = 1;//要C[0][0]初始化为1
fors(i,1,20){//行
C[i][0] = 1;//记住每一行第一个元素为1
fors(j,1,i)//列
C[i][j] = c[i-1][j] + c[i-1][j-1];
}Lucas 组合数
$Lucas(n,m,p) = C(n ~mod~ p, m ~mod~ p) * Lucas(n/p , m/p ,p)$
$Lucas(n,0,p) = 1 , C(n,m) = (n! / (n-m)!)^{p-2} mod p $
int a[maxn];
LL C(LL n ,LL m){
if(m > n) return 0;//注意 先求m! 的逆元 在（n-m)！的逆元 接着 和n！全部乘起来
return ((a[n] * pows(a[m] , p-2 , p)) % p * pows(a[n-m] , p-2 , p) % p); //注意是组合，不是排列 ，所以要 * m！的倒数（逆元）
}
LL lucas(LL n , LL m){
if(!m) return 1;
return C(n % p ,m % p) * lucas(n / p , m / p) % p;
}//O(p) 的处理 -》 C 所以是 % 接着lucas -》 /p
int main(){
int t = read();
while(t--){
int n = read() , m = read() ;
p = read();
a[0] = 1;//注意初始化为 1 求 1~P 的阶层
fors(i,1,p)
a[i] = (a[i-1] * i) % p;
writen(lucas(n+m,m));
}
return 0;
}卡特兰数
只要看到能转变为合法括号序列问题的或者出栈序列问题的求方案数的题就上卡特兰数就行了
$h(n)=C(2n,n)-C(2n,n-1) (n = 0,1,2,...)$
n = read();
C[0][0] = 1;
fors(i,1,n*2){
C[i][0] = 1;
fors(j,1,i)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
writen([2*n][n] - C[n*2][n-1]);矩阵
矩阵乘法 分别给定 $n×p$ 和 $p×m$ 的两个矩阵 $A$和 $B$，求 $A×B$。
// a.m[i][k]*b.m[k][j] ->类似 floyd i-k-j - c[i][j]
struct node
{
int m[507][507];
}a,b,c;
int n,m,p;
const int mod=1e9+7;
int main(int argc, char const *argv[])
{
n=read(),p=read(),m=read();
fors(i,1,n)
fors(j,1,p)
a.m[i][j]=read();
fors(i,1,p)
fors(j,1,m)
b.m[i][j]=read();
mem(c.m,0);
fors(i,1,n)
fors(k,1,p)
fors(j,1,m)
c.m[i][j]=(c.m[i][j] + a.m[i][k]*b.m[k][j]%mod + mod) % mod;;
fors(i,1,n){
fors(j,1,m)
write(c.m[i][j]),putchar(32);
putchar(10);
}
return 0;
}node mul(node a,node b){
node ans;
//mem(ans.m,0);
fors(i,1,3)//矩阵乘法 注意Floyd ， LL 精度需要
fors(k,1,3){
int tmp = a.m[i][k];
fors(j,1,3)
ans.m[i][j] = (ans.m[i][j] + tmp * b.m[k][j] ) % mod;
}
return ans;
}
int pows(int k){
node ans,e;
//mem(ans.m,0);
//mem(e.m,0);
fors(i,1,3) e.m[i][i] = 1; //单位矩阵对角为1
//注意是先单位矩阵 * 目标矩阵
ans.m[1][1] = ans.m[1][3] = ans.m[2][1] = ans.m[3][2] = 1;
//初始化矩阵
--k;// 注意 是 k-1 次方
while(k){
if(k & 1) e = mul(e , ans);
ans = mul(ans , ans);
k >>= 1;
}
return e.m[1][1];// 注意求出来的在第一个位置
}广义的斐波那契数列是指形如$a_n=p * a_{n-1}+q* a_{n-2}$的数列。今给定数列的两系数$p$和$q$，以及数列的最前两项$a_1$
和$a_2$ ，另给出两个整数$n$和$m$，试求数列的第$n$项$a_n$ 除以$m$的余数。
int pows(int a1,int a2,int p,int q,int k){
node ans,e;
e.m[1][1] = a2,e.m[1][2] = a1;//初始第一项，第二项
ans.m[1][1] = p , ans.m[1][2] = 1,ans.m[2][1] = q;//要乘的矩阵
while(k){
if(k & 1) e = mul(e , ans);//每次对初始矩阵 *
ans = mul(ans , ans);
k >>= 1;
}
return e.m[1][1];
}
signed main(){
int p = read() , q = read() , a1 = read() , a2 = read() , n = read();
mod = read();
if(n == 1) writen(a1);
else if(n == 2) writen(a2);
else writen(pows(a1,a2,p,q,n-2));//自己认为因为已经给出两项的值所以这里的幂要-2
return 0;
}然后给弱弱的自己背下来一些板子
1.$f(n)=a*f(n-1)+b*f(n-2)+c$；（a,b,c是常数）
2.$f(n)=c^n-f(n-1) $；（c是常数）
3.斐波拉契数列的第n项和第m项的最大公约数是 $gcd(F[n],F[m])=F[gcd(n,m)]$
(反正我证不来)
高斯消元法
给定一个线性方程组，对其求解
想象一个矩阵（最终好像就是一左下半角矩阵（应该是左对角下面一半都为0））
void Cal_s(){
fors(i,1,n){
int maxn_i = i;//找这一列系数最大值
fors(j,i+1,n){
if(fabs(maps[maxn_i][i]) < fabs(maps[j][i])){
maxn_i = j;
}
}//如果系数最大的为0则无解
if(fabs(maps[maxn_i][i]) < epx){
puts("No Solution");
exit(0);
}
if(maxn_i != i) std::swap(maps[maxn_i] , maps[i]);
//交换这两行
double divs = maps[i][i];
fors(j,i+1,n+1) maps[i][j]/=divs;//接下来每一个元素 / 这个系数
fors(j,i+1,n){//然后对每一行 div
divs = maps[j][i];//取第j行，第i个元素
fors(k,i,n+1){//对每一行 - 第i行的元素*div
maps[j][k] -= maps[i][k] * divs;
}
}
}//开始回代
ans[n] = maps[n][n+1];//从最后一行 直接等于 最后一行方程的答案 Z = ...
for(int i = n ; i>=1 ; --i){///从n-1开始 ， 每次去方程的答案作为起始值
ans[i] = maps[i][n+1];
fors(j,i+1,n)//每次- 从上一个方程的ans[j~n] * maps第i行第j 的值
ans[i] -= (maps[i][j] * ans[j]);
}
}欧拉函数
$phi(x)$表示小于等于x的正整数中有几个与其互质(出现的p,q都是质数)
- $phi(a~*~b) = phi(a) * phi(b)$ (a,b互质)
- $phi(p)=p-1$
- $phi(i * p)=p * phi(i)~ (i~mod~p==0)$
- $phi(i * p) = phi(i) * (p-1) (i ~mod ~p!=0)$
int phi[p];
void Phi(int maxn) {
phi[1] = 1;
for(int i=2; i<=maxn; ++i)
if(!phi[i]) {
for(int j=i; j<=maxn; j+=i) {
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}
}
//顺便筛素数的版本(耗空间),但快，推荐离线查找maxn最大值（防止MLE）
void Phi(int maxn){
phi[1]=1;
int tot=0;
fors(i,2,maxn){
if(!vis[i]){
prime[++tot]=i;
phi[i]=i-1;//对应第二定理
}
for(int j=1,k;j<=tot && (k=i*prime[j])<=maxn;++j){
vis[k]=1;//素数的判定
if(i % prime[j]==0) {
phi[k]=phi[i]*prime[j];//对应第三定理
break;
}
phi[k]=phi[i]*(prime[j]-1);//对应第四定理
}
}
}
/*int OL(int n) {//单点查询Phi不过可能比较慢
int x=sqrt(n+0.5),ans=n;
fors(i,2,x)
if(n%i==0) {
ans=ans/i*(i-1);
while(n%i==0) n/=i;//分解质因数 第一定理
}
if(n>1) ans=ans/n*(n-1);
return ans;
//P2158 是个简单的求Phi *2+1 就ok了，不过你要手动模拟一下才知道为什么。
}
*/欧拉降幂
求$a^b~mod~c~$可以转化为$a^{~b~mod~phi(~c~)+phi(~c~)}~mod~c$
注意当$phi(c)==1 $时返回$0$；
int solve(int mods){
if(mods==1) return 0;
int ok=phi(mods);
return pows(2,solve(ok)+ok,mods);//这里只是求无限的2^2^2^2...%p
}
int isprim[maxn],tot,vis[maxn];
void isprime3(int maxns){
vis[1]=1;
fors(i,2,maxns){
if(!vis[i]){
isprim[++tot] = i;
}
for(int j=1;j<=tot && (i * isprim[j] <= maxns); ++j){
vis[i * isprim[j] ] = 1 ;
if(i % isprim[j] == 0) break;
}
}
}
int isprime2(int n){
if(n==1) return 0;
if(n == 2 || n== 3 || n == 5) return 1;
if(n % 6 != 1 && n % 6 != 5) return 0;
int len=sqrt(n);
for(int i=5;i<=len;i+=6){
if(n % i == 0 || n % (i+2) == 0) return 0;
}
return 1;
}
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
int main(){
for(int i=1;i<=23333;++i){
system("data.exe > date.out");//data是你的随机数据程序（记得不要加freopen）
double st=clock();//计算开始时间
system("plus.exe < date.out > plus.out");
double ed=clock();//计算你的正解运行速度，也记得不要加freopen
system("pre.exe < date.out > pre.out");
if(system("fc plus.out pre.out")){
cout<<"WA"<<endl;
return 0;
//接着你就可以在data.out里查看是你程序答案错误的数据
}
else
printf("Ac,测试点 #%d, 用时 %.0lfms\n",i,ed-st);
}
return 0;
}