T1 lesson5！
正方拓扑最短路,然后在值域上开一个权值线段树/堆/multiset。
拓扑序枚举每个点，删去这个点贡献的答案，统计ans，再加上。
#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int _max(int a,int b){return a>b?a:b;}
int _min(int a,int b){return a<b?a:b;}
const int N=1100000,M=5100000,INF=0x7fffffff;
int head[2][N],cnt,n,m,dis[2][N],du[2][N],ansx,ans;
struct rec
{
int nxt,v;
}e[2][M];
int change[N];
int num[N],res[M];
void clear()
{
cnt=0;
memset(head,0,sizeof(head));
memset(change,0,sizeof(change));
memset(du,0,sizeof(du));
memset(res,0,sizeof(res));
memset(dis,0,sizeof(dis));
memset(num,0,sizeof(num));
ansx=1;ans=n;
}
void add(bool id,int x,int y)
{
e[id][++cnt].v=y;
e[id][cnt].nxt=head[id][x];
head[id][x]=cnt;
}
void pushup(int p)
{
res[p]=_max(res[ls],res[rs]);
}
void add(int p,int l,int r,int k)
{
if(l==r)
{
num[l]++;
if(num[l]>0)
res[p]=l;
else
{
num[l]=0;
res[p]=-INF;
}
return;
}
int mid=(l+r)>>1;
if(k<=mid)
add(ls,l,mid,k);
else
add(rs,mid+1,r,k);
pushup(p);
}
void del(int p,int l,int r,int k)
{
if(l==r)
{
num[l]--;
if(num[l]>0)
res[p]=l;
else
{
num[l]=0;
res[p]=-INF;
}
return;
}
int mid=(l+r)>>1;
if(k<=mid)
del(ls,l,mid,k);
else
del(rs,mid+1,r,k);
pushup(p);
}
void topo(int ty)
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(!du[ty][i])
{
if(!ty)
change[++change[ty]]=i;
q.push(i);
}
}
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[ty][x];i;i=e[ty][i].nxt)
{
if(dis[ty][e[ty][i].v]<dis[ty][x]+1)
dis[ty][e[ty][i].v]=dis[ty][x]+1;
if(!(--du[ty][e[ty][i].v]))
{
if(!ty)
change[++change[ty]]=e[ty][i].v;
q.push(e[ty][i].v);
}
}
}
}
int main()
{
freopen("johnny.in","r",stdin);
freopen("johnny.out","w",stdout);
int T=read();
while(T--)
{
n=read();m=read();
cnt=1;
memset(head,0,sizeof(head));
memset(change,0,sizeof(change));
memset(du,0,sizeof(du));
memset(res,0,sizeof(res));
memset(dis,0,sizeof(dis));
memset(num,0,sizeof(num));
ansx=1;ans=n;
for(int i=1;i<=m;i++)
{
int u,v;
u=read();v=read();
add(0,u,v);
add(1,v,u);
du[0][v]++;
du[1][u]++;
}
topo(0);
topo(1);
for(int i=1;i<=n;i++)
add(1,0,n,dis[1][i]);
for(int x=1;x<=n;x++)
{
for(int i=head[1][change[x]];i;i=e[1][i].nxt)
{
del(1,0,n,dis[0][e[1][i].v]+dis[1][change[x]]+1);
}
del(1,0,n,dis[1][change[x]]);
if(res[1]<ans||(ans==res[1]&&change[x]<ansx))
{
ansx=change[x];
ans=res[1];
}
for(int i=head[0][change[x]];i;i=e[0][i].nxt)
{
add(1,0,n,dis[0][change[x]]+dis[1][e[0][i].v]+1);
}
add(1,0,n,dis[0][change[x]]);
}
printf("%d %d
",ansx,ans);
}
return 0;
}
/*
1
6 5
1 3
1 4
3 6
3 4
4 5
*/
T2 贝尔数
暴力处理前50项贝尔数，把 (mod) 拆分成5个小质数的积。
矩阵乘法快速算出五个小质数下的答案，中国剩余定理合并答案。
[egin{vmatrix}
0& 0& 0& 0& 0& 1\
1& 1& 0& 0& 0& 0\
0& 1& 1& 0& 0& 0\
0& 0& 1& 1& 0& 0\
…& …& …& …& …& …\
0&0 &0 &0 &1 &1
end{vmatrix}
imes
egin{vmatrix}
B_1 \
B_2 \
B_3 \
B_4 \
…… \
B_p
end{vmatrix}
=
egin{vmatrix}
B_p \
B_{p+1} \
B_{p+2} \
B_{p+3} \
…… \
B_{2p-1}
end{vmatrix}]
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
//#define int long long
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int _min(int a,int b){return a<b?a:b;}
int _max(int a,int b){return a>b?a:b;}
int n,C[60][60][6],mo[6]={0,31,37,41,43,47},mod,B[60][6],ys[6],mi[6],ji=95041567;
long long ans=0;
struct jvzhen
{
int n,m;
int s[60][60];
void build()
{
for(int i=1;i<=n;i++)
s[i][i]=1;
return;
}
void clear()
{
memset(s,0,sizeof s);
}
void write()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",s[i][j]);
}
puts("");
}
}
void write01()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d",s[i][j]);
}
puts("");
}
}
};
jvzhen operator * (jvzhen &a,jvzhen &b)
{
jvzhen res;
res.clear();
res.n=a.m;
res.m=b.n;
memset(res.s,0,sizeof res.s);
for(int i=1;i<=a.n;i++)
{
for(int j=1;j<=b.m;j++)
{
for(int k=1;k<=a.m;k++)
{
res.s[i][j]=((res.s[i][j]+a.s[i][k]*b.s[k][j]%mod)%mod+mod)%mod;
}
}
}
return res;
}
jvzhen quick_pow(jvzhen a,int b)
{
jvzhen res;
res.clear();
res.n=res.m=a.n;
res.build();
while(b)
{
if(b&1)
{
res=a*res;
}
a=a*a;
b>>=1;
}
return res;
}
jvzhen x[6],y[6];
int exgcd (int a,int b ,int& x,int& y) {//函数将返回（gcd(a,b)）
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
int inv(int a,int b)
{
int iv,tp;
exgcd(a,b,iv,tp);
return (iv%b+b)%b;
}
int main()
{
freopen("bell.in","r",stdin);
freopen("bell.out","w",stdout);
for(int k=1;k<=5;k++)
{
mi[k]=ji/mo[k];
y[k].n=y[k].m=mo[k];
y[k].s[1][mo[k]]=1;
for(int i=2;i<=mo[k];i++)
{
y[k].s[i][i]=y[k].s[i][i-1]=1;
}
//y[k].write01();
}
for(int i=1;i<=5;i++)
{
C[0][0][i]=1;
}
for(int i=1;i<=50;i++)
{
for(int j=0;j<=i;j++)
{
for(int k=1;k<=5;k++)
{
C[i][j][k]=(C[i-1][j][k]+C[i-1][j-1][k])%mo[k];
}
}
}
for(int o=1;o<=5;o++)
{
B[0][o]=1;
for(int i=0;i<=49;i++)
{
for(int k=0;k<=i;k++)
{
B[i+1][o]+=C[i][k][o]*B[k][o]%mo[o];
B[i+1][o]%=mo[o];
}
}
}
for(int k=1;k<=5;k++)
{
x[k].n=mo[k];
x[k].m=1;
for(int i=1;i<=mo[k];i++)
{
x[k].s[i][1]=B[i][k];
}
}
int T=read();
while(T--)
{
ans=0;
n=read();
for(int i=1;i<=5;i++)
{
if(n<=50)
ys[i]=B[n][i];
else
{
int c=ceil(1.0*(n-mo[i])/(mo[i]-1)),gt=(n-mo[i])%(mo[i]-1);
if(gt==0) gt=mo[i]-1;
gt++;
mod=mo[i];
//y[i].write01();
jvzhen tmp=quick_pow(y[i],c);
//tmp.write01();
mod=mo[i];
tmp=tmp*x[i];
//tmp.write();
ys[i]=tmp.s[gt][1];
}
}
for(int i=1;i<=5;i++)
{
mod=ji;
//cout<<mi[i]<<" "<<mo[i]<<endl;
long long tmp=(1LL*mi[i]*ys[i]%ji*inv(mi[i],mo[i])%ji+ji)%ji;
//cout<<tmp<<endl;
ans=(ans+tmp)%ji;
}
printf("%lld
",ans);
}
return 0;
}
T3 穿越广场
AC自动机上DP，(f_{l,r,k,typ}) 表示匹配了长度 (l)，(r)个R，匹配到AC自动机 (k) 节点，状态为包含了串 (0，1，2，12)。
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
//#define int long long
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int _min(int a,int b){return a<b?a:b;}
int _max(int a,int b){return a>b?a:b;}
const int N=220,mod=1e9+7;
int m,n,f[N][N][N][4],ans;
char c[N];
namespace AC_zdj
{
int tot;
struct AC_zdj
{
int son[2],num,fail;//0R 1D
}AC[N];
int change(char x)
{
if(x=='R')
return 0;
else
return 1;
}
void Build(char *s,int ys)
{
int len=strlen(s+1),p=0;
for(int i=1,gg;i<=len;i++)
{
gg=change(s[i]);
if(!AC[p].son[gg])
AC[p].son[gg]=++tot;
p=AC[p].son[gg];
}
AC[p].num|=ys;
return;
}
void get_fail()
{
AC[0].fail=0;
queue<int>q;
for(int i=0;i<2;i++)
{
if(AC[0].son[i])
{
AC[AC[0].son[i]].fail=0;
q.push(AC[0].son[i]);
}
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<2;i++)
{
if(AC[u].son[i])
{
AC[AC[u].son[i]].fail=AC[AC[u].fail].son[i];
AC[AC[u].son[i]].num|=AC[AC[AC[u].son[i]].fail].num;
q.push(AC[u].son[i]);
}
else
AC[u].son[i]=AC[AC[u].fail].son[i];
}
}
}
void clear()
{
memset(AC,0,sizeof AC);
tot=0;
}
};
using namespace AC_zdj;
int main()
{
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
int T=read();
while(T--)
{
m=read();n=read();
scanf("%s",c+1);
Build(c,1);
scanf("%s",c+1);
Build(c,2);
get_fail();
f[0][0][0][0]=1;
for(int l=0;l<m+n;l++)
{
for(int r=0;r<=_min(l,m);r++)
{
for(int k=0;k<=tot;k++)
{
for(int typ=0;typ<4;typ++)
{
f[l+1][r+1][AC[k].son[0]][typ|AC[AC[k].son[0]].num]+=f[l][r][k][typ];
f[l+1][r+1][AC[k].son[0]][typ|AC[AC[k].son[0]].num]%=mod;
f[l+1][r][AC[k].son[1]][typ|AC[AC[k].son[1]].num]+=f[l][r][k][typ];
f[l+1][r][AC[k].son[1]][typ|AC[AC[k].son[1]].num]%=mod;
}
}
}
}
/*
for(int l=0;l<=m+n;l++)
{
for(int r=0;r<=_min(l,m);r++)
{
for(int k=0;k<=tot;k++)
{
for(int typ=0;typ<4;typ++)
{
// printf("%d %d %d %d:%d
",l,r,k,typ,f[l][r][k][typ]);
}
}
}
}*/
ans=0;
for(int i=0;i<=tot;i++)
{
ans+=f[n+m][m][i][3];
ans%=mod;
}
printf("%d
",ans);
clear();
memset(f,0,sizeof f);
memset(c,0,sizeof c);
}
return 0;
}
T4 舞动的夜晚
最大匹配跑完以后，对于有流量的边反向见图，没有的正向见图跑Tarjan强连通分量。一个分量内的或者匹配边两边端点的就不在答案内。其他的在。
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
//#define int long long
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int _min(int a,int b){return a<b?a:b;}
int _max(int a,int b){return a>b?a:b;}
const int N=110000,M=1100000,INF=0x7fffffff;
int n,m,T,s,t,xs,xt,dep[N],cnt=1,head[N],cur[N],zhan[N],top,belong[N],dfn[N],low[N],st,scc,ans;
vector<int>b[N];
bool inq[N],vis[M];
queue<int>q;
struct edge
{
int v,nxt,w,u;
}e[M];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].u=u;
e[cnt].nxt=head[u];
e[cnt].w=w;
head[u]=cnt;
}
void make(int u,int v)
{
add(u,v,1);
add(v,u,0);
}
bool SPFA()
{
q.push(xs);
for(int i=1;i<=t;i++)
dep[i]=INF,cur[i]=head[i];
dep[xs]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u],v;i;i=e[i].nxt)
{
v=e[i].v;
if(dep[v]>dep[u]+1&&e[i].w>0)
{
dep[v]=dep[u]+1;
if(!inq[v])
q.push(v);
}
}
}
return dep[xt]!=INF;
}
int dfs(int u,int minn)
{
if(u==xt)
{
ans+=minn;
return minn;
}
int used=0;
for(int i=cur[u],v;i;i=e[i].nxt)
{
cur[u]=i;
v=e[i].v;
if(dep[v]==dep[u]+1&&e[i].w>0)
{
int tmp=dfs(v,_min(minn,e[i].w));
if(tmp>0)
{
used+=tmp;
e[i].w-=tmp;
e[i^1].w+=tmp;
if(used==minn)
break;
}
}
}
return used;
}
void Dinic()
{
while(SPFA())
{
dfs(xs,INF);
}
}
void Tarjan(int cur)
{
dfn[cur]=low[cur]=++st;
zhan[++top]=cur;inq[cur]=true;
for(auto v:b[cur])
{
if(dfn[v]==0)
{
Tarjan(v);
low[cur]=_min(low[cur],low[v]);
}
else
{
if(inq[v]==true)
{
low[cur]=min(low[cur],dfn[v]);
}
}
}
if(low[cur]==dfn[cur])
{
scc++;
int ding;
do
{
ding=zhan[top];
inq[ding]=false;
zhan[top--]=0;
belong[ding]=scc;
}while(ding!=cur);
}
return;
}
int main()
{
freopen("night.in","r",stdin);
freopen("night.out","w",stdout);
n=read();m=read();T=read();
s=n+m+1;t=s+1;
for(int i=1,u,v;i<=T;i++)
{
u=read();v=read();
make(u,v+n);
}
for(int i=1;i<=n;i++)
make(s,i);
for(int i=1;i<=m;i++)
make(i+n,t);
xs=s;xt=t;
Dinic();
for(int i=2,u,v;i<=cnt;i++)
{
if(e[i].w)
{
u=e[i].u;v=e[i].v;
b[u].push_back(v);
//printf("%d %d
",u,v);
}
}
for(int i=1;i<=n+m+2;i++)
{
if(!dfn[i])
Tarjan(i);
}
for(int i=3,u,v;i<=cnt;i+=2)
{
u=e[i].u;
v=e[i].v;
if(belong[u]==belong[v]||e[i].w>0)
{
vis[i]=1;
}
}
ans=0;
for(int i=1;i<=T;i++)
{
if(!vis[i*2+1])
ans++;
}
printf("%d
",ans);
for(int i=1;i<=T;i++)
{
if(!vis[i*2+1])
printf("%d ",i);
}
return 0;
}