A
CF294C Shaass and Light
考虑初始已点亮的灯将所有剩下的灯划分成的连续段。除开头结尾外，每个长为 \(l\) 的连续段有 \(2 ^ l\) 种操作序列。开头结尾的连续段只有 \(1\) 种操作序列。从前往后将所有的操作序列归并到全局的操作序列里，拿组合数随便乱搞搞就好了。
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int P = 1e9 + 7;
int n, m;
int a[1005];
inline int qpow(int x, int y) {
if (y <= 0)
return 1;
int ret = 1;
while (y) {
if (y & 1)
ret = ret * x % P;
y >>= 1;
x = x * x % P;
}
return ret;
}
int inv[1005], ifac[1005], fac[1005];
inline int C(int n, int m) { return (n < m ? 0 : fac[n] * ifac[m] % P * ifac[n - m] % P); }
signed main() {
cin >> n >> m;
inv[0] = ifac[0] = fac[0] = inv[1] = ifac[1] = fac[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (P - P / i) * inv[P % i] % P;
fac[i] = fac[i - 1] * i % P;
ifac[i] = ifac[i - 1] * inv[i] % P;
}
for (int i = 1; i <= m; i++) cin >> a[i];
sort(a + 1, a + m + 1);
int res = n - m;
int ans = C(res, a[1] - 1);
res -= (a[1] - 1);
ans = ans * C(res, n - a[m]) % P;
res -= (n - a[m]);
for (int i = 2; i <= m; i++) {
ans = ans * qpow(2, a[i] - a[i - 1] - 2) % P;
ans = ans * C(res, a[i] - a[i - 1] - 1) % P;
res -= (a[i] - a[i - 1] - 1);
}
cout << ans;
return 0;
}
B
CF1753C Wish I Knew How to Sort
发现最终序列一定是前面全是 \(0\)，后面全是 \(1\)。设有 \(k\) 个 \(0\)，则我们判断是否排好序的标准就是前 \(k\) 个数里是否有 \(k\) 个 \(0\)。又发现操作后任意一段前缀里 \(0\) 的个数是单调不降的。于是可以设计出 dp 状态：\(dp[i]\) 表示前 \(k\) 个数里有 \(i\) 个 \(0\) 时的期望步数。最终答案即为 \(dp[k]\)。转移考虑期望经过多少步可以使得前 \(k\) 个数里的 \(0\) 增加。设当前前 \(k\) 个里共有 \(i\) 个 \(0\)，则要增加就必须选到前面的 \(1\) 和后面的 \(0\)。可以发现前面 \(1\) 的个数和后面 \(0\) 的个数都是 \(k - i\) 个。而总的选择方案共有 \(\binom{n}{2}\) 种。所以此时一次操作给前 \(k\) 个增加一个 \(0\) 的概率即为 \(\frac{(k - i) ^ 2}{\binom{n}{2}}\)，期望次数即为 \(\frac{\binom{n}{2}}{(k - i) ^ 2}\)。于是有 \(dp[i + 1] = dp[i] + \frac{\binom{n}{2}}{(k - i) ^ 2}\)。直接算即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
inline int qpow(int x, int y) {
int ret = 1;
while (y) {
if (y & 1)
ret = ret * x % P;
y >>= 1;
x = x * x % P;
}
return ret;
}
int dp[200005];
int a[200005];
signed main() {
int tc;
cin >> tc;
while (tc--) {
int n, k = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] ^= 1, k += a[i];
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
dp[a[k]] = 0;
int S = n * (n - 1) / 2;
for (int i = a[k] + 1; i <= k; i++) dp[i] = (dp[i - 1] + S % P * qpow((k - i + 1) * (k - i + 1), P - 2) % P) % P;
cout << dp[k] << "\n";
}
return 0;
}
C
CF1657E Star MST
题目限制等价于以 \(1\) 为中心的菊花是图的一棵 MST。也就是每个点到 \(1\) 的边权必须小于等于到其他点的边权，不然换成那条更小的边肯定可以使得 MST 的权值变小。于是可以考虑 dp。我们从小到大给每条与 \(1\) 相连的点赋权，定义 \(dp[i][j]：\) 已经给 \(i\) 个点的与 \(1\) 相连的边赋了权，最后一次赋权赋的是 \(j\) 的方案数。考虑转移。对于一个 \(dp[i][j]\)，我们枚举给几个点（边）赋上 \(j\) 的权，记为 \(m\)。然后再枚举上次赋的是什么权，记为 \(x\)。再记 \(t = i - m\)，则 \(dp[i][j]\) 可以从 \(dp[t][x]\) 转移。考虑转移系数。显然我们要先在剩下的 \(n - t\) 个点里选出 \(i - t\) 个赋权。然后要在这选出的 \(i - t\) 个点里相互连边，还要向前面的 \(t - 1\) 个点连边（减 \(1\) 是因为不用考虑向 \(1\) 连）。新连的边的权值必然是要大于等于 \(j\) 的（因为其有一个端点向 \(1\) 连了权为 \(j\) 的边），于是每条边有 \(k - j + 1\) 种选权值的方案。总共是 \(\binom{n - t}{i - t}(k - j + 1)^{(\frac{(i - t)(i - t - 1)}{2} + (i - t)(t - 1))}\)，这就是转移系数。上面那个指数可以化简变成 \(\frac{(i - t)(i + t - 3)}{2}\)，于是转移：\(dp[i][j] = \sum\limits_{t = 1}^{i - 1}(\sum\limits_{x = 0}^{k})\binom{n - t}{i - t}(k - j + 1)^{\frac{(i - t)(i + t - 3)}{2}}\)。使用前缀和优化即可做到 \(O(n^3)\)。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
int f[255][255];
int g[255][255];
int inv[255], ifac[255], fac[255];
inline void Cpre(int n) {
inv[0] = ifac[0] = fac[0] = inv[1] = ifac[1] = fac[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (P - P / i) * inv[P % i] % P;
fac[i] = fac[i - 1] * i % P;
ifac[i] = ifac[i - 1] * inv[i] % P;
}
}
inline int C(int n, int m) { return n < m || n < 0 || m < 0 ? 0 : fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int qpow(int x, int y) {
int ret = 1;
while (y) {
if (y & 1)
ret = ret * x % P;
y >>= 1;
x = x * x % P;
}
return ret;
}
signed main() {
int n, K;
cin >> n >> K;
Cpre(max(n, K));
f[1][0] = 1;
for (int i = 0; i <= K; i++) g[1][i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= K; j++) {
for (int t = 1; t < i; t++)
f[i][j] = (f[i][j] + g[t][j - 1] * C(n - t, i - t) % P * qpow(K - j + 1, (i - t) * (i + t - 3) / 2) % P) % P;
g[i][j] = (g[i][j - 1] + f[i][j]) % P;
}
}
cout << g[n][K];
return 0;
}