OI - Fake Bullions(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Fake Bullions(Codeforces)

发表于 分类于 Valine：

我觉得这道题评到 3400 也不咋过分？

# 题面

> Linked 洛谷 CF804F

点击展开/折叠题面

给定一张 $n$ 个点的竞赛图,第 $i$ 个点上有 $S_i$ 个人,编号从 $0$ 到 $S_i-1$，其中的某一些人手上有真金条。

在时刻 $T$，如果从 $u$ 到 $v$ 有一条边，并且 $u$ 中第 $T\bmod\ S_u$ 个人手上有金条(无论真假)，并且 $v$ 中第 $T\bmod S_v$ 个人没有金条,那么 $v$ 中第 $T\bmod S_v$ 个人会获得一个假金条。

当所有人手上的金条数目不再变化时，他们开始卖出金条，真金条一定会卖出去，而假金条可能卖出去也可能卖不出去。

现在从卖出金条最多的 $A$ 个点中随机选择 $B$ 个,问可能选出的点集合有多少个。

# 解析

考虑存在从 $u$ 到 $v$ 的有向边，设 $t=(S_u,S_v)$，根据同余方程可以得到：若 $a\equiv b\pmod t$，则 $u$ 中 $a$ 的金条会传递给 $v$ 中的 $b$。

于是我们发现，一个强连通分量内，设强连通中所有点的 GCD 为 $t$，若其中存在一点的 $a$ 有金条，则最后强连通中每个点的 $b\equiv a\pmod t$ 都会有金条。

所以我们可以把一个强连通分量等价于一个 $S$ 为 $t$ 的点，即缩点。显然缩点过后仍然是一个竞赛图，不过变成了一个 DAG。

然后就可以想到拓扑进行转移，拓扑到的点向其指向的每个点做一次 $O(S)$ 的转移。这样每个点会向 $O(n)$ 个点转移，总共复杂度为 $O(n^2S)$。

对拓扑进行优化。对于是DAG的竞赛图，有结论“存在恰好一个点指向其他所有点”（因为是DAG，所以一定有无入度的点，因为是竞赛图，则该点出度为 $n-1$，即指向其他所有点）。

我们发现，设 $x,y,z$ 是拓扑序从先到后连续的 3 个点，会有转移 $x\to y,x\to z,y\to z$，而实际上我们可以通过 $y$ 把 $x$ 的金条转移给 $z$，两种转移等价，即 $x\to y\to z$。

所以一个点只需要转移给拓扑序的下一个点，优化到 $O(nS)$。

# 源代码

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
/*Lucky_Glass*/
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define upd(a,b) ((a)=(a)|(b))
#define cs const int &
const int N=5e3+10,M=2e6+10,MOD=1e9+7;

inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

bool debug;
int n,A,B,ndfn,nscc;
char str[M];
bool instk[N];
vector<bool> bag[N],fbag[N];
stack<int> stk;
int fac[N],ifac[N],siz[N],fsiz[N],dfn[N],low[N],scc[N],mn[N],mx[N],tbag[M],fcnt[N];

struct GRPAH{
	int head[N],to[N*N],nxt[N*N],ncnt;
	void AddEdge(cs u,cs v){
		ncnt++;
		nxt[ncnt]=head[u],to[ncnt]=v;
		head[u]=ncnt;
	}
	inline int operator [](cs u){return head[u];}
}Gr;

inline int Comb(cs a,cs b){return (a<0 || b<0 || a>b)? 0:Mul(fac[b],Mul(ifac[a],ifac[b-a]));}
void Init(){
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=Mul(fac[i-1],i);
	ifac[N-1]=Pow(fac[N-1],MOD-2);for(int i=N-2;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
}
void Input(){
	scanf("%d%d%d",&n,&A,&B);
	for(int i=1;i<=n;i++){
		scanf("%s",str+1);
		for(int j=1;j<=n;j++)
			if(str[j]=='1')
				Gr.AddEdge(i,j);
	}
	for(int i=1;i<=n;i++){
		scanf("%d%s",&siz[i],str);
		if(siz[1]==831484) debug=true;
		for(int j=0;j<siz[i];j++){
			bag[i].push_back(str[j]-'0');
			mn[i]+=str[j]-'0';
		}
	}
}
inline int GCD(cs a,cs b){return b? GCD(b,a%b):a;}
void Tarjan(cs u){
	dfn[u]=low[u]=++ndfn;
	instk[u]=true,stk.push(u);
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int tmp=0;nscc++;
		do{
			tmp=stk.top(),stk.pop();
			instk[tmp]=false;
			scc[tmp]=nscc;
			fsiz[nscc]=GCD(fsiz[nscc],siz[tmp]);
		}while(tmp!=u);
		fbag[nscc].resize(fsiz[nscc]);
	}
}
void PartGraph(){
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			Tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=0;j<siz[i];j++)
			upd(fbag[scc[i]][j%fsiz[scc[i]]],bag[i][j]);
	for(int i=nscc;i>1;i--){
		int tsiz=GCD(fsiz[i],fsiz[i-1]);
		int u=i,v=i-1;
		for(int j=0;j<tsiz;j++) tbag[j]=0;
		for(int j=0;j<fsiz[u];j++) upd(tbag[j%tsiz],fbag[u][j]);
		for(int j=0;j<fsiz[v];j++) upd(fbag[v][j],tbag[j%tsiz]);
	}
	for(int i=1;i<=nscc;i++)
		for(int j=0;j<fsiz[i];j++)
			fcnt[i]+=fbag[i][j];
	for(int i=1;i<=n;i++)
		mx[i]=siz[i]/fsiz[scc[i]]*fcnt[scc[i]];
}
int PartMath(){
	int ans=0;
	for(int i=1;i<=n;i++){
		int mus=0,may=0;
		for(int j=1;j<=n;j++){
			if(mx[i]<mn[j]) mus++;
			else if(mx[i]<mx[j] || (mx[i]==mx[j] && i<j)) may++;
		}
		if(mus>=A) continue;
		for(int j=min(B,min(A-1-mus,may));j+mus+1>=B;j--)
			ans=Add(ans,Mul(Comb(j,may),Comb(B-1-j,mus)));
	}
	return ans;
}
int main(){
	Init();
	Input();
	PartGraph();
	printf("%d\n",PartMath());
	return 0;
}

THE END

Thanks for reading!

> Linked 僕が死のうと思ったのは(曾经我也想过一了百了)-Bilibili