2020-2021:teams:legal_string:jxm2001:contest:cf_664_div._2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_664_div._2 [2020/08/14 16:49]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_664_div._2 [2020/08/14 17:06] (当前版本)
jxm2001
@@ 行 7: / 行 7: @@
 ==== 题意 ====
-给定一个 $n$ 个点 $m$ 条边的有向图，每个点度数不超过 $k$，每条边的权为 $1\sim m$ 且各不相同。
+给定一个 $n$ 个点 $m$ 条边的有向图，每个点出度 $\in [1,k]$，每条边的权为 $1\sim m$ 且各不相同。
-要求输出满足下列条件的 $k$ 元组 $(c_1,c_2\cdots c_k)$ 的数目。
+要求输出满足下列条件的 $k$ 元组 $(c_1,c_2\cdots c_k)$ 的数目：
+  - $1\le c_i\le i$
+  - 如果一个点的出度为 $i$，则沿他的出边中边权第 $c_i$ 大的边走向下一个顶点。需要保证每个点能在有限步内回到起点。
 ==== 题解 ====
+对某个 $k$ 元组 $(c_1,c_2\cdots c_k)$，记 $f(u)$ 表示 $u$ 沿上述规则走到的下一个点。
+则 $(c_1,c_2\cdots c_k)$ 满足条件当且仅当 $f$ 为 $1\sim n$ 的置换。
+记出度为 $i$ 的点集沿他的出边中边权第 $j$ 大的边到达的点集，记为 $S_{i,j}$。
+则 $f$ 为 $1\sim n$ 的置换当且仅当 $\bigcup_{i=1}^k S_{i,c_i}=\{1,2\cdots n\}$。
+考虑哈希预处理 $S_{i,j}$，则可以 $O(k)$ 时间求出 $\bigcup_{i=1}^k S_{i,c_i}$。
+于是暴力枚举所有可能情况即可，时间复杂度 $O(n+m+k!)$。
 <hidden 查看代码>
 <code cpp>
+const int mod[3]={998244353,1004535809,1<<30},MAXN=2e5+5,MAXK=10,Base=32767;
+struct Hash_num{
+	int h[3];
+	Hash_num(LL seed=0){_for(i,0,3)h[i]=seed%mod[i];}
+	Hash_num operator + (const Hash_num &b)const{
+		Hash_num c;
+		c.h[0]=(h[0]+b.h[0])%mod[0];
+		c.h[1]=1LL*h[1]*b.h[1]%mod[1];
+		c.h[2]=h[2]^b.h[2];
+		return c;
+	}
+	void operator += (const Hash_num &b){
+		h[0]=(h[0]+b.h[0])%mod[0];
+		h[1]=1LL*h[1]*b.h[1]%mod[1];
+		h[2]=h[2]^b.h[2];
+	}
+	bool operator == (const Hash_num &b)const{
+		_for(i,0,3)if(h[i]!=b.h[i])return false;
+		return true;
+	}
+};
+Hash_num a[MAXN],s[MAXK][MAXK],t;
+LL get_rand(){return 1LL*rand()*Base*Base+1LL*rand()*Base+rand();}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int deg[MAXN],head[MAXN],edge_cnt,k,ans;
+pair<int,int> temp[MAXN];
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+void dfs(int pos,Hash_num cur){
+	if(pos>k){
+		if(cur==t)ans++;
+		return;
+	}
+	_rep(i,1,pos)
+	dfs(pos+1,cur+s[pos][i]);
+}
+int main()
+{
+	srand(time(NULL));
+	int n=read_int(),m=read_int(),u,v,w;
+	k=read_int();
+	_rep(i,1,m){
+		u=read_int(),v=read_int(),w=read_int();
+		temp[w]=make_pair(u,v);
+		deg[u]++;
+	}
+	for(int i=m;i;i--)
+	Insert(temp[i].first,temp[i].second);
+	_rep(i,1,n)a[i]=Hash_num(get_rand()),t+=a[i];
+	_rep(u,1,n){
+		for(int i=head[u],j=1;i;i=edge[i].next,j++){
+			int v=edge[i].to;
+			s[deg[u]][j]+=a[v];
+		}
+	}
+	dfs(1,Hash_num());
+	enter(ans);
+	return 0;
+}
 </code>
 </hidden>

2020-2021/teams/legal_string/jxm2001/contest/cf_664_div._2.1597394983.txt.gz · 最后更改: 2020/08/14 16:49 由 jxm2001