题目大意.

求高维多项式 $\ln$。

时限 $4$s，各维长度 $n_i$ 之积不超过 $2.5\text{e}5$。

下面记维数为 $m$。

1. 高维多项式乘法

欲求 $\ln$ 必然要先考虑多项式乘法。毫无疑问，我们只需要对每一个方向做 DFT，就可以得到满足循环卷积的多项式乘法，具体来说做到的是

在一维情况下我们把循环卷积变为卷积的方法就是补长度，于是，你的确可以直接把每一维长度补到 $4$ 来计算子集卷积：只不过复杂度很劣而已（准确来说是要额外乘以 $2^m$）。这当然是无法接受的，所以原问题的关键实际上在于如何不给每一位补长度。

还是考虑子集卷积，一般的子集卷积解决上面这个问题的策略是编一个合适的占位函数 $|\mathbf i|$，满足

在子集卷积中，$|\mathbf i|=\sum i$。但是它对原问题来说值域太大了并不合适。事实上值域足够小的占位函数甚至是不大可能存在的。

但是其实我们只需要 $\{|\mathbf i\ominus\mathbf j|+|\mathbf j|\}$ 这个集合所在的区间长度 $L$ 较小即可；这样我们把占位函数模 $L$ 运算就足够了。EIls 找到的一个满足上述性质的占位函数如下。

记 $c(\mathbf i)=i_1+i_2n_1+\ldots+i_kn_1n_2...n_{k-1}$。显然 $\mathbf i$ 可按 $c(\mathbf i)$ 唯一地排成一个线性序列。重新定义 $\mathbf i \oplus\mathbf j=c^{-1}(c(\mathbf i)+c(\mathbf j))$（显然这个 $\oplus$ 意义下的卷积只需要对整个序列做多项式乘法即可）。

于是我们只需要监测每一位是否进位，具体来说

$$|\mathbf i|=\lfloor c(\mathbf i)/n_1\rfloor+\lfloor c(\mathbf i)/n_1n_2\rfloor+\ldots$$

显然地，此处 $L=k$。

于是这就在 $\Theta(k\cdot \prod n\cdot\sum \log n)$ 的时间内完成了多项式乘法。

2. 高维 Ln

牛迭和求导等均可直接按把高维多项式看成一维进行操作，此处不验证了。（可见上述变换的性质有多么优秀……我只能膜拜）

3. 参考瑇🐎

喜提最劣解第二

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
​
typedef long long ll;
typedef unsigned long long ull;
​
const int p = 998244353, g = 3, maxn = 1 << 19;
int qpow(int a, int k) {
    int ans = 1;
    for (; k; k >>= 1, a = (ull)a * a % p)
        if (k & 1) ans = (ull)ans * a % p;
    return ans;
}
int norm(int x) { return x >= p ? x - p : x; }
int mron(int x) { return x < 0 ? x + p : x; }
void add(int &x, int y) { if((x += y) >= p) x -= p; }
void sub(int &x, int y) { if((x -= y) < 0) x += p; }
​
int k;
int n[22], N = 1;
int a_[22][22];
​
vector<int> W[22];
int fac[maxn], ifac[maxn], inv[maxn];
int ppc[maxn];
void init(int n_) {
    for (int i = 0; i <= n_; i++) {
        W[i].resize(1 << i);
        int w = qpow(g, (p - 1) >> i);
        W[i][0] = 1;
        for (int j = 1; j <= 1 << i; j++) W[i][j] = (ull)W[i][j - 1] * w % p;
    }
    inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i < 1 << n_; i++)
        fac[i] = (ull)fac[i - 1] * i % p,
        inv[i] = (ull)mron(-inv[p % i]) * (p / i) % p, assert((ull)inv[i] * i % p == 1),
        ifac[i] = (ull)ifac[i - 1] * inv[i] % p;
    for (int i = 0; i < 1 << n_; i++) {
        for (int j = 1, i1 = i; j <= k; j++) ppc[i] += i1 /= n[j];
        ppc[i] %= k;
    }
}
​
void DFT(int d[], int n) {
    for (int L = n - 1, x = 1 << L; L >= 0; L--, x >>= 1)
    for (int *j = d; j < d + (1 << n); j += x << 1)
    for (int *k0 = j, *k1 = j + x, *w = W[L + 1].data(); k0 < j + x; k0++, k1++, w++) {
        int t = *k1;
        *k1 = (ull)mron(*k0 - t) * *w % p;
        add(*k0, t);
    }
}
void iDFT(int d[], int n) {
    for (int L = 0, x = 1; L < n; L++, x <<= 1)
    for (int *j = d; j < d + (1 << n); j += x << 1)
    for (int *k0 = j, *k1 = j + x, *w = W[L + 1].data() + (x << 1); k0 < j + x; k0++, k1++, w--) {
        int t = (ull)*k1 * *w % p;
        *k1 = mron(*k0 - t);
        add(*k0, t);
    }
    int invx = qpow(1 << n, p - 2);
    for (int i = 0; i < 1 << n; i++) d[i] = (ull)d[i] * invx % p;
}
​
void clear(int d[][maxn], int n0) {
    for (int i = 0; i < k; i++) memset(d[i], 0, 4 << n0);
}
void Conv(int p_[][maxn], int q[][maxn], int r[][maxn], int n0) {
    clear(r, n0);
    for (int i1 = 0; i1 < k; i1++)
    for (int i2 = 0; i2 < k; i2++) {
        int i3 = (i1 + i2) % k;
        for (int j = 0; j < 1 << n0; j++) r[i3][j] = (r[i3][j] + (ull)p_[i1][j] * q[i2][j]) % p;
    }
    for (int i3 = 0; i3 < k; i3++) iDFT(r[i3], n0);
}
int d[maxn], ans[maxn], P[22][maxn], Q[22][maxn], R[22][maxn];
void Inv(int n0) {
    if(n0 == 0) {
        ans[0] = 1;
        return;
    }
    Inv(n0 - 1);
    int x = 1 << n0;
    clear(P, n0), clear(Q, n0);
    for (int i = 0; i < x; i++) P[ppc[i]][i] = ans[i], Q[ppc[i]][i] = d[i];
    for (int i = 0; i < k; i++) DFT(P[i], n0), DFT(Q[i], n0);
    Conv(P, Q, R, n0); clear(Q, n0);
    for (int i = x >> 1; i < x; i++) Q[ppc[i]][i] = R[ppc[i]][i];
    for (int i = 0; i < k; i++) DFT(Q[i], n0);
    Conv(P, Q, R, n0);
    for (int i = x >> 1; i < x; i++) ans[i] = mron(-R[ppc[i]][i]);
}
​
int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) scanf("%d", &n[i]), N *= ++n[i];
    for (int i = 1; i <= k; i++)
    for (int j = 1; j <= k; j++) scanf("%d", &a_[i][j]), a_[i][j]++;
    int N_ = 0; while(1 << N_ < N) N_++; init(N_);
    for (int i = 0; i < 1 << N_; i++) {
        static int v[22];
        d[i] = 1;
        for (int j = 1, i1 = i; j <= k; i1 /= n[j++]) {
            v[j] = i1 % n[j];
            d[i] = (ull)d[i] * ifac[v[j]] % p;
        }
        for (int x = 1; x <= k; x++)
        for (int y = x; y <= k; y++)
            d[i] = (ull)d[i] * qpow(a_[x][y], x == y ? (ull)v[x] * (v[x] - 1) / 2 % (p - 1) : v[x] * v[y]) % p;
    }
    Inv(N_);
    int ANS = 0;
    for (int i = 0; i < N; i++) ANS = (ANS + (ull)ans[i] * d[N - i - 1] % p * (N - i - 1)) % p;
    ANS = (ull)ANS * qpow(N - 1, p - 2) % p;
    for (int i = 1; i <= k; i++) ANS = (ull)ANS * fac[n[i] - 1] % p;
    printf("%d\n", ANS);
}