Mục tiêu là tính số lượng các rừng cây cơ bản không đánh số có kích thước n và giới hạn độ vào không vượt quá k.
Đặt N=n, K=k. Độ phức tạp của thuật toán là O(n^3 log n).
Tính dp_n biểu diễn số cách tạo cây không đánh số với n đỉnh thỏa mãn giới hạn độ số.
Sau đó, liệt kê kích thước của chu trình, sử dụng nguyên lý Burnside để tính số cây cơ bản không đánh số kích thước n với giới hạn độ số, ghi nhận là tr_n.
Cuối cùng, đếm số lượng rừng cây cơ bản kích thước n, ký hiệu là ans_n.
Bước 1
\[dp_{n}=[x^{n-1}]\prod_{i=1}^{\infty}(\frac{1}{1-x^i})^{dp_i} \]
Phương trình trên sử dụng hàm sinh để mô tả cấu trúc này một cách hiệu quả.
Đối với mỗi cây, liệt kê tất cả các con và cây con tương ứng.
\( \frac{1}{1-x^i}=0+x^i+x^{2i}+x^{3i}+\cdots \) giúp nhóm các con giống nhau lại để đảm bảo tính chất không đánh số.
Lũy thừa \( dp_i \) liên quan đến việc xét các cấu trúc khác nhau, trong khi \( i \) đại diện cho các kích thước khác nhau.
Xét thêm giới hạn về độ số, cần thêm một biến \( y \).
\[dp_n=\sum_{k\le K}[x^{n-1}y^k]\prod_{i=1}^{\infty}(\frac{1}{1-x^iy})^{dp_i} \]
\[dp_n=[x^{n-1}y^K](\prod_{i=1}^{\infty}(\frac{1}{1-x^iy})^{dp_i})\cdot\frac{1}{1-y} \]
Độ phức tạp của việc thực hiện túi đồ một cách đơn giản. \( dp_i \) có thể rất lớn, không thể liệt kê trực tiếp, nhưng hệ số trong định lý nhị thức có thể được tính bằng tổ hợp.
\[w_t=[x^{ti}y^t](\frac{1}{1-x^iy})^{dp_i} \]
\[w_t=\binom{t+dp_i-1}{dp_i-1}=\binom{t+dp_i-1}{t} \]
Tương đương với việc xác định số lượng phần tử \( t \) được lấy từ một phương án cụ thể, tức là phân phối \( t \) số vào \( dp_i \) hộp có thể chứa 0 phần tử.
Lưu ý rằng \( dp_i \) có thể cực kỳ lớn, việc lấy modulo \( p \) vẫn đúng.
\[\binom{w}{t}=\binom{w/p}{t/p}\binom{w\%p}{t\%p} \]
Lưu ý rằng \( t \) thực sự rất nhỏ so với \( p \), do đó \( \binom{w/p}{t/p}=1 \). Việc lấy modulo trong quá trình tính \( dp \) là hợp lý.
Để chuẩn bị cho phần thứ hai, cần điều chỉnh giá trị của \( dp \) vì nút gốc cuối cùng sẽ nằm trên chu trình của cây cơ bản, do đó sẽ có một độ vào. Kết quả cần tính là số lượng con của cây nhỏ hơn hoặc bằng \( k-1 \).
\[dp'_n=[x^{n-1}y^{K-1}](\prod_{i=1}^{\infty}(\frac{1}{1-x^iy})^{dp_i})\cdot\frac{1}{1-y} \]
void tinhdp() {
static ll f[N][N]; dp[1] = 1;
for (int i = 0; i <= kk; i++) f[0][i] = 1;
for (int n = 1; n <= nn; n++) {
vector<node> a;
for (int j = n, t = 1; j <= nn; j += n, t++)
a.push_back({ t, C(t + dp[n] - 1, t) });
for (int x = nn; x >= 0; x--) for (int y = kk; y >= 0; y--)
for (auto [i, cnt] : a) if (i * n <= x && i <= y)
(f[x][y] += f[x - i * n][y - i] * cnt) %= mod;
dp[n + 1] = f[n][kk];
}
for (int i = 1; i <= nn; i++) dp[i] = f[i - 1][kk - 1];
}
Bước 2
Trong phần thứ hai, sử dụng nguyên lý Burnside.
\[|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]
\[tr_n=\sum_{h=1}^n\frac{1}{h}\sum_{t}F(gcd(h,t),\frac{ngcd(h,t)}{h}) \]
\[tr_n=\sum_{h=1}^n\frac{1}{h}\sum_{d|h}[h|nd]F(d,\frac{nd}{h})\varphi(\frac{h}{d}) \]
\(F(n,m)\) biểu thị số cách phân bổ \(n\) vị trí, mỗi vị trí chứa một cây có kích thước \(a_i\) sao cho tổng \(a_i=m\), với số cách là tích của \(dp_{a_i}\).
Tính trực tiếp.
\[F(n,m)=\sum_{i=0}^ndp_i\cdot F(n-1,m-i) \]
void tinhh() {
f[0][0] = 1;
for (int i = 1; i <= nn; i++)
for (int k = 1; k <= nn; k++)
for (int t = 1; t <= nn; t++) if (k >= t)
(f[i][k] += f[i - 1][k - t] * dp[t]) %= mod;
}
void tinhtc() {
for (int n = 1; n <= nn; n++)
for (int h = 1; h <= n; h++) {
const ll inv = powmod(h, mod - 2); ll sum = 0;
for (int d = 1; d <= n; d++) if (h % d == 0 && (n * d) % h == 0)
sum = (sum + f[d][n * d / h] % mod * phi[h / d]) % mod;
tr[n] = (tr[n] + sum * inv) % mod;
}
}
Bước 3
Cuối cùng, chỉ cần ghép các cây cơ bản thành một rừng.
\[ans_{n}=[x^{n}]\prod_{i=1}^{\infty}(\frac{1}{1-x^i})^{tr_i} \]
Đây chính là phương trình trong Bước 1. Cách tính và lý do tương tự.
void tinhrung() {
static ll f[N]; f[0] = 1;
for (int n = 1; n <= nn; n++) {
vector<node> a;
for (int j = n, t = 1; j <= nn; j += n, t++)
a.push_back({ t, C(t + tr[n] - 1, t) });
for (int x = nn; x >= 0; x--)
for (auto [i, cnt] : a) if (i * n <= x)
(f[x] += f[x - i * n] * cnt) %= mod;
ans[n] = f[n];
}
}