AT_ddcc2017_final_d なめらかな木 的線性做法
給定一棵 \(N\) 個點的樹，你需要給每一個節(jié)點編號 \(a_i\)，使得所有點的編號構(gòu)成一個 \(1\sim N\) 的排列，問有多少種方法使得任意相鄰節(jié)點編號差不超過 \(2\)，答案對 \(10^9+7\) 取模。
\(\texttt{Data Range:}\;N\le50\texttt{; Time Limit: 2000ms; Memory Limit: 256MB}\)。
本題解采用自頂向下的方式說明如何設(shè)出狀態(tài)以及轉(zhuǎn)移方程。
如果一個點的度數(shù) \(>4\)，那么顯然答案為 \(0\)，記 \(T(x,y)\) 表示以 \(x\) 為根，砍掉所有 \(y\) 對應(yīng)的子樹后得到的樹，其中 \(y\) 中的每個元素都是 \(x\) 為根時的子節(jié)點。
否則，記 \(f(x,y)\) 表示只考慮樹 \(T(x,y)\)，且 \(a_x=1\) 時的方案數(shù)，則答案為 \(\sum\limits_{i=1}^{n}f(x,\varnothing)\)。
考慮根據(jù) \(x\) 刪去 \(y\) 對應(yīng)的子樹后的情況分類討論：
- 如果此時 \(x\) 的兒子個數(shù)為 \(0\)，顯然答案為 \(1\)；
- 如果此時 \(x\) 的兒子個數(shù)大于 \(2\)，顯然答案為 \(0\)；
- 如果此時 \(x\) 的兒子個數(shù)為 \(2\)，那么我們需要將兩個兒子分別填入 \(2,3\) 或 \(3,2\)。
此時，我們記 \(g(x,y,X,Y)\) 表示假設(shè)同時考慮 \(T(x,y)\) 和 \(T(X,Y)\) 這兩棵子樹，且強制要求 \(a_x=1,a_X=2\) 時的方案數(shù)，那么這種情況可由 \(g\) 轉(zhuǎn)移。 - 如果此時 \(x\) 的兒子個數(shù)為 \(1\)，我們找到第一個分岔點，記為 \(z\)，我們再根據(jù) \(z\) 的度數(shù)分類討論：
- 如果 \(z\) 的度數(shù)為 \(1\)，則此時為一條鏈，可以預(yù)處理出此時對應(yīng)的答案 \(\mathit{dp1}_{\mathit{len}}\)，其中 \(\mathit{len}\) 為鏈上的節(jié)點數(shù)量。具體的，\(\mathit{dp1}_x\) 表示 \(x\) 個點的鏈，要求第一個節(jié)點對應(yīng)的數(shù)字為 \(1\) 的方案數(shù)。
- 如果 \(z\) 的度數(shù)為 \(4\)，假設(shè)它對應(yīng)的數(shù)字是 \(v\)，那么它相鄰四個節(jié)點上的數(shù)字就是 \(v-2,v-1,v+1,v+2\)，顯然可以被劃分為 \((v-2,v-1)\) 以及 \((v+1,v+2)\) 兩組，彼此之間獨立。
- 我們再記 \(h_1(x,y,z)\) 表示考慮 \(T(x,y)\) 以及一條長度為 \(z\) 的鏈，其中 \(a_x=1\)，鏈首值為 \(2\)，鏈末值最大；\(h_2(x,y,z)\) 表示考慮 \(T(x,y)\) 以及一條長度為 \(z\) 的鏈，其中 \(a_x=2\)，鏈首值為 \(1\)，鏈末值最大。再記 \(h(x,y,z)=h_1(x,y,z)+h_2(x,y,z)\)。
- 則這種情況可以將三棵非鏈端子樹以及一條鏈分成兩組，方案數(shù)為 \(g\) 和 \(h\) 的乘積。
- 如果 \(z\) 的度數(shù)為 \(3\)，記 \(x\) 到 \(z\) 這條鏈上的邊數(shù)為 \(c\)，假設(shè)它對應(yīng)的數(shù)字是 \(v\)，那么根據(jù)它相鄰三個節(jié)點以及子樹內(nèi)的 \(a\) 分類討論（假設(shè)靠近鏈的節(jié)點為 \(p\)，其余兩個節(jié)點為 \(q,r\) 且 \(a_q<a_r\)）：
- 如果 \(a_q=v+1,a_r=v+2,a_p=v-2\) 且 \(v-1\) 在 \(q\) 的子樹內(nèi)，我們枚舉 \(v-1\) 在 \(q\) 的哪個子樹內(nèi)，那么此時 \((v-1,v-2)\) 和 \((v+1,v+2)\) 就獨立了，可以由一個 \(g\) 以及一個 \(h_1\) 的乘積轉(zhuǎn)移而來；
- 如果 \(a_q=v+1,a_r=v+2,a_p=v-2\) 或 \(a_p=v-1\)，且 \(v-1\) 不在 \(q\) 的子樹內(nèi)，那么此時的 \((v+1,v+2)\) 和這條鏈就獨立了，可以由一個 \(p\) 和一個 \(\mathit{dp2}_c+\mathit{dp3}_c\) 的乘積轉(zhuǎn)移而來。具體的，\(\mathit{dp2}_x\) 表示 \(x\) 個點的鏈，要求第一個節(jié)點對應(yīng)的數(shù)字為 \(1\)，最后一個節(jié)點對應(yīng)的數(shù)字為 \(x\) 的方案數(shù)；\(\mathit{dp3}_x\) 表示 \(x\) 個點的鏈，要求第一個節(jié)點對應(yīng)的數(shù)字為 \(1\)，最后一個節(jié)點對應(yīng)的數(shù)字為 \(x-1\) 的方案數(shù)。
- 如果 \(a_q=v-2,a_r=v+2,a_p=v+1\)，那么此時可以 \((v+1,v+2)\) 就獨立出來了，可以由一個 \(f\) 和一個 \(h_2\) 轉(zhuǎn)移而來。
- 如果 \(a_q=v-1,a_r=v+2,a_p=v-2\) 且 \(v+1\) 在 \(q\) 的子樹內(nèi)，那么這種情況與第一種情況類似；
- 否則，必然有 \(a_r=v+1\) 或 \(v+2\)，且 \(a_p,a_q\) 一個為 \(v-1\) 一個為 \(v-2\)，在排除掉上面一種情況后，\((v-2,v-1)\) 又獨立了！所以可以由 \(x\) 去掉 \(p\) 和 \(q\) 為根的子樹對應(yīng)的 \(f\) 的一個 \(h\) 的乘積轉(zhuǎn)移而來。
綜上所述，我們完成了 \(f\) 的轉(zhuǎn)移，接下來我們討論 \(g(x,y,X,Y),h_1(x,y,z),h_2(x,y,z),\mathit{dp1}_x,\mathit{dp2}_x,\mathit{dp3}_x\) 的轉(zhuǎn)移。
先來討論比較簡單的 \(\mathit{dp1}_x,\mathit{dp2}_x,\mathit{dp3}_x\)，當(dāng) \(x\ge4\) 時，我們?nèi)菀椎玫剑?/p>
- \(\mathit{dp1}_x=\mathit{dp1}_{x-3}+\mathit{dp1}_{x-1}+1\)；
- \(\mathit{dp2}_x=\mathit{dp2}_{x-3}+\mathit{dp2}_{x-1}\)；
- \(\mathit{dp3}_x=\mathit{dp3}_{x-3}+\mathit{dp3}_{x-1}\)。
考慮 \(g(x,y,X,Y)\)，我們記 \(T(x,y)\) 和 \(T(X,Y)\) 中 \(x,X\) 的度數(shù)分別為 \(p,q\)，當(dāng) \(p=2\) 時顯然答案為 \(0\)；當(dāng) \(p=0\) 時可以規(guī)約回 \(f\)，所以只需考慮 \(p=1\) 的情況。
當(dāng) \(p=1\) 成立時，如果 \(q=0\) 我們?nèi)匀豢梢砸?guī)約回去，\(q=2\) 時答案仍為 \(0\)，所以只需考慮 \(p=q=1\) 的情況。
這個時候，我們發(fā)現(xiàn) \(x\) 與 \(X\) 唯一相鄰的點上填的數(shù)是確定的。所以可以迭代計算，為了加速，可以分別找到第一個分岔點，記兩條鏈的較小長度為 \(c\)，則可以一次性迭代 \(c\) 次，這可以預(yù)處理后 \(\mathcal{O}(1)\) 查詢所到節(jié)點。
發(fā)現(xiàn) \(h_1\) 和 \(h_2\) 也可以類似分討處理，在此不做贅述。
綜上所述，有關(guān) \(f\) 的全部狀態(tài)轉(zhuǎn)移可以全部使用 \(f\) 進行轉(zhuǎn)移。至此，本題在 \(\mathcal{O}(N)\) 的時間復(fù)雜度內(nèi)得解！
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 55, P = 1e9 + 7;
struct MOD {
int operator ()(long long x) {
return x - (((__int128)x * 18446743944) >> 64) * P;
}
} mod;
vector<int> G[N];
int f[N][1 << 4], cnt[1 << 4];
int id(int x, int y) {
for (int i = 0; i < (int)G[x].size(); ++i) {
if (y == G[x][i]) return 1 << i;
}
return -1;
}
vector<int> adj(int x, int y) {
vector<int> arr;
for (int i = 0; i < (int)G[x].size(); ++i) {
if (!((y >> i) & 1)) arr.push_back(G[x][i]);
}
return arr;
}
tuple<int, int, int> nxt[N][1 << 4];
tuple<int, int, int> getNxt(int x, int y) {
if (~get<0>(nxt[x][y])) return nxt[x][y];
vector<int> z = adj(x, y);
if (z.empty()) return nxt[x][y] = {0, 0, 0};
if (z.size() == 1) {
nxt[x][y] = getNxt(z[0], id(z[0], x));
++get<2>(nxt[x][y]);
return nxt[x][y];
}
return nxt[x][y] = {x, G[x][__builtin_ctz(y)], 0};
}
int sum[N], to[N << 1];
vector<int> tG[N << 1];
int deg[N << 1];
vector<int> ptr;
void dfs(int x) {
ptr.push_back(x);
for (auto v : tG[x]) dfs(v);
}
vector<int> arr[N << 1];
pair<int, int> pid[N << 1];
int ID(int x, int y) {
return sum[x - 1] + __builtin_ctz(id(x, y)) + 1;
}
int walk(int x, int y, int c) {
if (!c) return x;
vector<int> z = adj(x, y);
int tid = ID(x, z[0]);
return arr[pid[tid].first][pid[tid].second + c - 1];
}
int dp1[N], dp2[N], dp3[N];
// Ban Y.
int _F(int x, int y); // $x = 1
int _G(int x, int y, int X, int Y); // $x = 1, $X = 2
int _H(int x, int y, int L); // H1 + H2
int _H1(int x, int y, int L); // $x = 1, $head(L) = 2, $tail(L) = MAX
int _H2(int x, int y, int L); // $x = 2, $head(L) = 1, $tail(L) = MAX
int _F(int x, int y) {
if (~f[x][y]) return f[x][y];
if (G[x].size() - cnt[y] == 0) return f[x][y] = 1;
if (G[x].size() - cnt[y] == 1) {
auto [a, b, c] = getNxt(x, y);
if (!a) return dp1[c + 1];
vector<int> z = adj(a, id(a, b));
if (z.size() == 3) {
int res = 0;
sort(z.begin(), z.end());
do {
res = mod(res + 1ll * _G(z[0], id(z[0], a), z[1], id(z[1], a)) * _H(z[2], id(z[2], a), c));
} while (next_permutation(z.begin(), z.end()));
return f[x][y] = res;
}
int res = 0;
sort(z.begin(), z.end());
do {
vector<int> tz = adj(z[0], id(z[0], a));
res = mod(res + 1ll * _G(z[0], id(z[0], a), z[1], id(z[1], a)) * (dp2[c] + dp3[c])); // $z[0] = x + 1, $z[1] = x + 2, $b = x - 2 or x - 1 expect ↓
for (auto v : tz) {
if (v == z[0]) continue;
res = mod(res + 1ll * _H1(v, id(v, z[0]), c) * _G(z[0], id(z[0], a) | id(z[0], v), z[1], id(z[1], a))); // $z[0] = x + 1, $z[1] = x + 2, $b = x - 2, x - 1 IN Subtree(z[0])
}
if (c != 1) res = mod(res + 1ll * _F(z[1], id(z[1], a)) * _H2(z[0], id(z[0], a), c - 1)); // $z[0] = x - 2, $z[1] = x + 2, $b = x + 1
res = mod(res + 1ll * _H(z[0], id(z[0], a), c) * _F(a, id(a, b) | id(a, z[0]))); // $z[1] = x + 1 or x + 2, ($z[0], $b) = (x - 2, x - 1) expect ↓
for (auto v : tz) {
if (v == z[0]) continue;
res = mod(res + 1ll * _H1(z[0], id(z[0], a) | id(z[0], v), c) * _G(v, id(v, z[0]), z[1], id(z[1], a))); // $z[0] = x - 1, $z[1] = x + 2, $b = x - 2, x + 1 IN Subtree(z[0])
}
} while (next_permutation(z.begin(), z.end()));
return f[x][y] = res;
}
if (G[x].size() - cnt[y] == 2) {
vector<int> z = adj(x, y);
return f[x][y] = mod(_G(z[0], id(z[0], x), z[1], id(z[1], x)) + _G(z[1], id(z[1], x), z[0], id(z[0], x)));
}
return f[x][y] = 0;
}
int _G(int x, int y, int X, int Y) {
if (G[x].size() - cnt[y] == 0) return _F(X, Y);
if (G[x].size() - cnt[y] >= 2) return 0;
if (G[X].size() - cnt[Y] == 0) {
vector<int> z = adj(x, y);
return _F(z[0], id(z[0], x));
}
if (G[X].size() - cnt[Y] >= 2) return 0;
auto [a, b, c] = getNxt(x, y);
auto [A, B, C] = getNxt(X, Y);
int ta = walk(x, y, min(c, C)), tb = walk(x, y, min(c, C) - 1),
tA = walk(X, Y, min(c, C)), tB = walk(X, Y, min(c, C) - 1);
return _G(ta, id(ta, tb), tA, id(tA, tB));
}
int _H(int x, int y, int L) {
return mod(_H1(x, y, L) + _H2(x, y, L));
}
int _H1(int x, int y, int L) {
if (G[x].size() - cnt[y] == 0) return dp2[L];
if (G[x].size() - cnt[y] >= 2) return 0;
if (L == 1) return 0;
auto [a, b, c] = getNxt(x, y);
int ta = walk(x, y, min(c, L - 1)), tb = walk(x, y, min(c, L - 1) - 1);
return _H1(ta, id(ta, tb), L - min(c, L - 1));
}
int _H2(int x, int y, int L) {
if (L == 1) return 0;
if (G[x].size() - cnt[y] == 0) return dp2[L - 1];
if (G[x].size() - cnt[y] >= 2) return 0;
auto [a, b, c] = getNxt(x, y);
int ta = walk(x, y, min(c, L - 1)), tb = walk(x, y, min(c, L - 1) - 1);
return _H2(ta, id(ta, tb), L - min(c, L - 1));
}
signed main() {
int n; scanf("%d", &n);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (G[i].size() > 4) return 0 & puts("0");
for (int j = 0; j < 1 << 4; ++j) nxt[i][j] = {-1, -1, -1};
}
for (int i = 1; i < 1 << 4; ++i) {
cnt[i] = cnt[i >> 1] + (i & 1);
}
dp1[1] = dp1[2] = 1, dp1[3] = 2;
for (int i = 4; i <= n; ++i) dp1[i] = mod(dp1[i - 3] + dp1[i - 1] + 1);
dp2[1] = dp2[2] = dp2[3] = 1;
for (int i = 4; i <= n; ++i) dp2[i] = mod(dp2[i - 3] + dp2[i - 1]);
dp3[1] = dp3[2] = 0, dp3[3] = 1;
for (int i = 4; i <= n; ++i) dp3[i] = mod(dp3[i - 3] + dp3[i - 1]);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + G[i].size();
for (auto v : G[i]) to[ID(i, v)] = v;
}
for (int i = 1; i <= n; ++i) {
for (auto v : G[i]) {
if (G[v].size() != 2) continue;
tG[ID(i, v)].push_back(ID(v, adj(v, id(v, i))[0]));
}
}
int m = (n - 1) * 2;
for (int i = 1; i <= m; ++i) {
for (auto v : tG[i]) ++deg[v];
}
int r = 0;
for (int i = 1; i <= m; ++i) {
if (deg[i]) continue;
ptr.clear(), dfs(i), ++r;
for (int j = 0; j < (int)ptr.size(); ++j) {
pid[ptr[j]] = {r, j};
arr[r].push_back(to[ptr[j]]);
}
}
memset(f, -1, sizeof(f));
int res = 0;
for (int i = 1; i <= n; ++i) {
res = mod(res + _F(i, 0));
}
printf("%d\n", (res % P + P) % P);
return 0;
}
浙公網(wǎng)安備 33010602011771號