题解 P8280 Photoelectric Effect
Ryo_Yamada
·
·
题解
高复杂度做法。
看到 k=5，可以思考一些复杂度带 2^k 或 k! 的做法。
我们发现从 u 子树中选两个点 x,y 使 lca=u，一定是 x, \, y 属于 u 两个不同的儿子的子树。于是如果我们知道了 u 每个儿子的子树用了的颜色集合，就可以算出 u 需要选的颜色（或无解）。
考虑先预处理出 \text{trs}_{i,j} 表示：若对于一个节点 u 的两个儿子 x,\,y，它们用了的颜色集合为 i,\,j，则 u 需要用什么颜色（-1 表示无解）。这个过程可以直接 k^2 \times 2^{2k} 做。
接下来考虑如何进行树形dp。设 dp_{u,i,j} 表示对于节点 u，当它用颜色 i 且它的子树（不包括 u 本身）所用颜色集合为 j 时的方案数。
首先，对于每个叶子节点 x 都有 dp_{x,i,0}=1。
对于非叶子节点 u，枚举它的每个叶子节点 v。枚举 u 当前用的颜色集合 j 和 v 的状态 dp_{v,i',j'}。若 \text{trs}_{j,j'} \not= -1，令 js=j' | \, 2^{i'-1} 则可以转移到 dp_{u,\text{trs}_{i, js}, i|js}。最终时间复杂度 O(nk \times 2^{2k})，空间复杂度 O(nk \times 2^k)。能过也是奇迹（。
```cpp
def(N, int, 1e5 + 5)
def(p, int, 1e9 + 7)
int n, k, sta;
int to[6][6];
int trs[1 << 5][1 << 5];
vector<int> e[N];
int dp[N][6][1 << 5], f[N][6][1 << 5];
int get(int x, int y) {
int res = 0;
rep(i, 1, k) {
if(!(x >> (i - 1) & 1)) continue;
rep(j, 1, k) {
if(!(y >> (j - 1) & 1)) continue;
if(!res) res = to[i][j];
else if(res != to[i][j]) res = -1;
}
}
swap(x, y);
rep(i, 1, k) {
if(!(x >> (i - 1) & 1)) continue;
rep(j, 1, k) {
if(!(y >> (j - 1) & 1)) continue;
if(!res) res = to[i][j];
else if(res != to[i][j]) res = -1;
}
}
return res;
}
void dfs(int u) {
if(!e[u].size()) {
rep(i, 1, k) dp[u][i][0] = 1;
return ;
}
rep(l, 0, e[u].size() - 1) {
int v = e[u][l];
dfs(v);
if(!l) {
rep(nw, 1, k) rep(i, 0, sta) rep(j, 1, k) dp[u][nw][i | (1 << j - 1)] = (dp[u][nw][i | (1 << j - 1)] + dp[v][j][i]) % p;
continue;
}
rep(i, 1, sta) rep(j, 1, k) f[u][j][i] = dp[u][j][i], dp[u][j][i] = 0;
rep(i, 1, sta) {
if(!dp[v][i]) continue;
rep(j, 0, sta) {
rep(nw, 1, k) {
int js = (j | (1 << nw - 1));
if(trs[i][js] == -1) continue;
dp[u][trs[i][js]][i | js] = (dp[u][trs[i][js]][i | js] + 1ll * f[u][trs[i][js]][i] * dp[v][nw][j] % p) % p;
}
}
}
}
}
int main() {
int t; cin >> t;
W(t) {
qread(n, k);
sta = (1 << k) - 1;
rep(i, 1, n) e[i].clear();
rep(i, 1, k) rep(j, 1, k) qread(to[i][j]);
rep(i, 2, n) {
int f; qread(f);
e[f].pb(i);
}
rep(i, 1, sta) rep(j, 1, sta) trs[i][j] = get(i, j);
rep(i, 1, n) {
memset(dp[i], 0, sizeof dp[i]);
memset(f[i], 0, sizeof f[i]);
}
dfs(1);
ll ans = 0;
// rep(i, 1, n) rep(l, 1, n) rep(j, 0, sta) printf("dp[%d][%d][%d] : %lld\n", i, l, j, dp[i][l][j]);
rep(l, 1, k) rep(i, 1, sta) ans = (ans + dp[1][l][i]) % p;
cout << ans << '\n';
}
return 0;
}
```