Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Don’t try to build the tree directly. For labeled trees, the degrees are screaming “Prufer sequence”. A vertex degree is basically 1 + how many times it appears.
For a color with vertices, its total degree parity is
where is the number of positions in the Prufer sequence occupied by vertices of color .
So the whole problem becomes: count length sequences where each position chooses one of the vertices, and the parity of how many chosen vertices belong to each color is fixed. Choosing color has weight .
For one color with vertices, its contribution to a generating function is split into even/odd powers:
Multiply the required or over colors, then take coefficient of and multiply by .
The constraints allow per test over the relevant degree range. Build the product DP by degrees: dp[len] stores the coefficient using processed colors. For each color, transition by adding only terms with the required parity. Empty colors are a quick impossibility check if they demand odd parity.
We are counting labeled trees on the fixed vertex set . The colors are fixed too. Only the edges vary.
The annoying condition is about degrees grouped by color. Direct tree DP is a trap: the tree has no given shape, so there is nothing useful to root. Use the classic labeled-tree weapon: Prufer sequences.
For , every labeled tree corresponds to exactly one Prufer sequence of length . If a vertex appears times in the sequence, then
Let be the number of vertices of color , and let be the total number of Prufer positions whose chosen vertex has color .
Then the total degree of all vertices of color is
So the required condition becomes
Since subtraction and addition are the same modulo , define
Now forget trees for a second. We just need to count Prufer sequences of length such that color appears with parity .
If a sequence uses color counts , with , then the number of actual vertex sequences with those color counts is
because every time we pick color , there are actual vertices available.
So the answer is
\frac{L!}{x_1!x_2!\cdots x_m!}\prod_{j=1}^m a_j^{x_j}.$$ This already looks like exponential generating functions, because of the $x_j!$ denominators. For each color $j$, we want either only even powers or only odd powers: $$P_j(z)=\sum_{\substack{k\ge 0\\k\equiv need_j\pmod 2}}\frac{a_j^k z^k}{k!}.$$ Then $$\text{answer}=L!\cdot [z^L]\prod_{j=1}^m P_j(z).$$ No FFT is needed here, despite the tag trying to look scary in a hoodie. The total $n$ and $m$ are only $10^4$, and each test only needs coefficients up to $L\le n-2$. A straightforward degree DP is enough. **DP definition** Let $dp[s]$ be the coefficient of $z^s$ after processing some colors. Initially: $$dp[0]=1.$$ For a color with $a$ vertices and required parity $p$, we transition by choosing a contribution size $k$ such that $k\equiv p\pmod 2$: $$ndp[s+k] += dp[s]\cdot \frac{a^k}{k!}.$$ All arithmetic is modulo $10^9+7$, so division by $k!$ means multiplication by the modular inverse factorial $invfact[k]$. After all colors are processed, the answer is $$dp[L]\cdot L! \pmod {10^9+7}.$$ **Empty colors** If $a_j=0$, there are no vertices of that color. Its total degree is always $0$. Therefore if $\mathrm{mask}_j=1$, the answer is instantly $0$. The DP handles this too in spirit, but checking it explicitly is cleaner. For $a=0$, only $k=0$ contributes, so it cannot satisfy an odd needed parity. **The $n=1$ case** There is exactly one tree: the single isolated vertex. Its degree is $0$, so every color has total degree $0$. Therefore the answer is $1$ iff all masks are $0$, otherwise $0$. Do not try to force Prufer here; length $n-2=-1$ is nonsense. Tiny case, tiny hammer. **Complexity** For each test case, the DP has at most $L+1\le n-1$ states. For each color, we try valid contribution sizes up to $L$, giving $$O(mn)$$ time per test case and $O(n)$ memory. Since the sums of $n$ and $m$ over all tests are both at most $10^4$, this is fine.#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
int main() {
setIO();
int T;
cin >> T;
const int MAXN = 10000;
vector<ll> fact(MAXN + 1), invfact(MAXN + 1);
fact[0] = 1;
for (int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
invfact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> cnt(m + 1, 0);
for (int i = 0; i < n; i++) {
int c;
cin >> c;
cnt[c]++;
}
vector<int> mask(m + 1);
bool bad = false;
for (int i = 1; i <= m; i++) {
cin >> mask[i];
if (cnt[i] == 0 && mask[i] == 1) bad = true;
}
if (n == 1) {
cout << (bad ? 0 : 1) << '\n';
continue;
}
if (bad) {
cout << 0 << '\n';
continue;
}
int L = n - 2;
vector<ll> dp(L + 1, 0), ndp(L + 1, 0);
dp[0] = 1;
for (int color = 1; color <= m; color++) {
int a = cnt[color];
int need = mask[color] ^ (a & 1);
vector<ll> term(L + 1, 0);
ll pw = 1;
for (int k = 0; k <= L; k++) {
if ((k & 1) == need) term[k] = pw * invfact[k] % MOD;
pw = pw * a % MOD;
}
fill(ndp.begin(), ndp.end(), 0);
for (int s = 0; s <= L; s++) {
if (dp[s] == 0) continue;
for (int k = need; s + k <= L; k += 2) {
ndp[s + k] = (ndp[s + k] + dp[s] * term[k]) % MOD;
}
}
dp.swap(ndp);
}
cout << dp[L] * fact[L] % MOD << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
int main() {
setIO();
int T;
cin >> T;
const int MAXN = 10000;
vector<ll> fact(MAXN + 1), invfact(MAXN + 1);
fact[0] = 1;
for (int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
invfact[MAXN] = modpow(fact[MAXN], MOD - 2);
for (int i = MAXN; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> cnt(m + 1, 0);
for (int i = 0; i < n; i++) {
int c;
cin >> c;
cnt[c]++;
}
vector<int> mask(m + 1);
bool bad = false;
for (int i = 1; i <= m; i++) {
cin >> mask[i];
if (cnt[i] == 0 && mask[i] == 1) bad = true;
}
if (n == 1) {
cout << (bad ? 0 : 1) << '\n';
continue;
}
if (bad) {
cout << 0 << '\n';
continue;
}
int L = n - 2;
vector<ll> dp(L + 1, 0), ndp(L + 1, 0);
dp[0] = 1;
for (int color = 1; color <= m; color++) {
int a = cnt[color];
int need = mask[color] ^ (a & 1);
vector<ll> term(L + 1, 0);
ll pw = 1;
for (int k = 0; k <= L; k++) {
if ((k & 1) == need) term[k] = pw * invfact[k] % MOD;
pw = pw * a % MOD;
}
fill(ndp.begin(), ndp.end(), 0);
for (int s = 0; s <= L; s++) {
if (dp[s] == 0) continue;
for (int k = need; s + k <= L; k += 2) {
ndp[s + k] = (ndp[s + k] + dp[s] * term[k]) % MOD;
}
}
dp.swap(ndp);
}
cout << dp[L] * fact[L] % MOD << '\n';
}
return 0;
}