#2043. 匹配计数

    ID: 2043 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest763来源:qoj.ac数据:公开样例组合数学

匹配计数

匹配计数

题目描述

标题: 匹配计数 - Problem - QOJ.ac

#4921. 匹配计数

Statistics

The problem was used in the following contests:

题目描述

给定正整数 n 以及正整数序列 a1,a2,⋯,an,其中 ai 表示第 i 个点的颜色。求同时满足如下条件的大小为 n 的简单无向图 G 的个数:

  1. 边之间没有公共端点。即 G 是一匹配。
  2. 对于任一条边它的两个端点的颜色相同。
  3. 对两条不同的边 e1=(u1,v1)(u1<v1) 与 e2=(u2,v2)(u2<v2),若 u1<u2<v1<v2 或 u2<u1<v2<v1 则称 e1 与 e2 相交。满足 e1 与 e2 相交的无序对 (e1,e2) 有偶数个。

由于答案可能很大,对 998244353 取模。每个数据点有 T 组数据。

输入格式

第一行输入一个正整数 T。接下来紧跟着 T 组数据,两组数据之间会换一行。

每组数据的第一行是一个正整数 n,第二行 n 个正整数 a1,a2,⋯,an,两个正整数之间以一个空格隔开。

输出格式

T 行,每行一个非负整数表示答案。

样例输入

3
3
1 2 3
4
1 2 1 2
4
4 4 4 4

样例输出

1
3
9

样例解释

对于第一组数据,由于点的颜色互不相同,故不能连边,而不连边时交点数为 0,故答案为 1。

对于第二组数据,有 4 个匹配,其中 (1,3),(2,4) 全连的匹配的交点数为 1 不合法,故答案为 3。

对于第三组数据,连 0 条边或 1 条边都是合法的,而若连两条边则连 (1,3),(2,4) 是不合法的,故答案为 9。

数据范围

对于数据点 1∼2,n≤13。

对于数据点 3∼4,ai 是全部相同的。

对于数据点 5∼10,ai≤10。

对于数据点 11∼14,n≤300。

对于数据点 15∼20,n≤2000。

对 100% 的数据,1≤T≤5,1≤n≤2000,1≤ai≤n。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
3
1 2 3
4
1 2 1 2
4
4 4 4 4
1
3
9