P10881 「KDOI-07」能量场 - I

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

#define me(f, x) memset(f, x, sizeof(f))

constexpr int N = 22;
constexpr int M = (1 << 20) + 3;
constexpr int P = 998244353;
int n, a[N], m, A[N][N], id[N], deg[N], pr[N], sf[N];

IL int qpow (int b, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, b = (LL)b * b % P) if (k & 1) r = (LL)r * b % P;
  return r;
}

int iv[N];

void init () {
  iv[1] = 1;
  L (i, 2, n) {
    iv[i] = (LL)iv[P % i] * (P - P / i) % P;
  }
  L (i, 3, n) {
    iv[i] = (LL)(P + 1) / 2 * iv[i] % P;
  }
}

int T[M], f[M][N];

IL int det () {
  L (i, 1, m) {
    L (j, 1, m) {
      A[i][j] = (P - A[i][j]) % P;
    }
  }
  L (i, 1, m) {
    (A[i][i] += deg[i]) %= P;
  }
  int det = 1;
  L (i, 1, m) {
    int t = 0;
    L (j, i, m) {
      if (A[j][i]) {
        t = j;
        break;
      }
    }
    if (!t) {
      return 0;
    }
    if (i ^ t) {
      swap(A[i], A[t]);
      det = P - det;
    }
    det = (LL)det * A[i][i] % P;
    int x = qpow(A[i][i]);
    L (j, i + 1, m) {
      int y = (LL)(P - A[j][i]) * x % P;
      L (k, 1, m) {
        A[j][k] = (A[j][k] + (LL)y * A[i][k]) % P;
      }
    }
  }
  return det % P;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  init();
  L (i, 0, n - 1) {
    cin >> a[i];
  }
  L (t, 0, n - 1) {
    me(f, 0);
    f[1 << t][t] = 1;
    L (s, 0, (1 << n) - 2) if (s >> t & 1) {
      vi u, v;
      int x = s;
      while (x) {
        int i = __builtin_ctz(x);
        u.eb(i), x ^= 1 << i;
      }
      x = (1 << n) - 1 - s;
      while (x) {
        int i = __builtin_ctz(x);
        v.eb(i), x ^= 1 << i;
      }
      for (int i : v) {
        int ss = 0;
        for (int j : u) {
          ss = (ss + (LL)f[s][j] * (a[i] + a[j])) % P;
        }
        (f[s | (1 << i)][i] += ss) %= P;
      }
    }
    L (s, 0, (1 << n) - 1) {
      L (i, 0, n - 1) {
        if (s >> i & 1) {
          T[s] = (T[s] + (LL)f[s][i] * (a[i] + a[t])) % P;
        }
      }
    }
  }
  L (s, 0, (1 << n) - 1) {
    T[s] = (LL)T[s] * iv[__builtin_popcount(s)] % P;
  }
  int ns = T[(1 << n) - 1];
  L (s, 0, (1 << n) - 2) {
    int cnt = __builtin_popcount(s);
    if (cnt > 2) {
      m = 0;
      L (i, 0, n - 1) {
        id[i] = (s >> i & 1) ? 0 : ++m;
      }
      me(deg, 0);
      me(A, 0);
      L (i, 0, n - 1) {
        L (j, 0, n - 1) {
          int w = (a[i] + a[j]) % P;
          (A[id[i]][id[j]] += w) %= P;
          (deg[id[i]] += w) %= P;
        }
      }
      pr[0] = 1;
      L (i, 1, m) {
        pr[i] = (LL)pr[i - 1] * deg[i] % P;
      }
      sf[m + 1] = 1;
      R (i, m, 1) {
        sf[i] = (LL)sf[i + 1] * deg[i] % P;
      }
      int ss = pr[m];
      L (i, 1, m) {
        int t = 1;
        ss = (ss + (LL)(P - A[i][i]) * pr[i - 1] % P * sf[i + 1]) % P;
        L (j, i + 1, m) {
          LL w = ((LL)(P - A[i][j]) * A[j][i] + (LL)A[i][i] * A[j][j]) % P;
          ss = (ss + (LL)w * pr[i - 1] % P * sf[j + 1] % P * t) % P;
          t = (LL)t * deg[j] % P;
        }
      }
      ns = (ns + (LL)ss * T[s]) % P;
    }
  }
  cout << ns << '\n';
}
// I love WHQ!