题目大意
给出(n)以及(a_{1,2,...,n})，表示有(n)个完全图，第(i)个完全图大小为(a_i)，这些完全图之间第(i)个完全图的点(a_i)与(imod n+1)的点(1)相连。问有多少种方法可以删掉某些边，使得整个图变成一个森林。
思路
话说因为是英文懒得读题，直接看题解里面的题目大意，结果一直理解不了，后来才发现他意思写错了。。。所以说一个正确的题目大意有多重要（雾
有一个人尽皆知的知识，就是(n)个点的树有(n^{n-2})个。下面会用到这个东西。
我们设(f_i)表示(i)个点的完全图删掉一些边变成森林的方案数。可以得到:
[f_n=sum_{i=0}^{n-1}inom{n-1}{i}f_i(n-i)^{n-i-2}
]
[=(n-1)!sum_{i=0}^{n-1}frac{f_i}{i!}frac{(n-i)^{n-i-2}}{(n-i-1)!}
]
这个式子的意思就是我们可以先固定一个点，然后从(n-1)选出(i)个点单独成森林，然后剩下的点组成一棵树。
然后我们发现这个式子我们其实可以使用分治( ext {NTT})预处理(Theta(nlog^2 n))之内求出来。
我们考虑如何统计答案。我们发现其实可以使用容斥原理求到:
[ ext {ans}=2^nprod_{i=1}^{n} f_{a_i}-prod_{i=1}^{n} (sum_{j=2}^{a_i}inom{a_i-2}{j-2}j^{j-2}f_{a_i-j})
]
前面一个的意思就是统计所有的答案，完全图之间管它连不连，后面一个就是整个图构成一个大环（这其实并不准确，但是意思到位就行）。既然要构成大环，肯定一个完全图内首尾要相连，就肯定是一棵树（要删边成森林）。
然后我们发现后面那个式子可以( ext {NTT})预处理，于是我们就解决了这个问题。
总时间复杂度为(Theta(max{a_i}log^2 max{a_i}+Tn))。
( ext {Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 998244353
#define ll long long
#define MAXN 600005
int quick_pow (int a,int b,int c){
int res = 1;for (;b;b >>= 1,a = 1ll * a * a % c) if (b & 1) res = 1ll * res * a % c;
return res;
}
int rev[MAXN];
void NTT (int *a,int len,int type){
#define G 3
#define Gi 332748118
int limit = 1,l = 0;
while (limit < len) limit <<= 1,l ++;
for (Int i = 0;i < limit;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
for (Int i = 0;i < limit;++ i) if (i < rev[i]) swap (a[i],a[rev[i]]);
for (Int i = 1;i < limit;i <<= 1){
int Wn = quick_pow (type == 1 ? G : Gi,(mod - 1) / (i << 1),mod);
for (Int j = 0;j < limit;j += i << 1)
for (Int k = 0,w = 1;k < i;++ k,w = 1ll * w * Wn % mod){
int x = a[j + k],y = 1ll * w * a[i + j + k] % mod;
a[j + k] = (x + y) % mod,a[i + j + k] = (x + mod - y) % mod;
}
}
if (type == 1) return ;
for (Int i = 0,Inv = quick_pow (limit,mod - 2,mod);i < limit;++ i) a[i] = 1ll * a[i] * Inv % mod;
#undef G
#undef Gi
}
void multi (int *a,int *b,int *c,int len1,int len2){
int limit = 1;
while (limit < len1 + len2 - 1) limit <<= 1;
for (Int i = len1;i < limit;++ i) a[i] = 0;
for (Int i = len2;i < limit;++ i) b[i] = 0;
NTT (a,limit,1),NTT (b,limit,1);
for (Int i = 0;i < limit;++ i) c[i] = 1ll * a[i] * b[i] % mod;
NTT (c,limit,-1);
}
int f[MAXN],g[MAXN],A[MAXN],B[MAXN],C[MAXN],fac[MAXN],ifac[MAXN];
void cdq (int l,int r){
if (l == r){
if (l == 0) f[l] = 1;
else f[l] = 1ll * f[l] * fac[l - 1] % mod;
return ;
}
int mid = (l + r) >> 1;cdq (l,mid);
for (Int i = l;i <= mid;++ i) A[i - l] = 1ll * f[i] * ifac[i] % mod;
B[0] = 1;for (Int i = 2;i <= r - l;++ i) B[i - 1] = 1ll * quick_pow (i,i - 2,mod) * ifac[i - 1] % mod;
multi (A,B,C,mid - l + 1,r - l);
for (Int i = mid + 1;i <= r;++ i) f[i] = (f[i] + C[i - l - 1]) % mod;
cdq (mid + 1,r);
}
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
signed main(){
#define Maxn 1<<17
#define Maxm 100005
fac[0] = 1;for (Int i = 1;i <= Maxn;++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[Maxn] = quick_pow (fac[Maxn],mod - 2,mod);for (Int i = Maxn;i;-- i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
cdq (0,Maxm);
for (Int i = 2;i <= Maxm;++ i) A[i - 2] = 1ll * quick_pow (i,i - 2,mod) * ifac[i - 2] % mod;
for (Int i = 0;i <= Maxm - 2;++ i) B[i] = 1ll * f[i] * ifac[i] % mod;
multi (A,B,C,Maxm - 1,Maxm - 1);
g[1] = 1;for (Int i = 2;i <= Maxm;++ i) g[i] = 1ll * fac[i - 2] * C[i - 2] % mod;
int T;read (T);
while (T --){
int n;read (n);int ans = quick_pow (2,n,mod),sum = 1;
for (Int i = 1,a;i <= n;++ i) read (a),ans = 1ll * ans * f[a] % mod,sum = 1ll * sum * g[a] % mod;
write ((ans + mod - sum) % mod),putchar ('
');
}
return 0;
}