中国剩余定理/GAUSS消元
中国剩余定理:
设x\in Z
若有：
x \equiv a_1 \pmod{m_1}
x \equiv a_2 \pmod{m_2}
x \equiv a_3 \pmod{m_3}
…
x \equiv a_n \pmod{m_n}
令M=m_1\cdot m_2 \cdot m_3\cdot …\cdot m_n
M_i=\tfrac{M}{m_i}
$M_it_i \equiv 1\pmod{mi}会有x=\sum{i=1}^n a_iM_it_i$
模板题
#include
using namespace std;
const int N=15;
typedef long long LL;
int n,A[N],B[N];
LL M=1,res=0;
void exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1;
y=0;
}
else
{
exgcd(b,a%b,y,x);
y-=a/b*x;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&A[i],&B[i]);
M*=(LL)A[i];
}
for(int i=0;i<n;i++)
{
LL mi=M/A[i],t,x;
exgcd(mi,A[i],t,x);
res+=B[i]*mi*t;
}
printf("%lld",(res%M+M)%M);
return 0;
}
高斯消元
板子
#include
#include
#include
#include
#include
using namespace std;
const int N=110;
const double eps=1e-6;
int n;
double a[N][N];
int gauss()
{
int c,r;
for(c=0,r=0;c<n;c++)
{
int t=r;
for(int i=r;ifabs(a[t][c]))
t=i;
if(fabs(a[t][c])<eps)continue;
for(int i=c;i=c;i--)a[r][i]/=a[r][c];
for(int i=r+1;ieps)
for(int j=n;j>=c;j--)
a[i][j]-=a[r][j]*a[i][c];
r++;
}
if(r<n)
{
for(int i=r;ieps)
return 2;
return 1;
}
for(int i=n-1;i>=0;i--)
for(int j=i+1;j<n;j++)
a[i][n]-=a[i][j]*a[j][n];
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<=n;j++)
scanf("%lf",&a[i][j]);
int t=gauss();
if(!t)
{
for(int i=0;i<n;i++)printf("%.2lf\n",a[i][n]);
}
else if(t==1)printf("Infinite group solutions");
else printf("No solution");
return 0;
}
关于 Tarjan
首先是这位割点
#include
using namespace std;
const int N=2e4+5;
int n,m,root;
int flag[N],dfn[N],low[N],timestamp;
vectorG[N];
void tarjan(int u)
{
int cnt=0;
dfn[u]=low[u]=++timestamp;
for(int j:G[u])
{
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
if(u==root)cnt++;
if(u!=root&&dfn[u]=2)flag[u]=1;
}
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
root=i;
tarjan(i);
}
}
int res=0;
for(int i=1;i<=n;i++)res+=flag[i];
printf("%d\n",res);
for(int i=1;i<=n;i++)
{
if(flag[i])printf("%d ",i);
}
return 0;
}
强联通分量(SCC)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,in_stk[N];
int id[N],scc_cnt,Size[N];
int out[N],in[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u;
in_stk[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(in_stk[j])low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u])
{
++scc_cnt;
int y;
do
{
y=stk[top--];
in_stk[y]=0;
id[y]=scc_cnt;
Size[scc_cnt]++;
}
while(y!=u);
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i);
}
int res=0;
for(int i=1;i<=scc_cnt;i++)res=max(res,Size[i]);
printf("%d\n",res);
if(scc_cnt==1)puts("0");
else
{
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
{
int k=e[j];
if(id[i]!=id[k])
{
out[id[i]]++;
in[id[k]]++;
}
}
}
int none_out_cnt=0,none_in_cnt=0;
for(int i=1;i<=scc_cnt;i++)
{
if(!in[i])none_in_cnt++;
if(!out[i])none_out_cnt++;
}
printf("%d",max(none_in_cnt,none_out_cnt));
}
return 0;
}
边双联通分量(E-DCC)
#include
using namespace std;
const int N=5e5+5,M=4e6+5;
int n,m,h[N],e[M],ne[M],idx,dfn[N],low[N],timestamp,stk[N],top,d[N];
vector<vector >res;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u,int from)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j,i);
low[u]=min(low[u],low[j]);
}
else if(i!=(from^1))low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u])
{
vectortmp;
int y;
do
{
y=stk[top--];
tmp.push_back(y);
}
while(y!=u);
res.push_back(tmp);
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i,-1);
}
printf("%d\n",res.size());
for(auto item:res)
{
printf("%d ",item.size());
for(auto j:item)printf("%d ",j);
puts("");
}
return 0;
}
点双联通分量(V-DCC)
#include
using namespace std;
const int N=5e5+5,M=4e6+5;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int cnt;
vectordcc[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u,int father)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u;
int son=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
son++;
tarjan(j,u);
low[u]=min(low[u],low[j]);
if(dfn[u]<=low[j])
{
cnt++;
int y;
do
{
dcc[cnt].push_back(y=stk[top--]);
}
while(y!=j);
dcc[cnt].push_back(u);
}
}
else if(j!=father)low[u]=min(low[u],dfn[j]);
}
if(!father&&!son)dcc[++cnt].push_back(u);
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int root=1;root<=n;root++)
{
if(!dfn[root])
{
top=0;
tarjan(root,0);
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d ",dcc[i].size());
for(auto j:dcc[i])printf("%d ",j);
puts("");
}
return 0;
}