牛客多校第三场补题记录

A Ancestor

题意：给出两棵 $n$ 个节点的树 $A,B$，$A,B$ 树上每个节点均有一个权值，给出 $k$ 个关键点的编号 $x_1,x_2,\cdots ,x_k$，问有多少种方案，使得去掉恰好一个关键点使得剩余关键点在树 $A$ 上 lca 的权值大于树 $B$ 上 lca 的权值。$1\le k\le n\le 1\times 10^5$。

解法：由于 LCA 是可合并但没有逆的，因而对于这种挖去一个的情况，可以考虑维护序列的 lca 前缀和 $pr{e}_i$ 与 LCA 的后缀和 $su{f}_i$。对于挖去 $j$ 的情况就是 $\mathrm{lca}(pr{e}_{j-1},su{f}_{j+1})$。时间复杂度 $\mathcal{O}(n\log n)$。

#pragma GCC optimize(3)
#include
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
struct hh{
	int to,nxt;
};
int n,k,nd[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
struct tree{
	hh e[N<<1];int num,fir[N],val[N],dep[N],fa[N][20],lf[N],rf[N];
	IL void add(int x,int y){
		e[++num]=(hh){y,fir[x]},fir[x]=num;
	}
	void dfs(int u,int f){
		dep[u]=dep[f]+1,fa[u][0]=f;
		for(int i=0;fa[u][i];++i)
		  fa[u][i+1]=fa[fa[u][i]][i];
		for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		  dfs(v,u);
	}
	IL int Lca(int x,int y){
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=18;~i;--i)
		  if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		if(x==y) return x;
		for(int i=18;~i;--i)
		  if(fa[x][i]^fa[y][i])
		    x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	IL void init(){
		lf[1]=nd[1];
		for(int i=2;i<=k;++i)
		  lf[i]=Lca(lf[i-1],nd[i]);
		rf[k]=nd[k];
		for(int i=k-1;i;--i)
		  rf[i]=Lca(rf[i+1],nd[i]);
	}
	IL int get(int n){
		if(n==1) return val[rf[2]];
		if(n==k) return val[lf[k-1]];
		return val[Lca(lf[n-1],rf[n+1])];
	}
}A,B;
void solve(){
	n=in(),k=in();int ans=0;
	for(int i=1;i<=k;++i) nd[i]=in();
	for(int i=1;i<=n;++i) A.val[i]=in();
	for(int i=2;i<=n;++i) A.add(in(),i);
	for(int i=1;i<=n;++i) B.val[i]=in();
	for(int i=2;i<=n;++i) B.add(in(),i);
	A.dfs(1,0),B.dfs(1,0),A.init(),B.init();
	for(int i=1;i<=k;++i) ans+=(A.get(i)>B.get(i));
	printf("%d\n",ans);
}
int main()
{
	solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

B Boss

题意：$k$ 个城市有 $n$ 个人去上班，每个人选一个城市上班，第 $i$ 个城市需要 $e_i$ 个人去上班。第 $i$ 个人去第 $j$ 个城市上班的代价为 $c_{i,j}$，问最小化代价。$n\le 1\times 10^5$，$k\le 10$。

解法：如果不看范围，这题就是一个板子最小费用最大流——每个人向城市连边，流量为 $1$ 费用为 $c_{i,j}$；源点向每个人连边流量 $1$ 费用 $0$，第 $i$ 个城市向汇点连边流量 $e_i$ 费用 $0$。

但是此题边数达到了 $1\times 10^6$，点数 $1\times 10^5$，因而考虑模拟费用流的过程。注意到每次费用流的过程为：从源点找到汇点找一条最短路径，然后更新本条路径的流量，更新反向边的流量。而这题每次增广的流量必然为 $1$，因而这极大的限制了运行效率。

首先考虑做第一步的优化，将人初始分到一些城市去，优化第一步的 $n$ 次增广。一个简单的方法就是全部安排到 $1$ 号城市，利用 $\mathrm{now}$ 数组来记录第 $i$ 个人现在工作的城市。通过这一安排将源点到人所在的节点完全固定下来，节约了大量的无效增广。

接下来考虑人员的流动。显然从源点到人这一部分是不可能再去增广了，唯一能实现流的增广的就是让人从一个城市到另一个城市上班——因为此时 $1$ 号城市负载量过大，别的城市需要从 $1$ 号城市挖人。这样的好处是将原本人与城市之间复杂的边关系转化成了城市与城市之间的关系，由于 $k$ 非常小因而这降低了大量的复杂度。

那么依次考虑可能的增广操作——第 $i,i\in [2,k]$ 个城市需要进行 $e_i$ 次增广。对于这每一轮的增广，按照费用流的思想就是找到从源点到汇点的最短路，但是显然从源点到人、从城市到汇点这两部分对最短路是无意义的，因而考虑城市到城市之间的转移。对于每一对城市 $(u,v)$，用一个堆记录之间所有可能的边——对于每个人 $i$，若其原定城市为 $u$，则 $(u,v)$ 之间有一条距离为 $c_{i,v}-c_{i,u}$ 的边，这个边代表了第 $i$ 个人的跳槽选择。表示这个人从 $u$ 城市换到了 $v$ 城市所改变的代价。因而暴力使用 spfa 来找到一条从 $1$ 到 $i$ 的路径。在松弛的时候只需要找到每一对城市中边权最小的一条边即可，使用优先队列维护。

注意：整个过程可以认为是 $1$ 号城市源源不断的给别的城市输送人，虽然其他城市之间也会互相换，但是这个换的意义是利用网络流中反悔边。所以源头一直都是 $1$。

找到最短路径之后就是费用流正常的操作——退流反向。这里的反向操作由于是在城市之间进行的，其意义是人在不同城市之间流动。例如对于一次增广中找到的路径 $u\to v$，若其边代表的人是 $i$，则意义是第 $i$ 个人从第 $u$ 个城市前往了 $v$ 城市进行工作，因而更改 $\mathrm{now}$ 数组。同时由于 $i$ 的跳槽，他也有了新的 $k-1$ 个跳槽选择，因而需要增设连向其他城市的 $k-1$ 条边。

#include 
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
using pli = pair<long long, int>;
priority_queue<pli, vector<pli>, greater<pli>> q[15][15];
//q[i][j] 内存储了边，这些边代表一个人的跳槽选择，以代价差为第一关键字，第二关键字仅用于表示人编号。
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> now(n + 1, 1), e(k + 1);//now[i]表示第i个人目前工作的城市
    for (int i = 1; i <= k;i++)
        scanf("%d", &e[i]);
    vector<vector<long long>> c(n + 1, vector<long long>(k + 1));
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= k;j++)
            scanf("%lld", &c[i][j]);
    long long ans = 0;
    for (int i = 1; i <= n;i++)
    {
        ans += c[i][1];
        for (int j = 2; j <= k;j++)
            q[1][j].emplace(c[i][j] - c[i][1], i);
    }
    queue<int> que;
    for (int i = 2; i <= k;i++)
        for (int times = 1; times <= e[i];times++)
        {
            vector<long long> dis(k + 1, inf);
            que.push(1);
            vector<int> pre(k + 1, 0), vis(k + 1, 0);
            vis[1] = 1;
            dis[1] = 0;
            while(!que.empty())
            {
                int tp = que.front();
                que.pop();
                vis[tp] = 0;
                for (int j = 2; j <= k;j++)
                {
                    while(!q[tp][j].empty() && now[q[tp][j].top().second] != tp)//当前人已经不在tp城市工作了，因而这条边废弃
                        q[tp][j].pop();
                    if (!q[tp][j].empty() && dis[j] > dis[tp] + q[tp][j].top().first)
                    {
                        dis[j] = dis[tp] + q[tp][j].top().first;
                        pre[j] = tp;
                        if(!vis[j])
                        {
                            vis[j] = 1;
                            que.push(j);
                        }
                    }
                }
            }
            ans += dis[i];
            int place = i;
            while(place != 1)
            {
                int fa = pre[place];
                int ori_id = q[fa][place].top().second;
                now[ori_id] = place;//退流表现为人工作城市的变化
                for (int i = 1; i <= k;i++)
                    if (i != place)//增设新的跳槽选择
                        q[place][i].emplace(c[ori_id][i] - c[ori_id][place], ori_id);
                place = fa;
            }
        }
    printf("%lld", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

C Concatenation

题意：给定 $n$ 个仅由 0、1、2、3、4构成的字符串，问 $n!$ 种排列中字典序最小的那一个。$n\le 2\times 10^6$，$\sum |s_i|\le 2\times 10^7$。

解法：本题暴力使用 sort可以通过，排序规则为 $a+b<b+a$，其中 $a,b$ 均为字符串。

考虑如何 $\mathcal{O}(n)$ 的实现。首先将全部串插入 Trie 树，不妨设 $|a|<|b|$，对于 $a+b<b+a$，如果 $a$ 不是 $b$ 的前缀，则可以根据 $a$ 和 $b$ 在 Trie 树上的 dfs 序大小来判断。

若 $a$ 是 $b$ 的前缀，则需要比较依次比较 $b_{|a|+j}$ 与 $b_j$ 的大小关系。这个可以通过对每个串进行一次 Z 函数得到每个串后缀和原串的 $\mathrm{lcp}$ 长度，从而实现 $\mathcal{O}(1)$ 的比较。因而一个前缀的比较等效于对应的未匹配后缀。由于 $b$ 的前缀个数仅 $\mathcal{O}(|b|)$ 个的，因而对这些前缀排序仅需 $\mathcal{O}(|b|)$ 的时间。

D Directed

题意：给定一个 $n$ 个点以 $1$ 为根的树，现在要从 $s$ 出发到 $1$ 号节点。现在随机选择 $k$ 条树边变成单向边，方向由儿子指向父亲。同时人在某一个节点以等概率选择出边，问期望多少步走到 $1$ 号节点。

解法：对于一个有根树，从儿子节点 $v$ 走到父节点 $u$，其期望步数为 $E_v=2si{z}_v-1$，其中 $si{z}_v$ 表示 $v$ 的子树大小。

首先对于叶子节点 $v$，$E_v=2si{z}_v-1$ 显然成立；考虑非叶子节点 $v$，其孩子个数为 $c$，则有 $E_v=1+\sum _{i\in C}\frac{E_i+E_v}{c+1}$ 可得 $E_v=2si{z}_v-1$。

由此，如果没有改为单向边的操作，考虑从 $s$ 到 $1$ 的期望步数，即是从 $s$ 一步一步走到其祖先直到 $1$ 的期望步数之和。记从 $s$ 到 $1$ 的路径为特殊路径 $l$：$s\to v_1\to v_2\to \cdots \to 1$，基础答案为 $\sum _{v\in l,v\ne 1}2si{z}_v-1$。

考虑有单向边的情况。如果一条边 $(u,v)$ （不妨令 $u$ 是 $v$ 的祖先）作为单向边，那么其祖先的子树大小会受到影响（等效于从祖先视角看，$u$ 这个子树被删除了），$v$ 的子树都不会受到影响。进一步的，由于统计的期望步数仅由 $l$ 上的子树和决定，因而影响区间为 $u$ 在 $l$ 上的最近祖先至 $1$ 的这一条 $l$ 上的链。

考虑两种情况：

1. $(u,v)$ 为 $l$ 上的链。如果当前边不选，则对步数的贡献会减少 $2si{z}_u$——向上的一步还是要计入。考虑从 $u$ 开始到 $1$ 的每一步的期望贡献：对于 $u$ 的一级祖先 $a_1$，$u\to a_1$ 的期望步数要减少 $2si{z}_u$，对于任何情况均成立，仅需要满足 $v\to u$ 被选定，概率为 $P_1=\left(\genfrac{}{}{0ex}{}{n-1-1}{k-1}\right)$；对于 $u$ 的二级祖先 $a_2$，$a_1\to a_2$ 的期望步数要减少 $2si{z}_u$ 而非 $2si{z}_{a_1}$，需要 $u\to a_1$ 不是单向边，否则从 $a_2$ 上升到 $a_3$ 时，贡献为 $2si{z}_{a_1}$ 而不是 $2si{z}_u$，因而可选择范围为 $P_2=\left(\genfrac{}{}{0ex}{}{n-1-2}{k-1}\right)$——$v\to u$ 选定，且 $u\to a_1$ 必不选；三级祖先需要满足 $u\to a_1$ 和 $a_1\to a_2$ 均不是单向边，因而概率为 $P_3=\left(\genfrac{}{}{0ex}{}{n-1-3}{k-1}\right)$；因而，若 $u$ 到 $1$ 的路径长度为 $de{p}_u$，则总的概率为 $\sum _{i=1}^{de{p}_u-1}{P}_i$，对答案的贡献需要减去 $2si{z}_u\sum _{i=1}^{de{p}_u-1}{P}_i$。
2. $(u,v)$ 不是 $l$ 上的链。记 $u$ 到链 $l$ 上的最近祖先为 $a$，则$si{z}_u$ 的贡献能被直接记录在 $l$ 上而非 $u$ 到 $a$ 的其他祖先上的概率为 $u\to a$ 的路径上所有边都不允许是单向边。然后在 $l$ 上从 $a$ 到 $1$ 的分析和上面相同。因而其概率为 $\sum _{i=de{p}_a}^{de{p}_u}{P}_i$。

总时间复杂度仅为遍历复杂度，$\mathcal{O}(n)$。

（队友代码）

#include
#define IL inline
#define LL long long
using namespace std;
const int N=1e6+3,p=998244353;
struct hh{
	int to,nxt;
}e[N<<1];
int n,k,s,num,fir[N],fac[N],ifac[N],bo[N],siz[N],dep[N],P[N],fa[N],bel[N],pp,ans;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL void add(int x,int y){e[++num]=(hh){y,fir[x]},fir[x]=num;}
IL int ksm(int a,int b){
	int c=1;
	while(b){
		if(b&1) c=1ll*c*a%p;
		a=1ll*a*a%p,b>>=1;
	}
	return c;
}
void init(){
	fac[0]=1;for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p;
	ifac[n]=ksm(fac[n],p-2);
	for(int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%p;
}
IL int C(int n,int m){if(n<m) return 0;return 1ll*fac[n]*ifac[m]%p*ifac[n-m]%p;}
void dfs1(int u,int f){
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) dfs1(v,u),siz[u]+=siz[v];
}
void dfs2(int u,int bl){
	bel[u]=bl;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^fa[u]){
	  	if(bo[v]) dfs2(v,v);
	  	else dfs2(v,bl);
	  }
}
int main()
{
	int x,y;
	n=in(),k=in(),s=in(),init();
	for(int i=1;i<n;++i)
	  x=in(),y=in(),add(x,y),add(y,x);
	dfs1(1,0);
	bo[s]=1;while(s!=1) bo[s=fa[s]]=1;
	dfs2(1,1);
	pp=ksm(C(n-1,k),p-2);
	for(int i=1;i<n;++i) P[i]=1ll*C(n-1-i,k-1)*pp%p,P[i]=mod(P[i-1]+P[i]);
	for(int i=2;i<=n;++i) if(bo[i]) ans=mod(ans+mod(2*siz[i]-1));
	for(int i=2;i<=n;++i)
	  if(dep[i]>2){
		  if(bo[i]) ans=mod(ans-1ll*P[dep[i]-2]*mod(2*siz[i])%p+p);
		  else ans=mod(ans+p-1ll*mod(P[dep[i]-2]-P[dep[i]-dep[bel[i]]-1]+p)*mod(2*siz[i])%p);
	  }
	printf("%d\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

F Fief

题意：有一个 $n$ 个点 $m$ 条边的无向图 $G$，$q$ 次询问，每次询问给定 $x_i,y_i$，表示一个长度为 $n$ 的排列的第一项和最后一项，问是否能找到一个长度为 $n$ 且首尾项为 $x_i$ 和 $y_i$ 的排列，使得 $\forall i\in [1,n-1]$，排列的前 $i$ 项构成的子图和后 $n-i$ 项均联通。$n,q\le 1\times 10^5$，$m\le 2\times 10^5$。

解法：考虑以割点进行缩图。

首先考虑几种特殊情况：

1. 原图仅两个点，必然成立。
2. 原图无割点，即全图为点双连通，则必然成立。
3. 原图不连通，必然不成立。

对于一个朴素的连通且具有割点的图，缩完点后的图 $G^{\prime }$ 必然为一条链——若 $G^{\prime }$ 上存在一度数大于等于 $3$ 的节点，记为 $u$，从 $u$ 割出的某一连通分量出发，必然在随着排列的前 $i$ 项数量从小到大的扩张过程中扩张到 $u$，且后续还要继续扩张。而一旦扩张到 $u$，后 $n-i$ 项不连通。

进一步的，考虑 $x_i$ 和 $y_i$ 在 $G^{\prime }$ 上的位置——若不是分属链的两端点，必然不成立——假设 $x_i$ 不在端点，则 $y_i$ 必然会因为 $x_i$ 的阻断导致不能和两个链端点同时连通，对于 $i=2$ 的情况就失败了。

代码来源于队友。

#pragma GCC optimize(3)
#include
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+3;
struct hh{
	int to,nxt;
}e[N<<1];
int n,m,q,num,col,tp,sta[N],fir[N],dfn[N],low[N],val[N];
vector<int>e1[N],e2[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void add(int x,int y){e[++num]=(hh){y,fir[x]},fir[x]=num;}
void tarjan(int u){
	dfn[u]=low[u]=++num,sta[++tp]=u;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(!dfn[v]){
	  	tarjan(v),low[u]=min(low[u],low[v]);
	  	if(dfn[u]<=low[v]){
	  		++col;
	  		while(sta[tp+1]!=v)
	  		  e1[sta[tp]].pb(col),
	  		  e2[col].pb(sta[tp--]);
	  		e1[u].pb(col),e2[col].pb(u);
	  	}
	  }
	  else low[u]=min(low[u],dfn[v]);
}
IL void print(int op){for(int i=1;i<=q;++i) puts(op?"YES":"NO");exit(0);}
int main()
{
	int x,y,z;
	n=in(),m=in();
	for(int i=1;i<=m;++i)
	  x=in(),y=in(),add(x,y),add(y,x);
	q=in(),num=0,tarjan(1),num=0;
	if(n==2) print(1);
	for(int i=1;i<=n;++i)
	  if(!dfn[i]||e1[i].size()>2) print(0);
	if(col==1) print(1);
	for(int i=1;i<=col;++i){
		int deg=0;
		for(int j=0;j<e2[i].size();++j)
		  deg+=e1[e2[i][j]].size()-1;
		if(deg>2) print(0);
		if(deg==1){
			++num;
			for(int j=0;j<e2[i].size();++j)
			  if(e1[e2[i][j]].size()==1) val[e2[i][j]]=num;
		}
	}
	while(q--) puts(val[in()]+val[in()]^3?"NO":"YES");
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

G Geometry

题意：给定两个 $n$ 个点和 $m$ 个点的凸包和运动方向，问是否会发生碰撞，何时发生碰撞。$3\le n,m\le 5\times 10^4$。

解法：两个多边形速度为 $\overrightarrow{v_1},\overrightarrow{v_2}$ 等效于一个凸包以速度 $\overrightarrow{v_2}-\overrightarrow{v_1}$ 运动。那么问题就转化为了两个凸包的闵氏和与射线 $(0,0)\to \overrightarrow{v_2}-\overrightarrow{v_1}$ 有无交点，最近交点在哪里。此题与 https://www.luogu.com.cn/problem/P4557 很像。

I Ice Drinking

题意：给定 $n$，记随机变量 $X$ 为一个长度为 $n$ 的排列中满足 $a_i=i$ 的个数，求所有排列中 $E(X^k)$。$1\le n\le 1\times 10^{18}$，$0\le k\le n+5000$。

解法：由错排定义可得 $n!=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)D_{n-i}$。
E ( X k ) = ∑ i = 0 n i k Pr ⁡ [ x = i ] = ∑ i = 0 n i k ( n i ) D n − i = ∑ i = 0 n D n − i ( n i ) ∑ j = 0 k j ! ( i j ) { k j } = ∑ i = 0 n ∑ j = 0 k ( n i ) ( i j ) j ! { k j } D n − i = ∑ i = 0 n ∑ j = 0 k ( n j ) ( n − j i − j ) j ! { k j } D n − i = ∑ j = 0 k ( n j ) { k j } j ! ( ∑ i = j n ( n − j i − j ) D n − i ) = ∑ j = 0 k ( n j ) { k j } j ! ( ∑ i = 0 n − j ( n − j i ) D n − i − j ) = ∑ j = 0 k ( n j ) { k j } j ! ( n − j ) ! = ∑ j = 0 k n ! j ! ( n − j ) ! { k j } j ! ( n − j ) ! = n ! ∑ j = 0 n { k j }

E(Xk)==========​i=0∑n​ikPr[x=i]i=0∑n​ik(in​)Dn−i​i=0∑n​Dn−i​(in​)j=0∑k​j!(ji​){jk​}i=0∑n​j=0∑k​(in​)(ji​)j!{jk​}Dn−i​i=0∑n​j=0∑k​(jn​)(i−jn−j​)j!{jk​}Dn−i​j=0∑k​(jn​){jk​}j!(i=j∑n​(i−jn−j​)Dn−i​)j=0∑k​(jn​){jk​}j!(i=0∑n−j​(in−j​)Dn−i−j​)j=0∑k​(jn​){jk​}j!(n−j)!j=0∑k​j!(n−j)!n!​{jk​}j!(n−j)!n!j=0∑n​{jk​}​
因而对于 $n\ge k$，答案为贝尔数 ${\varpi }_n=\sum _{i=0}^k\left\{\genfrac{}{}{0ex}{}{k}{i}\right\}$；对于 $n<k$，需要手动计算出最后几项斯特灵数，然后进行相减。

求贝尔数对 $p$ 取模，可以参考本文https://www.cnblogs.com/lfri/p/11546313.html：利用 ${\varpi }_{n+p}\equiv {\varpi }_n+{\varpi }_{(n+1)}(\mathrm{mod}p)$，$p$ 是质数，其时间复杂度为 $\mathcal{O}(p^2\log n)$。

对于斯特灵数的快速计算，对于本题 $k-n\le 5\times 10^3$，可以采用二阶欧拉数 ⟨ ⟨ n k ⟩ ⟩ \left\langle \left\langle

nk" role="presentation" style="position: relative;">nk$$\begin{array}{c}n\\ k\end{array}$$

\right\rangle \right\rangle ⟨⟨nk​⟩⟩：
{ x x − n } = ∑ k = 0 n ⟨ ⟨ n k ⟩ ⟩ ( x + n − 1 − k 2 n ) {x \brace x-n}=\sum_{k=0}^n \left\langle \left\langle

nk" role="presentation" style="position: relative;">nk$$\begin{array}{c}n\\ k\end{array}$$

\right\rangle \right\rangle {x+n-1-k \choose 2n} {x−nx​}=k=0∑n​⟨⟨nk​⟩⟩(2nx+n−1−k​)
其中二阶欧拉数递推式为 ⟨ ⟨ n k ⟩ ⟩ = ( k + 1 ) ⟨ ⟨ n − 1 k ⟩ ⟩ + ( 2 n − 1 − k ) ⟨ ⟨ n − 1 k − 1 ⟩ ⟩ \left\langle \left\langle

nk" role="presentation" style="position: relative;">nk$$\begin{array}{c}n\\ k\end{array}$$

\right\rangle \right\rangle=(k+1)\left\langle \left\langle

n−1k" role="presentation" style="position: relative;">n−1k$$\begin{array}{c}n-1\\ k\end{array}$$

\right\rangle \right\rangle+(2n-1-k)\left\langle \left\langle

n−1k−1" role="presentation" style="position: relative;">n−1k−1$$\begin{array}{c}n-1\\ k-1\end{array}$$

\right\rangle \right\rangle ⟨⟨nk​⟩⟩=(k+1)⟨⟨n−1k​⟩⟩+(2n−1−k)⟨⟨n−1k−1​⟩⟩。该时间复杂度为 $\mathcal{O}((k-n{)}^2)$。

此外还有一个做法，来源于 hos.lyric：
{ n k }   m o d   p = { ( x y )   m o d   p , i f   p ∣ k , y ← k p , x ← ⌊ n − y p − 1 ⌋ ( x y ) { n − 1 − ( p − 1 ) x − y k }   m o d   p , i f   p ∤ k , y ← ⌊ k p ⌋ , x ← ⌊ n − y − 1 p − 1 ⌋ {n \brace k} \bmod p=

{kn​}modp=⎩ ⎨ ⎧​(yx​)modp,if p∣k,y←pk​,x←⌊p−1n−y​⌋(yx​){kn−1−(p−1)x−y​}modp,if p∤k,y←⌊pk​⌋,x←⌊p−1n−y−1​⌋​
具体证明可以参看http://matwbn.icm.edu.pl/ksiazki/aa/aa94/aa9413.pdf。

hos 对此的解释为：

I just guessed the pattern by looking the table for $p=7$. We can prove that Stirling1 mod p has a nice pattern because $x(x-1)...(x-(p-1))\equiv x^p-x(\mathrm{mod}p)$, and since Stirling2 is its inverse matrix, my intuition says it is correct.

如果提前预处理好 $p^2$ 的斯特灵数表和组合数表，利用 Lucas 定理可以 $\mathcal{O}(\log n)$ 的求出。

由于本题的模数 $862118861=857\times 997\times 1009$，因而可以通过中国剩余定理，对于每个质因子单独考虑，然后合并。最终复杂度为 $\mathcal{O}(p^2\log n+(k-n{)}^2)$。

#include 
using namespace std;
const int P = 862118861;
const int mod[3] = {857, 997, 1009};
class Bell
{
    const static int N = 1100;
    vector<vector<int>> Stirling;
    vector<int> bell;
    int mod;

public:
    Bell(int mod)
    {
        bell.resize(N + 5);
        Stirling.resize(N + 5);
        for (auto &i : Stirling)
            i.resize(N + 5);
        this->mod = mod;
        Stirling[0][0] = 1;
        for (int i = 0; i <= N; i++)
            for (int j = 1; j <= i; j++)
                Stirling[i][j] = (Stirling[i - 1][j - 1] + 1LL * j * Stirling[i - 1][j]) % mod;
        bell[0] = 1;
        for (int j = 1; j <= N; j++)
        {
            bell[j] = 0;
            for (int k = 1; k <= j; k++)
                bell[j] = (bell[j] + Stirling[j][k]) % mod;
        }
    }
    int query(long long n)
    {
        if(n < mod)
            return bell[n];
        vector<int> B(N + 5, 0), a(N + 5, 0), d(N + 5, 0);
        for (int i = 0; i <= mod;i++)
            B[i] = bell[i];
        int cnt = 0;
        while (n)
        {
            a[cnt++] = n % mod;
            n /= mod;
        }
        for (int i = 1; i < cnt; i++)
            for (int j = 1; j <= a[i]; j++)
            {
                for (int k = 0; k < mod; k++)
                    d[k] = (B[k + 1] + i * B[k] % mod) % mod;
                d[mod] = (d[0] + d[1]) % mod;
                for (int k = 0; k <= mod; k++)
                    B[k] = d[k];
            }
        return d[a[0]];
    }
};
class Binom
{
    int mod;
    const static int N = 1100;
    vector<vector<int>> C;

public:
    void set(int mod)
    {
        C.resize(N + 5);
        for (auto &i : C)
            i.resize(N + 5);
        this->mod = mod;
        for (int i = 0; i <= N;i++)
            C[i][i] = C[i][0] = 1;
        for (int i = 1; i <= N;i++)
            for (int j = 1; j < i;j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    long long query(long long n, long long m)
    {
        if(n < mod && m < mod)
            return C[n][m];
        else
            return C[n % mod][m % mod] * query(n / mod, m / mod) % mod;
    }
};
class Euler
{
    const static int N = 5000;
    vector<vector<int>> euler;
    int mod;
    Binom b;

public:
    Euler(int mod)
    {
        euler.resize(N + 5);
        for (auto &i : euler)
            i.resize(N + 5);
        b.set(mod);
        this->mod = mod;
        euler[0][0] = 1;
        for (int i = 1; i <= N;i++)
        {
            euler[i][0] = 1;
            euler[i][i] = 0;
        }
        for (int i = 2; i <= N;i++)
            for (int j = 1; j < i;j++)
                euler[i][j] = (euler[i - 1][j] * (j + 1) + (2 * i - 1 - j) * euler[i - 1][j - 1]) % mod;
    }
    long long query_stirling(long long x, int n)
    {
        long long ans = 0;
        for (int k = 0; k <= n;k++)
            ans = (ans + euler[n][k] * b.query(x + n - 1 - k, 2 * n) % mod) % mod;
        return ans;
    }
};
int main()
{
    long long n, m;
    scanf("%lld%lld", &n, &m);
    long long ans[3] = {0};
    for (int i = 0; i < 3;i++)
    {
        Bell solve(mod[i]);
        ans[i] = solve.query(m);
        // printf("SOLVE:%d %lld\n", mod[i], ans[i]);
    }
    if (n < m)
        for (int i = 0; i < 3;i++)
        {
            Euler solve(mod[i]);
            for (int j = 0; j < m - n;j++)
                ans[i] = (ans[i] - solve.query_stirling(m, j) + mod[i]) % mod[i];
        }
    long long res = (463753553LL * ans[0] + 376150155LL * ans[1] + 22215154LL * ans[2]) % P;
    printf("%lld", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

H Hacker

题意：给定长度为 $n$ 的模式串 $S$，和长度为 $m$ 的权值数组 { w i } \{w_i\} {wi​}。对于一个长度为 $m$ 的串，$w_i$ 表示使用该串上第 $i$ 个字符与 $S$ 匹配可以获得 $w_i$ 的权值。$k$ 次询问一个长度为 $m$ 的串 $T$ 与 $S$ 的最大权值公共子串。$n,m,k\le 1\times 10^5,mq\le 1\times 10^6$。

解法：对 $S$ 建立 SAM，然后对于每次询问都可以将 $T$ 串拉上去跑，对于 $T$ 串，每匹配一个字符，就可以通过 SAM 知道当前匹配了多长的字符串。因而问题转化成为了对于每个右端点 $r$，有一个左边界 $l$，然后问处于某个区间的最大连续子段和。维护 $w$ 的前缀和，利用区间查询最小值的线段树即可通过。复杂度 $\mathcal{O}(n+n\log n)$。

#include 
using namespace std;
long long inf = 0x3f3f3f3f3f3f3f3fll;
class segment_tree
{
    int n;
    vector<long long> minimum;
    long long query(int place, int left, int right, int start, int end)
    {
        if (start <= left && right <= end)
            return minimum[place];
        long long ans = inf;
        int mid = (left + right) >> 1;
        if (start <= mid)
            ans = min(ans, query(place << 1, left, mid, start, end));
        if (end > mid)
            ans = min(ans, query(place << 1 | 1, mid + 1, right, start, end));
        return ans;
    }

public:
    void set(int n, vector<long long> &w)
    {
        this->n = n;
        minimum.resize(4 * n + 10);
        function<void(int, int, int)> build = [&](int place, int left, int right)
        {
            if (left == right)
            {
                minimum[place] = w[left];
                return;
            }
            int mid = (left + right) >> 1;
            build(place << 1, left, mid);
            build(place << 1 | 1, mid + 1, right);
            minimum[place] = min(minimum[place << 1], minimum[place << 1 | 1]);
        };
        build(1, 0, n);
    }
    long long query(int l, int r)
    {
        return query(1, 0, n, l, r);
    }
} tr;
vector<long long> pre;
class SAM
{
    const int shift = 97;
    struct node
    {
        int ch[26];
        int len;
        int father;
        long long cnt;
        node()
        {
            memset(ch, 0, sizeof(ch));
            len = father = cnt = 0;
        }
    } NIL;
    vector<node> t;
    int last, ind;
    void insert(int c)
    {
        int p = last;
        int np = last = ++ind;
        t.push_back(NIL);
        t[np].len = t[p].len + 1;
        t[np].cnt = 1;
        for (; p && !t[p].ch[c]; p = t[p].father)
            t[p].ch[c] = np;
        if(!p)
            t[np].father = 1;
        else
        {
            int q = t[p].ch[c];
            if (t[p].len + 1 == t[q].len)
                t[np].father = q;
            else
            {
                int nq = ++ind;
                t.push_back(t[q]);
                t[nq].cnt = 0;
                t[nq].len = t[p].len + 1;
                t[q].father = t[np].father = nq;
                for (; p && t[p].ch[c] == q; p = t[p].father)
                    t[p].ch[c] = nq;
            }
        }
    }
 
public:
    SAM(string s)
    {
        last = ind = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        for (auto i : s)
            insert(i - shift);
    }
    long long query(string &s)
    {
        int place = 1, len = 0, n = s.length();
        long long ans = 0;
        for (int i = 0; i < n;i++)
        {
            while (place > 1 && !t[place].ch[s[i] - shift])
            {
                place = t[place].father;
                len = t[place].len;
            }
            if (!t[place].ch[s[i] - shift])
                continue;
            place = t[place].ch[s[i] - shift];
            len++;
            ans = max(ans, pre[i + 1] - tr.query(i + 1 - len, i + 1));
        }
        return ans;
    }
};
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, k;
    long long x;
    cin >> n >> m >> k;
    pre.resize(m + 1);
    string s, t;
    cin >> s;
    SAM solve(s);
    for (int i = 1; i <= m;i++)
    {
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    tr.set(n, pre);
    for (int i = 1; i <= k;i++)
    {
        cin >> t;
        cout << solve.query(t) << "\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

J Journey

题意：有 $n$ 个十字路口，左转、掉头、直行都要等红灯，右转不用。这些十字路口相互连接成一个图，问从某个十字路口的某个方向开始到目的地的目标方向需要等几次红绿灯。$n\le 5\times 10^5$。

解法：对于每个方向的道路看作一个点，边权为道路与道路之间的路口是否要等红绿灯，那么问题转化为边权仅有 $0,1$ 的图的单源最短路问题，01 bfs 或者 Dijkstra 即可。复杂度 $\mathcal{O}(n\log n)$ 或 $\mathcal{O}(n)$。

#pragma GCC optimize(3)
#include
#define IL inline
#define LL long long
using namespace std;
const int N=5e5+3;
struct hh{
	int to,nxt,w;
}e[N<<4];
struct kk{
	int x,y;
}S,T;
int n,c[N][4],dis[N][4];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL kk turn(int x,int y){
	int pos=0;
	for(int i=1;i<4;++i)
	  if(c[x][i]==y) pos=i;
	return (kk){x,pos};
}
deque<kk>q;
void bfs(){
	q.push_front(S);dis[S.x][S.y]=0;
	while(q.size()){
		kk u=q.front();q.pop_front();
		kk v=turn(c[u.x][u.y],u.x);
		int op=(v.y+1)%4;
		if(c[v.x][op]&&dis[v.x][op]>dis[u.x][u.y]){
			dis[v.x][op]=dis[u.x][u.y];
			q.push_front((kk){v.x,op});
		}
		for(int i=0;i<4;++i)
		  if(i^op&&c[v.x][i]&&dis[v.x][i]>dis[u.x][u.y]+1){
		  	dis[v.x][i]=dis[u.x][u.y]+1;
		  	q.push_back((kk){v.x,i});
		  }
	}
	if(dis[T.x][T.y]>1e9) printf("-1\n");
	else printf("%d\n",dis[T.x][T.y]);
}

void solve(){
	n=in();memset(dis,63,sizeof(dis));
	for(int i=1;i<=n;++i)
		for(int j=0;j<4;++j)
			c[i][j]=in();
	int x=in(),y=in();S=turn(x,y);
	x=in(),y=in();T=turn(x,y);
	bfs();
}
int main()
{
	solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63