1010. J. Rare Game

题目描述

给定一个长度为 (n) 的颜色序列 (a_1,a_2,\ldots,a_n)。

你可以在任意两个相邻位置之间放置隔板，也可以不放置任何隔板。隔板会将整个序列划分成若干个连续非空段。

如果一个段中每种出现过的颜色都恰好出现 (4) 次，则称这个段是罕见的。

求有多少种放置隔板的方案，使划分出的每一个段都是罕见的。两种方案只要存在一个位置放置隔板的情况不同，就认为它们不同。

答案对 (998244353) 取模。

样例解释

对于第二组数据，只有相邻两种颜色的分界处可能放置隔板，这两个位置可以分别选择放置或不放置，因此答案为 (4)。

对于第三组数据，必须在第四个数后放置隔板。

数据范围

• (1\le T\le10)；
• (1\le n\le5\times10^5)；
• (1\le a_i\le n)；
• 所有测试数据的 (n) 之和不超过 (10^6)。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 (n)；
• 第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)，表示颜色序列。

输出格式

对于每组测试数据，输出一行一个整数，表示合法方案数对 (998244353) 取模后的结果。

样例输入

3
4
1 1 1 1
12
1 1 1 1 3 3 3 3 2 2 2 2
8
1 1 1 1 1 1 1 1

样例输出

1
4
1

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1010