题意：给你一个长度为n的序列a，求它所有子序列的和的积
注意到题目说(sum a_i)不超过1e5，也就是子序列的和不超过1e5
可以考虑枚举子序列的和s，算有多少个这样的子序列，那么答案就形如
[
m prod_{s=0}^{sum} s^{cnt[s]}
]
类似生成函数的套路，每个数的生成函数为
[(1+x^{a_i})
]
代表这个数选或不选，那么总的方案就是
[prod_{i=1}^{n}(1+x^{a_i})
]
先假设不取模，那么这个东西可以用分治FFT做，之前一直不知道如何具体实现
实现中用结构体存多项式，也就是一段系数，提前开好内存池，每次分配一段进去，保存首地址
int B[MAXN*2],tot;
struct P{
int *a,len;
void init(int _len){
len=_len;
a=B+tot;
for(int i=0;i<len;i++)
a[i]=0;
a[0]++;a[len-1]++;
tot+=len;
}
void mul(const P& rhs){
len=MTT(a,rhs.a,len,rhs.len,a,MOD-1);
}
};
支持两个操作，一个是初始化init，一个是乘上另一个多项式
然后套一个分治FFT，模仿了std的机智写法，在递归边界处读入
P solve(int l,int r){
P ans;
if(l==r){
int x=rd();
ans.init(x+1);
}else{
int mid=(l+r)>>1;
ans=solve(l,mid);
ans.mul(solve(mid+1,r));
}
return ans;
}
然后这个式子实际上是需要取模的，下面的相乘可以直接模，快速幂也可以直接模，但指数部分要模(varphi(MOD))
也就是要模998244352，任意模数NTT，搬出来优秀的MTT的板子，也就是拆位FFT，复杂度(O(nlog^2n))
#include<bits/stdc++.h>
using namespace std;
int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
typedef long long ll;
const int inf = 1<<30;
const int MAXN = 100005;
const int MOD = 998244353;
const int BASE = 1 << 15;
const long double Pi = acos(-1.0);
struct CP {
long double x, y;
CP (long double xx = 0, long double yy = 0) {
x = xx, y = yy;
}
} P1[MAXN << 2], P2[MAXN << 2], Q[MAXN << 2];
CP operator + (CP a, CP b) {
return CP(a.x + b.x, a.y + b.y);
}
CP operator - (CP a, CP b) {
return CP(a.x - b.x, a.y - b.y);
}
CP operator * (CP a, CP b) {
return CP(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
int limit, r[MAXN << 2];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return ans;
}
void FFT(CP *A, int type) {
for (int i = 0; i < limit; i++)
if (i < r[i])
swap(A[i], A[r[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
CP Wn( cos(Pi / mid), type * sin(Pi / mid) );
for (int R = mid << 1, j = 0; j < limit; j += R) {
CP w(1, 0);
for (int k = 0; k < mid; k++, w = w * Wn) {
CP x = A[j + k], y = w * A[j + mid + k];
A[j + k] = x + y;
A[j + mid + k] = x - y;
}
}
}
}
void init(int n) {
limit = 1;
while (limit <= n)
limit <<= 1;
for (int i = 1; i < limit; i++)
r[i] = r[i >> 1] >> 1 | ((i & 1) ? limit >> 1 : 0);
}
int MTT(int *a, int *b, int n, int m, int *res, int MOD) {
init(n + m);
for (int i = 0; i < n; i++) {
P1[i] = {a[i] / BASE, a[i] % BASE};
P2[i] = {a[i] / BASE, -a[i] % BASE};
}
for (int i = n; i < limit; i++) {
P1[i] = {0, 0}, P2[i] = {0, 0};
}
for (int i = 0; i < m; i++) {
Q[i] = {b[i] / BASE, b[i] % BASE};
}
for (int i = m; i < limit; i++) {
Q[i] = {0, 0};
}
FFT(P1, 1), FFT(P2, 1), FFT(Q, 1);
for (int i = 0; i < limit; i++) {
Q[i].x /= limit, Q[i].y /= limit;
P1[i] = P1[i] * Q[i], P2[i] = P2[i] * Q[i];
}
FFT(P1, -1), FFT(P2, -1);
for (int i = 0; i < n + m - 1; i++) {
long long a1b1, a1b2, a2b1, a2b2;
a1b1 = (long long)floor((P1[i].x + P2[i].x) / 2 + 0.5) % MOD;
a1b2 = (long long)floor((P1[i].y + P2[i].y) / 2 + 0.5) % MOD;
a2b1 = (long long)floor((P1[i].y - P2[i].y) / 2 + 0.5) % MOD;
a2b2 = (long long)floor((P2[i].x - P1[i].x) / 2 + 0.5) % MOD;
res[i] = ((a1b1 * BASE + (a1b2 + a2b1)) * BASE + a2b2) % MOD;
res[i] = (res[i] + MOD) % MOD;
}
return n + m - 1;
}
int B[MAXN*2],tot;
struct P{
int *a,len;
void init(int _len){
len=_len;
a=B+tot;
for(int i=0;i<len;i++)
a[i]=0;
a[0]++;a[len-1]++;
tot+=len;
}
void mul(const P& rhs){
len=MTT(a,rhs.a,len,rhs.len,a,MOD-1);
}
};
P solve(int l,int r){
P ans;
if(l==r){
int x=rd();
ans.init(x+1);
}else{
int mid=(l+r)>>1;
ans=solve(l,mid);
ans.mul(solve(mid+1,r));
}
return ans;
}
int n;
void work(){
tot=0;
n=rd();
P res=solve(1,n);
ll ans=1;
if(res.a[0]>1){
puts("0");
return;
}
for(int i=1;i<res.len;i++){
ans=(ans*qpow(i,res.a[i]))%MOD;
}
cout<<ans<<endl;
}
int main(){
freopen("input.txt","r",stdin);
int T=rd();
while(T--) work();
}