20231105题解
glass
brute_force
这种题目显然可以容斥。考虑状态压缩，用一个长度为 \(n\) 的二进制数表示状态，其中第 \(i\) 位为 0 表示钦定这一层不能放 AC。
容易发现，如果状态是 \(k\)，这种假设下 AC 正好有 \(k\) 个结点可以放。则答案为：
\[ \sum_{i=0}^{2^n-1}{(-1)^{n - \operatorname{popcount}(i)}i^m} \]
我们用 \(\operatorname{popcount}(i)\) 表示 \(i\) 的二进制中 1 的个数，并简写成 \(p(i)\)。
直接计算，复杂度 \(\mathcal{O}(n^2 \log m)\)。1
2
3
4
5
6
7
8
9
10
11
12namespace brute_force {
long long ans;
void solve() {
long long ans = 0;
for (int i = 0; i < (1 << n); i++) {
int k = __builtin_popcount(i);
if ((n - k) & 1) ((ans -= quick_pow(i, m)) += mod) %= mod;
else (ans += quick_pow(i, m)) %= mod;
}
printf("%lld\n", ans);
}
}
optimize
考虑 dp 上述柿子。
设 \(f_{i, j}=\sum_{x=0}^{2^i - 1}{(-1)^{n-p(x)}x^j}\)。
考虑 \(f_i \to f_{i+1}\)：
\[ \begin{aligned} f_{i+1, j}&=\sum_{x=0}^{2^{i+1}-1}{(-1)^{n-p(x)}x^j} \\ &= \sum_{x=0}^{2^i-1}{(-1)^{n-p(x)}x^j} + \sum_{x=0}^{2^i - 1}(-1)^{n-p(x)-1}(x + 2^i)^j \\ &= f_{i, j}-\sum_{x=0}^{2^i-1}(-1)^{n-p(x)}\sum_{k=0}^j{x^k2^{i(j-k)}\tbinom{j}{k}} \\ &= f_{i, j} - \sum_{k=0}^j{2^{i(j-k)}\tbinom{j}{k}f_{i, k}} \end{aligned} \]
这样时间复杂度 \(\mathcal{O}(nm^2)\)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25namespace sub2to5 {
const int maxn = 5e2 + 5;
long long f[maxn][maxn], c[maxn][maxn], p2[maxn * maxn];
void solve() {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= i; j++) {
if (i == j || j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
p2[0] = 1;
for (int i = 1; i <= m * m; i++) p2[i] = p2[i - 1] * 2 % mod;
for (int i = 1; i <= m; i++) f[0][i] = (n & 1) ? 1 : -1;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k <= j; k++) {
((f[i][j] -= p2[i * (j - k)] * c[j][k] % mod * f[i - 1][k] % mod) += mod) %= mod;
}
}
}
// printf("%lld%c", f[n - 1][m], " \n"[m == 10]);
printf("%lld\n", f[n - 1][m]);
}
}
accept
之前那个柿子的关键是二项式展开。但是二项式展开似乎不一定要一个一个转移。我们考虑 \(f_i \to f_{2i}\)：
\[ \begin{aligned} f_{2i, j} &= \sum_{x=0}^{2^i-1}\sum_{y=0}^{2^i-1}{(-1)^{n-p(x)-p(y)}(x+2^iy)^j} \\ &= (-1)^n\sum_{x=0}^{2^i-1}\sum_{y=0}^{2^i-1}{(-1)^{n-p(x)}(-1)^{n-p(y)}\sum_{k=0}^j{x^k2^{i(j-k)}y^{j-k}\tbinom{j}{k}}} \\ &= \sum_{k=0}^j2^{i(j-k)}\tbinom{j}{k}(-1)^n\sum_{x=0}^{2^i-1}\sum_{y=0}^{2^i-1}{(-1)^{n-p(x)}(-1)^{n-p(y)}{x^ky^{j-k}}} \\ &= \sum_{k=0}^j2^{i(j-k)}\tbinom{j}{k}(-1)^nf_{i, k}f_{i, j-k} \end{aligned} \]
既然我们有了 \(f_i \to f_{i+1},f_i \to f_{2i}\)，我们就可以倍增了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41namespace accept {
const int maxn = 2e3 + 5;
long long f[maxn][maxn], c[maxn][maxn], p2[maxn * maxn];
bool vis[maxn];
void getf(int i) {
if (vis[i]) return;
int nxt = i >> 1;
getf(nxt);
int ti = nxt << 1;
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= j; k++) {
(f[ti][j] += c[j][k] * p2[nxt * k] * ((n & 1) ? -1 : 1) % mod * f[nxt][j - k] % mod * f[nxt][k] % mod + mod) %= mod;
}
} vis[ti] = true;
if (i != ti) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k <= j; k++) {
((f[i][j] -= p2[(i - 1) * (j - k)] * c[j][k] % mod * f[i - 1][k] % mod) += mod) %= mod;
}
} vis[i] = true;
} return;
}
void solve() {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= i; j++) {
if (i == j || j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
p2[0] = 1;
for (int i = 1; i <= m * m; i++) p2[i] = p2[i - 1] * 2 % mod;
// memset(vis, 0, sizeof vis);
// memset(f, 0, sizeof f);
for (int i = 1; i <= m; i++) f[1][i] = (n & 1) ? 1 : -1;
vis[1] = true;
getf(n);
// printf("%lld%c", f[n][m], " \n"[m == 10]);
printf("%lld\n", f[n][m]);
}
}