#P18605. Help Me to Get This Published
Help Me to Get This Published
Help Me to Get This Published
对一个n个顶点的完全图的每条边赋予一种颜色。如果不存在三条边颜色两两不同的三角形,就称它为Gallai着色。颜色的种类和名称没有预先限制。
顶点v的“颜色度”d(v),指与v相连的所有边一共使用了多少种不同颜色。整数序列(a1,...,an)被称为合法颜色度序列,当且仅当存在该完全图的一种Gallai着色,使每个带标号顶点i的颜色度恰为ai。
现在给出部分ai,其余位置用-1表示。请统计把这些-1替换为整数、最终得到合法颜色度序列的方法数,答案模998244353。
统计的是带标号的整数序列,不是着色方案。同一序列即使能被多种着色实现,也只计一次;未知位置填值不同就视为不同序列。
输入格式
第一行一个整数n,2<=n<=100。
第二行n个整数ai。每个ai为-1,或满足1<=ai<=n-1。-1表示该顶点颜色度未知。
输出格式
输出一个整数,表示合法填值方法数模998244353。
样例输入 1
2
1 -1
样例输出 1
1
样例输入 2
3
-1 -1 -1
样例输出 2
4
样例输入 3
6
5 -1 -1 -1 -1 -1
样例输出 3
120
样例说明
第一组只能填为(1,1)。第二组的四种合法序列是(1,1,1)、(1,2,2)、(2,1,2)、(2,2,1):第一种可用三条同色边,后三种可用两条同色边及一条其他颜色的边。