#P17706. [2026年江苏省队集训]图

[2026年江苏省队集训]图

题目描述

有一张 nn 个点的完全图,点的编号从 11 到 nn。

你需要把图上的每条边染上一种颜色。颜色的数量没有限制,但你必须保证以下性质:

  • 对于任意三个点 x,y,zx,y,z,连接这三个点的三条边中至少有两条边颜色相同。

对于一个染色方案,定义其度数序列为 d1,d2,⋯ ,dnd_1,d_2,\cdots,d_n,其中 did_i 表示和 ii 相邻的边中不同颜色的种类数。

给定一个长度为 nn 的序列 aa,其中有些位置还未确定(用 ai=−1a_i=-1 表示)。求有多少种补全 aa 的方案,使得 aa 可能是某种染色方案对应的度数序列?

答案对 998244353998244353 取模。

输入格式

本题有多组测试数据。 输入的第一行一个整数 TT 表示测试数据组数。

对于每组测试数据:

  • 第一行一个正整数 nn;
  • 第二行 nn 个整数,表示 a1,⋯ ,ana_1,\cdots,a_n。

输出格式

对于每组数据,输出一行一个整数,表示答案对 998244353998244353 取模的结果。

样例输入

3
2
1 -1
3
-1 -1 -1
6
5 -1 -1 -1 -1 -1

样例输出

1
4
120

数据范围

设 ∑n\sum n 表示单个测试点内所有测试数据 nn 的和。

对于所有数据,2≤n≤1002\le n\le 100,∑n≤200\sum n\le 200。1≤ai≤n−11\le a_i\le n-1 或 ai=−1a_i=-1。

测试点编号 n≤n\le 特殊性质
1,21,2 33 无
3,43,4 66
5∼105\sim 10 100100 保证 ai≠−1a_i\neq -1
11∼2011\sim 20 无