HBC210243TopoCounting题解

素流年 算法基础篇 75 0
想要成为编程高手?那就来试试全网最全C++题库,让您在练习中快速成长。
Now we start to describe a kind of directed graph called the Drying Rack Graph (DRG) with a parameter N. A DRG contains N groups of vertexes. The i-th group ViV^iVi contains 2N vertices: V1i,V2i,,V2

Now we start to describe a kind of directed graph called the Drying Rack Graph (DRG) with a parameter N. A DRG contains N groups of vertexes. The i-th group ViV^iVi contains 2N vertices: V1i,V2i,⋯ ,V2NiV^i_1, V^i_2, cdots, V^i_{2N}V1i​,V2i​,⋯,V2Ni​. There are two types of edges in DRG: intra-group edges (edges inside each group) and inter-group edges (edges between groups). Intra-Group Edge: For the i-th group, the following intra-group edges exist: (Vji,Vj+Ni)(V^i_j, V^i_{j+N})(Vji​,Vj+Ni​), for all integer j such that 1≤j≤N1 le j le N1≤j≤N;  (Vji,Vj+1i)(V^i_j, V^i_{j+1})(Vji​,Vj+1i​), for all integer j such that 1≤j≤N−11 le j le N-11≤j≤N−1 or N+1≤j≤2N−1N + 1 leq j le 2N-1N+1≤j≤2N−1. Inter-Group Edge: The following inter-group edges exist: (Vi+N1,V1i+1)(V^1_{i+N}, V^{i+1}_1)(Vi+N1​,V1i+1​), for all integer i such that 1≤i≤N−11 le i le N - 11≤i≤N−1; (Vi1,V1+Ni)(V^1_{i}, V^{i}_{1+N})(Vi1​,V1+Ni​), for all integer i such that 2≤i≤N2 le i le N2≤i≤N. Now we want to know the number of topo-order of a DRG parameterized with N. A topo-order of a directed graph G=(V, E) is a permutation vp1,vp2,⋯ ,vp∣V(G)∣v_{p_1}, v_{p_2}, cdots, v_{p_{|V(G)|}}vp1​​,vp2​​,⋯,vp∣V(G)∣​​ of all vertices from V(G) such that for all i < j, (vpj,vpi)∉E(G)(v_{p_j}, v_{p_i}) notin E(G)(vpj​​,vpi​​)​∈E(G) In order to avoid calculations of huge integers, report answer modulo a prime M instead.

HBC210243TopoCounting题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
想要在职场中立于不败之地?那就来试试全网最全C++题库,让您在练习中快速提升技能。

标签: HBC210243TopoCounting题解