CF1795D.Triangle Coloring
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an undirected graph consisting of n vertices and n edges, where n is divisible by 6 . Each edge has a weight, which is a positive (greater than zero) integer.
The graph has the following structure: it is split into 3n triples of vertices, the first triple consisting of vertices 1,2,3 , the second triple consisting of vertices 4,5,6 , and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.
You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly 2n red vertices and 2n blue vertices. The coloring is called valid if it meets these constraints.
The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.
Let W be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight W , and print it modulo 998244353 .
输入格式
The first line contains one integer n ( 6≤n≤3⋅105 , n is divisible by 6 ).
The second line contains n integers w1,w2,…,wn ( 1≤wi≤1000 ) — the weights of the edges. Edge 1 connects vertices 1 and 2 , edge 2 connects vertices 1 and 3 , edge 3 connects vertices 2 and 3 , edge 4 connects vertices 4 and 5 , edge 5 connects vertices 4 and 6 , edge 6 connects vertices 5 and 6 , and so on.
输出格式
Print one integer — the number of valid colorings with maximum possible weight, taken modulo 998244353 .
输入输出样例
输入#1
12 1 3 3 7 8 5 2 2 2 2 4 2
输出#1
36
输入#2
6 4 2 6 6 6 4
输出#2
2
说明/提示
The following picture describes the graph from the first example test.
The maximum possible weight of a valid coloring of this graph is 31 .