相当于求 \(n\) 个集合幂级数 \(F_1, F_2, \dots, F_n\) 的子集卷积的 \(x^U\) 项系数，其中 \(F_i = \sum\limits_S [S\subseteq S_i] h_{i, \text{popcount} (S)} x^S\)。
直接做是 \(\mathcal O(2 ^ n n ^ 3)\)，不可通过。
考虑特殊的手法转化为 \(\exp(\sum\limits_{i = 1} ^ n \ln F_i)\)。
对于 \(\ln F_i\)，发现有值的位置为 \(S_i\) 的子集，并且 \([x ^ S] \ln F_i\) 的值只与 \(\text {popcount} (S)\) 有关，单次 \(\ln\) 可以做到 \(\mathcal O(n ^ 2)\)，总共为 \(\mathcal O(n ^ 3)\)。
对于 \(\exp\)，直接做就是 \(\mathcal O(2 ^ n n ^ 2)\)。
总时间复杂度为 \(\mathcal O(n ^ 3 + 2 ^ n n ^ 2)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll int
#define LL long long
#define ull unsigned
#define uLL unsigned LL
#define fi first
#define se second
#define mkp make_pair
#define pir pair<ll, ll>
#define pb push_back
#define i128 __int128
using namespace std;
template <class T>
const inline void rd(T &x) {char ch;bool neg = 0;while (!isdigit(ch = getchar()))if (ch == '-')neg = 1;x = ch - '0';while (isdigit(ch = getchar())) x = (x << 1) + (x << 3) + ch - '0';if (neg)x = -x;
}
const ll maxn = 23, M = 6e5 + 10, inf = 1e9 + 5; ll mod;
const ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;
const LL INF = 3e18 + 5;
ll power(ll a, ll b = mod - 2, ll p = mod) {ll s = 1;while (b) {if (b & 1)s = 1ll * s * a % p;a = 1ll * a * a % p, b >>= 1;}return s;
}
template <class T, class _T>
const ll pls(const T x, const _T y) { return x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const ll mus(const T x, const _T y) { return x < y ? x + mod - y : x - y; }
template <class T, class _T>
const void add(T &x, const _T y) { x = x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const void sub(T &x, const _T y) { x = x < y ? x + mod - y : x - y; }
template <class T, class _T>
const void chkmax(T &x, const _T y) { x = x < y ? y : x; }
template <class T, class _T>
const void chkmin(T &x, const _T y) { x = x < y ? x : y; }ll n, m, msk[maxn], h[maxn][maxn];
ll f[1 << 21], r[23], C[23][23], popcnt[1 << 21];
ll g[1 << 21], a[23][1 << 21], b[23][1 << 21], d[23][1 << 21];
LL c[23], s[23], t[23];void exgcd(ll a, ll b, ll &x, ll &y) {if(!b) return x = 1, y = 0, void();exgcd(b, a % b, y, x);y -= a / b * x;
}
ll getinv(ll x) {ll _, y;exgcd(x, mod, y, _);return (y % mod + mod) %mod;
}const LL LIM = 8e18;int main() {rd(mod), rd(n), rd(m); C[0][0] = 1;for(ll i = 1; i <= n; i++) {C[i][0] = 1;for(ll j = 1; j <= i; j++)C[i][j] = pls(C[i - 1][j], C[i - 1][j - 1]);}for(ll i = 1; i <= m; i++) {ll u, v; rd(u), rd(v);msk[u] |= 1 << v - 1;}for(ll S = 1; S < (1 << n); S++) popcnt[S] = popcnt[S & (S - 1)] + 1;for(ll i = 1; i <= n; i++) {ll k, x; rd(k);for(ll j = 0; j < k; j++) {rd(x);for(ll p = 0, t = 1; p <= n; p++, t = (LL) t * x %mod)add(h[i][p], t);}ll Inv = getinv(k);for(ll j = 0; j <= n; j++)h[i][j] = (LL) h[i][j] * Inv %mod;}for(ll i = 1; i <= n; i++) {for(ll j = 1; j <= n; j++) {r[j] = h[i][j];for(ll k = 1; k < j; k++)sub(r[j], (LL) h[i][k] * r[j - k] %mod * C[j - 1][k] %mod);}for(ll S = msk[i]; S; S = (S - 1) & msk[i])add(f[S], r[popcnt[S]]);}g[0] = 1;for(ll S = 0; S < (1 << n); S++)for(ll T = S; T; T = (T - 1) & S)if((S & -S) == (T & -T))add(g[S], (LL) g[S ^ T] * f[T] %mod);for(ll i = 0; i < n - 1; i++) {for(ll j = 0; j <= i; j++)for(ll S = 0; S < (1 << i); S++)a[j][S] = b[j][S] = 0;for(ll S = 0; S < (1 << i); S++)a[popcnt[S]][S] = g[S], b[popcnt[S]][S] = f[S | (1 << i)];for(ll u = 0; u <= i; u++)for(ll j = 0; j < i; j++)for(ll S = 0; S < (1 << i); S++)if(S & (1 << j))add(a[u][S], a[u][S ^ (1 << j)]),add(b[u][S], b[u][S ^ (1 << j)]);for(ll S = 0; S < (1 << i); S++) {for(ll j = 0; j <= i; j++) {c[j] = 0, s[j] = a[j][S], t[j] = b[j][S];for(ll k = 0; k <= j; k++) {c[j] += (LL) s[k] * t[j - k];if(c[j] > LIM) c[j] %= mod;}d[j][S] = c[j];}} for(ll u = 0; u <= i; u++) {for(ll j = 0; j < i; j++)for(ll S = 0; S < (1 << i); S++)if(S & (1 << j))sub(d[u][S], d[u][S ^ (1 << j)]);}for(ll S = 0; S < (1 << i); S++) g[S | (1 << i)] = d[popcnt[S]][S];} ll ans = 0;for(ll S = 0; S < (1 << n - 1); S++)add(ans, (LL) g[S] * f[((1 << n) - 1) ^ S] %mod);printf("%d\n", g[(1 << n) - 1]);return 0;
}