「Lesson5!·貝爾數·穿越廣場·舞動的夜晚」on 9.21
T1 Lesson5 !
解題思路
首先對于整張圖求出拓撲序，然後順着拓撲序其實也就是順着邊的方向，更新最長路，也就是從 1 節點到達這個節點的最長路。
然後再逆着拓撲序，反向求一下最長路，也就是從這個節點出發可以到達的最遠距離。
然後爆掃每一個點，用
multiset
維護删掉這個點以及與它相連的邊對最終答案造成的影響，更新答案。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,M=5e5+10,INF=1e18;
int T,n,m,top,ans,aid,sta[N],du[N],f[N],g[N];
int tot=1,head[N],nxt[M<<1],ver[M<<1];
multiset<int> se;
vector<int> v[N];
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
v[y].push_back(x);
du[y]++;
}
void topo_sort()
{
int pos=0;
for(int i=1;i<=n;i++)
if(!du[i])
sta[++top]=i;
while(top<n)
{
pos++;
for(int i=head[sta[pos]];i;i=nxt[i])
{
int to=ver[i]; du[to]--;
if(!du[to]) sta[++top]=to;
}
}
}
void solve()
{
tot=1; top=0; ans=INF; memset(head,0,sizeof(head)); memset(du,0,sizeof(du));
memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); se.clear();
n=read(); m=read();
if(n==1) return printf("1 0"),void();
for(int i=1;i<=n;i++) vector<int>().swap(v[i]);
for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add_edge(x,y);
topo_sort();
for(int i=1;i<=n;i++)
{
int x=sta[i]; f[x]=max(f[x],1ll);
for(int j=head[x];j;j=nxt[j])
f[ver[j]]=max(f[ver[j]],f[x]+1);
}
for(int i=n;i>=1;i--)
{
int x=sta[i]; g[x]=max(g[x],1ll);
for(int j=head[x];j;j=nxt[j])
g[x]=max(g[x],g[ver[j]]+1);
}
for(int i=1;i<=n;i++) se.insert(g[i]); se.insert(0);
for(int i=1;i<=n;i++)
{
int x=sta[i];
for(int j=0;j<v[x].size();j++)
{
int to=v[x][j];
se.erase(se.find(f[to]+g[x]));
}
se.erase(se.find(g[x]));
int temp=(*se.rbegin());
if(temp<ans) ans=temp,aid=x;
else if(temp==ans&&x<aid) aid=x;
for(int j=head[x];j;j=nxt[j])
{
int to=ver[j];
se.insert(g[to]+f[x]);
}
se.insert(f[x]);
}
printf("%lld %lld\n",aid,ans-1);
}
signed main()
{
freopen("johnny.in","r",stdin); freopen("johnny.out","w",stdout);
T=read(); while(T--) solve();
return 0;
}
T2 貝爾數
矩陣快速幂+CRT+exgcd
模數是一個合數，并且隻有 5 個比較小的質因數，是以我們可以選擇對于每一個小的質因數求出答案用 CRT 進行合并。
假設目前處理的質因數為 \(p\) ，對于小于 \(p\) 的答案可以直接根據公式1算出，對于比較大的直接矩陣快速幂通過第二個柿子進行轉移，每次轉移 \(p-1\) 個。
初始矩陣設為 \(1\times p\) 的矩陣，假設第一個數是 \(x\) 那麼 \(x\) 可以直接從 \(x+p-1\) 轉移過來， 其它的就運用公式進行運算就好了。
假如 \(p=3\) 的話（當然題目中并不存在這個因子）機關矩陣就是這樣： \(\begin{bmatrix}0 & 1 & 0\\\\0 & 1 & 1\\\\1 & 0 & 1\\\\\end{bmatrix}\)
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=110,M=1e3+10,mod=95041567;//31*37*41*43*47
int T,n,m,mo,q[N],f[M][10],c[N][N][10],s[10],t[10],d[10]={0,31,37,41,43,47};
struct Squre
{
int a[50][50];
void clear(){memset(a,0,sizeof(a));}
Squre friend operator * (Squre x,Squre y)
{
Squre z;z.clear();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
z.a[i][j]+=x.a[i][k]*y.a[k][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
z.a[i][j]%=mo;
return z;
}
}e;
void power(Squre &x,int y)
{
while(y)
{
if(y&1) x=x*e;
e=e*e; y>>=1;
}
}
int exgcd(int a,int b,int &x,int &y)
{
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y);
int z=x; x=y; y=z-y*(a/b);
return d;
}
void init(int pos)
{
int lim=d[pos],x,y; f[0][pos]=f[1][pos]=1;
exgcd(mod/d[pos],d[pos],x,y); t[pos]=(x%d[pos]+d[pos])%d[pos];
for(int i=1;i<=lim*2;i++)
{
c[i][0][pos]=c[i][i][pos]=1;
for(int j=1;j<i;j++)
c[i][j][pos]=(c[i-1][j][pos]+c[i-1][j-1][pos])%lim;
}
for(int i=2;i<=lim*2;i++)
for(int j=0;j<i;j++)
f[i][pos]=(f[i][pos]+c[i-1][j][pos]*f[j][pos])%lim;
}
void prework(int x)
{
e.clear(); e.a[x][1]=1;
for(int i=2;i<=x;i++)
e.a[i-1][i]=e.a[i][i]=1;
}
signed main()
{
freopen("bell.in","r",stdin); freopen("bell.out","w",stdout);
T=read();
for(int i=1;i<=T;i++) q[i]=read(),n=max(n,q[i]);
for(int i=1;i<=5;i++) init(i);
for(int i=1;i<=T;i++)
{
for(int j=1;j<=5;j++)
{
prework(d[j]); Squre x; x.clear();
m=mo=d[j];
int y=q[i]/(d[j]-1),res=q[i]%(d[j]-1);
for(int k=1;k<=d[j];k++)
x.a[1][k]=f[res+k-1][j];
power(x,y); s[j]=x.a[1][1];
}
int ans=0;
for(int j=1;j<=5;j++)
ans=(ans+s[j]*(mod/d[j])%mod*t[j]%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
T3 穿越廣場
AC自動機優化 DP
通過 AC 自動機 Fail 指針的定義可以知道，如果節點 u 的 Fail 指針指向 v ，那麼 v 到根節點的串一定是 u 到根節點串的最長字尾。
那麼我們對于一個節點一直跳下去每一個通過節點如果是兩個串中某一個的結尾，那麼相應的這個節點到根節點的路徑中也就是包含了這個串。
如果一個節點最後沒有子節點了他就一定會跳回根節點并且保留有之前走過的串的資訊。
設 \(f_{i,j,k,sta}\) 表示一共走了 \(i\) 步，其中有 \(j\) 個 D ，目前在 \(k\) 節點 包含串的狀态為 \(sta\) 的方案。
轉移方程就是：
(f[i+1][j+1][tre[k][0]][sta|ending[tre[k]['D']]]+=f[i][j][k][sta])%=mod,
(f[i+1][j][tre[k][1]][sta|ending[tre[k]['R']]]+=f[i][j][k][sta])%=mod;
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=110,mod=1e9+7;
int n,m,T,all,ans,ending[N<<1],tre[N<<1][2],f[N<<1][N][N<<1][4],fail[N<<1];
char ch1[N],ch2[N];
queue<int> q;
int insert(char ch[])
{
int len=strlen(ch+1),x=1;
for(int i=1;i<=len;i++)
{
int son=(ch[i]=='D');
if(!tre[x][son]) tre[x][son]=++all;
x=tre[x][son];
}
return x;
}
void get_Fail()
{
q.push(1); tre[0][0]=tre[0][1]=1;
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0;i<=1;i++)
{
int son=tre[x][i];
if(son) fail[son]=tre[fail[x]][i],q.push(son);
else tre[x][i]=tre[fail[x]][i];
}
}
}
void solve()
{
all=1; ans=0; memset(tre,0,sizeof(tre)); memset(f,0,sizeof(f));
memset(fail,0,sizeof(fail)); memset(ending,0,sizeof(ending));
n=read(); m=read(); scanf("%s%s",ch1+1,ch2+1);
ending[insert(ch1)]|=1; ending[insert(ch2)]=2; f[0][0][1][0]=1; get_Fail();
for(int i=1;i<=all;i++) for(int j=i;j;j=fail[j]) ending[i]|=ending[j];
for(int i=0;i<n+m;i++)
for(int j=0;j<=n;j++)
for(int k=1;k<=all;k++)
for(int sta=0;sta<4;sta++)
(f[i+1][j+1][tre[k][0]][sta|ending[tre[k][0]]]+=f[i][j][k][sta])%=mod,
(f[i+1][j][tre[k][1]][sta|ending[tre[k][1]]]+=f[i][j][k][sta])%=mod;
for(int i=0;i<=all;i++) ans=(ans+f[n+m][n][i][3])%mod;
printf("%lld\n",ans);
}
signed main()
{
freopen("square.in","r",stdin); freopen("square.out","w",stdout);
T=read(); while(T--) solve();
return 0;
}
T4 舞動的夜晚
最大流+Tarjan
先對于整個圖跑一次最大流也就是最大比對，如果對于最大比對這個點已經用過了那麼用它一定不會對答案造成影響。
對于最大流中沒有用到的邊建正邊，用到的建反邊，跑一邊 Tarjan 如果一個邊所連接配接的兩個點在同一個強連通分量裡。
表明這條邊是可以替代别的邊的，也可以了解為可以退流，是以不是我們要的答案。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=2e4+10,M=3e5+10,INF=1e18;
int tot=1,head[N],nxt[M<<1],ver[M<<1],edge[M<<1];
int n,m,t,fro,tim,top,cnt,Ans,sta[N<<1],low[N],bel[N],dfn[N],ending,Hd[N],dep[N];
bool ans[M],vis[N],b[N];
struct Road{int l,r;}pat[M];
void add_edge(int x,int y,int val)
{
ver[++tot]=y;
edge[tot]=val;
nxt[tot]=head[x];
head[x]=tot;
}
inline bool bfs()
{
memcpy(head,Hd,sizeof(Hd)); memset(dep,0x3f,sizeof(dep));
queue<int> q; while(!q.empty()) q.pop();
q.push(fro); dep[fro]=0;
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(dep[to]<=dep[x]+1||!edge[i]) continue;
q.push(to); dep[to]=dep[x]+1;
if(to==ending)return true;
}
if(x==ending) return true;
}
return false;
}
int dfs(int x,int in)
{
if(x==ending) return in;
int res=in;
for(int i=head[x];i;head[x]=i=nxt[i])
if(edge[i])
{
int to=ver[i];
if(dep[to]==dep[x]+1)
{
int tmp=dfs(to,min(res,edge[i]));
if(!tmp) dep[to]=0;
else edge[i]-=tmp,edge[i^1]+=tmp,res-=tmp;
}
if(!res) break;
}
return in-res;
}
void Tarjan(int x)
{
dfn[x]=low[x]=++tim; sta[++top]=x; b[x]=true;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);
else if(b[to]) low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x])
{
cnt++; int temp;
do
{
temp=sta[top--];
b[temp]=false;
bel[temp]=cnt;
}while(x!=temp);
}
}
signed main()
{
freopen("night.in","r",stdin); freopen("night.out","w",stdout);
n=read(); m=read(); t=read(); fro=0; ending=n+m+1;
for(int i=1,x,y;i<=t;i++)
x=read(),y=read(),pat[i]=(Road){x,y},
add_edge(x,y+n,1),add_edge(y+n,x,0);
for(int i=1;i<=n;i++) add_edge(fro,i,1),add_edge(i,fro,0);
for(int i=1;i<=m;i++) add_edge(i+n,ending,1),add_edge(ending,i+n,0);
memcpy(Hd,head,sizeof(head)); while(bfs()) dfs(fro,INF);
for(int i=1;i<=t;i++) ans[i]=edge[i<<1]^1;
for(int i=1;i<=n;i++) vis[i]=edge[(t+i)<<1]^1;
for(int i=1;i<=m;i++) vis[n+i]=edge[(t+n+i)<<1]^1;
tot=1;
for(int i=1;i<=n+m+2;i++) memset(head,0,sizeof(head));
for(int i=1;i<=t;i++)
if(!ans[i]) add_edge(pat[i].l,pat[i].r+n,0);
else add_edge(pat[i].r+n,pat[i].l,0);
for(int i=1;i<=n;i++)
if(!vis[i]) add_edge(fro,i,0);
else add_edge(i,fro,0);
for(int i=1;i<=m;i++)
if(!vis[i+n]) add_edge(i+n,ending,0);
else add_edge(ending,i+n,0);
Tarjan(fro);
for(int i=1;i<=n+m;i++)
if(!dfn[i])
Tarjan(i);
if(!dfn[ending]) Tarjan(ending);
for(int i=1;i<=t;i++)
if(bel[pat[i].l]==bel[pat[i].r+n])
ans[i]=true;
for(int i=1;i<=t;i++) Ans+=ans[i]^1;
printf("%lld\n",Ans);
for(int i=1;i<=t;i++)
if(!ans[i])
printf("%lld ",i);
return 0;
}