QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4921. 匹配计数

Statistics

题目描述

给定正整数 $n$ 以及正整数序列 $a_1,a_2,\cdots, a_n$,其中 $a_i$ 表示第 $i$ 个点的颜色。求同时满足如下条件的大小为 $n$ 的简单无向图 $G$ 的个数:

  1. 边之间没有公共端点。即 $G$ 是一匹配。
  2. 对于任一条边它的两个端点的颜色相同。
  3. 对两条不同的边 $e_1=(u_1,v_1) (u_1< v_1)$ 与 $e_2=(u_2,v_2) (u_2< v_2)$,若 $u_1< u_2< v_1< v_2$ 或 $u_2< u_1< v_2< v_1$ 则称 $e_1$ 与 $e_2$ 相交。满足 $e_1$ 与 $e_2$ 相交的无序对 $(e_1,e_2)$ 有偶数个。

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

输入格式

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

每组数据的第一行是一个正整数 $n$,第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$,两个正整数之间以一个空格隔开。

输出格式

$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\sim 2$,$n\le 13$。

对于数据点 $3\sim 4$,$a_i$ 是全部相同的。

对于数据点 $5\sim 10$,$a_i\le 10$。

对于数据点 $11\sim 14$,$n\le 300$。

对于数据点 $15\sim 20$,$n\le 2000$。

对 $100\%$ 的数据,$1\le T\le 5, 1\le n\le 2000, 1\le a_i\le n$。