1005. 减数游戏 2

题目描述

河灵和胖胖龙正在玩「减数游戏」。游戏在一个长度为 n 的正整数序列 a1, …, an (1 ≤ ai ≤ n) 上进行，

这些数构成了一个可重集合 S。游戏开始时，河灵和胖胖龙的分数均为 0。河灵和胖胖龙轮流操作，河灵先手。每次操作需要在 1 ∼ min{S} 范围内选择一个正整数 x，然后将当前集合 S 中的所有数都减去 x，如果某些数在当前操作后变成了 0，那么这些数将会被立即移出集合 S。若本次操作中至少有一个数被移出集合 S，则对方玩家得一分。当集合 S 为空时，游戏结束。记最终河灵与胖胖龙的分数分别为

A, B。若 A ≥ B，则河灵获胜；否则胖胖龙获胜。现在，河灵获得了一个残缺的序列 a1, …, an (0 ≤ ai ≤ n)，其中某些

位置的值已知，满足 1 ≤ ai ≤ n；其余位置的值未知，用 ai = 0 表

示。对于每个满足 ai = 0 的未知位置，河灵都可以将 ai 替换成 1 ∼ n 中

的任意一个正整数。不同未知位置的替换相互独立。请你帮帮河灵，求出有多少种不同的替换方案，使得在河灵和胖胖龙都采取最优策略的前提下，最终河灵获胜。两种替换方案不同，当且仅当存在某个未知位置，在两种方案中的替换数值不同。答案对

998244353 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 5 × 105 )，表示数据组数。对于每组测试数据：

第一行一个正整数 n (1 ≤ n ≤ 105 )，表示序列 a 长度。第二行 n 个整数 a1, …, an (0 ≤ ai ≤ n)，表示残缺的序列 a。其中某

些位置的值已知，保证满足 1 ≤ ai ≤ n；其余位置的值未知，用

ai = 0 表示。

保证所有测试数据中 n 之和不超过 5 × 105。

输出格式

对于每组测试数据：输出一行一个整数，表示答案对 998244353 取模后的值。

样例输入

5
7
7 4 1 3 5 4 1
11
8 9 3 1 11 1 6 6 4 2 7
6
0 1 4 5 0 0
6
0 0 0 0 0 0
15
0 4 0 13 0 0 6 0 13 0 0 2 8 3 0

样例输出

0
1
67
27867
528208295

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）