F. Sonya and Informatics - 题解
比赛与标签
比赛: Codeforces Round 553 (Div. 2) 标签: combinatorics, dp, matrices, probabilities 难度: *2300
题目大意喵~
主人 sama，你好呀！这道题是关于一个只包含 0 和 1 的数组 a 的说。
题目会给我们一个长度为 n 的数组 a 和一个整数 k。接下来会进行 k 次操作，每次操作都会做下面这件事：
- 等概率地随机选择两个不同的下标
i和j（1 <= i < j <= n）。 - 交换
a[i]和a[j]的值。
我们的任务是，计算经过这 k 次操作之后，数组 a 变得非递减有序（也就是所有的 0 都在所有的 1 前面）的概率是多少呢？最后要把这个概率对 10^9 + 7 取模后输出，喵~
解题思路大揭秘！
当本喵看到 k 的值可以达到 10^9 这么大时，就知道这一定不是一道简单的模拟题啦！这种“进行 k 次操作后达到某个状态的概率”的问题，通常都和动态规划（DP）以及矩阵快速幂有关哦，呐。
Step 1: 状态的定义与简化
首先，我们来想一想，什么决定了数组的状态呢？是数组里每个 0 和 1 的具体位置吗？其实不是哦！因为最终的目标状态是唯一的：所有的 0 都排在前面，所有的 1 都排在后面。
假设数组里一共有 m 个 0 和 n-m 个 1。那么，最终的有序状态就是前 m 个位置都是 0，后 n-m 个位置都是 1。
所以，我们可以用一个更简单的量来描述数组的“有序程度”。一个绝妙的状态定义是：“数组前 m 个位置中，0 的数量”。我们把这个数量记为 x。
- 当
x = m时，说明前m个位置全都是0，这意味着整个数组已经有序了！这就是我们的目标状态。 - 初始时，我们可以数一下给定的数组
a的前m个位置里有多少个0，这就是我们的初始状态x0。
x 的取值范围是多少呢？
x最多是m（前m个位置全是0）。x最少是多少呢？我们来分析一下：- 前
m个位置有x个0和m-x个1。 - 后
n-m个位置就有m-x个0和(n-m) - (m-x) = n-2m+x个1。 - 因为
1的数量不能是负数，所以n-2m+x >= 0，也就是x >= 2m-n。 - 所以
x的最小值为max(0, 2m-n)。
- 前
这样，我们就把一个复杂的数组状态，简化成了一个整数 x，状态的总数也大大减少了，最多只有 n+1 种可能，真棒！
Step 2: 状态转移概率
接下来，我们来分析一次随机交换操作后，状态 x 是如何变化的。
总共有 C(n, 2) = n * (n-1) / 2 种不同的交换方式，每种方式都是等概率的。
我们来分析交换 a[i] 和 a[j] 对 x 的影响：
x增加 1 (x -> x+1): 这需要我们把一个在前m个位置的1，和后n-m个位置的0进行交换。- 前
m个位置有m-x个1。 - 后
n-m个位置有m-x个0。 - 所以，能让
x增加 1 的交换方式有(m-x) * (m-x)种。 - 概率
P(x -> x+1) = (m-x)^2 / (n(n-1)/2)。
- 前
x减少 1 (x -> x-1): 这需要我们把一个在前m个位置的0，和后n-m个位置的1进行交换。- 前
m个位置有x个0。 - 后
n-m个位置有n-2m+x个1。 - 所以，能让
x减少 1 的交换方式有x * (n-2m+x)种。 - 概率
P(x -> x-1) = x * (n-2m+x) / (n(n-1)/2)。
- 前
x不变 (x -> x): 除了上面两种情况，其他所有的交换都不会改变x的值。- 概率
P(x -> x) = 1 - P(x -> x+1) - P(x -> x-1)。
- 概率
Step 3: DP 与矩阵快速幂
现在我们有了状态和转移概率，就可以建立一个 DP 模型了！
令 dp[s][i] 表示经过 s 次操作后，系统处于状态 i（即 x 值为 i）的概率。 那么递推关系就是： dp[s][i] = dp[s-1][i-1] * P(i-1 -> i) + dp[s-1][i] * P(i -> i) + dp[s-1][i+1] * P(i+1 -> i)
这是一个线性的递推关系！因为 k 非常大，直接递推 k 次肯定会超时。这时候，就轮到我们的好朋友矩阵快速幂登场啦！
我们可以把这个递推过程写成矩阵的形式： V_s = V_{s-1} * T
其中：
V_s是一个行向量，V_s[i]表示经过s步后处于状态i的概率。T是一个转移矩阵，T[i][j]表示从状态i一步转移到状态j的概率。
经过 k 次操作后，最终的概率分布向量就是 V_k = V_0 * T^k。
V_0是初始概率向量，因为我们一开始就处在x0这个状态，所以V_0在对应x0的位置上是1，其他位置都是0。- 我们用矩阵快速幂算法在
O(S^3 * log k)的时间里计算出T^k，其中S是状态总数。
最终，我们想要的答案就是 V_k 中对应目标状态 x=m 的那个概率值！搞定~
代码实现喵
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// MOD 是题目要求的模数
const long long MOD = 1000000007;
// 快速幂函数，用来计算 (base^exp) % MOD，喵~
long long mod_exp(long long base, long long exp) {
long long result = 1;
base %= MOD;
while (exp) {
if (exp & 1)
result = (result * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return result;
}
// 费马小定理求逆元，因为 MOD 是质数，所以 a^(MOD-2) 就是 a 的逆元
long long inv(long long x) {
return mod_exp(x, MOD-2);
}
// 矩阵乘法函数，计算 A * B
vector<vector<long long>> mat_mult(vector<vector<long long>> A, vector<vector<long long>> B) {
int n = A.size();
int p = B.size();
int m = B[0].size();
vector<vector<long long>> C(n, vector<long long>(m, 0));
for (int i = 0; i < n; i++) {
for (int k = 0; k < p; k++) {
if (A[i][k]) { // 一个小优化，如果 A[i][k] 是0就不用算了
for (int j = 0; j < m; j++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
}
}
}
}
return C;
}
// 矩阵快速幂，计算 base^exponent
vector<vector<long long>> mat_exp(vector<vector<long long>> base, long long exponent) {
int n = base.size();
// result 初始化为单位矩阵
vector<vector<long long>> result(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++)
result[i][i] = 1;
while (exponent) {
if (exponent & 1)
result = mat_mult(result, base);
base = mat_mult(base, base);
exponent /= 2;
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n, k;
cin >> n >> k;
vector<long long> a(n);
long long m = 0; // m 是数组中 0 的总数
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] == 0) m++;
}
// x0 是初始状态：前 m 个位置中 0 的数量
long long x0 = 0;
for (int i = 0; i < m; i++) {
if (a[i] == 0) x0++;
}
// low 是状态 x 的最小值
long long low = max(0LL, 2*m - n);
// num_states 是状态的总数
long long num_states = m - low + 1;
// 如果不可能达到有序状态（比如初始就没有0，m=0），直接输出1（因为已经有序了）
// 不过题目数据保证了 n>=2，这种情况在代码里处理了。
// 如果 m=0 或 m=n，数组已经有序，概率是1。代码中 x0=m，num_states=1，最终结果也是1。
// 总的交换对数
long long total_swaps = n * (n-1) / 2;
// 预计算总交换对数的逆元
long long inv_den = inv(total_swaps);
// 构建转移矩阵 T
vector<vector<long long>> T(num_states, vector<long long>(num_states, 0));
for (int i = 0; i < num_states; i++) {
long long x = low + i; // 当前状态对应的 x 值
// 计算 x -> x-1 的分子
long long numerator_down = 0;
if (x > low) {
numerator_down = x * (n - 2*m + x);
}
// 计算 x -> x+1 的分子
long long numerator_up = 0;
if (x < m) {
numerator_up = (m - x) * (m - x);
}
// 计算 x -> x 的分子
long long numerator_stay = total_swaps - numerator_down - numerator_up;
// 填充转移矩阵 T，注意要乘以逆元
if (x > low) {
T[i][i-1] = numerator_down % MOD * inv_den % MOD;
}
if (x < m) {
T[i][i+1] = numerator_up % MOD * inv_den % MOD;
}
T[i][i] = numerator_stay % MOD * inv_den % MOD;
}
// 计算 T^k
vector<vector<long long>> Tk = mat_exp(T, k);
// 初始状态向量 v0，在 x0 对应的位置是1
long long idx0 = x0 - low;
// 最终的答案就是从初始状态 idx0 转移到目标状态 (num_states-1) 的概率
// 也就是 T^k 矩阵的第 idx0 行，第 (num_states-1) 列的元素
long long ans = Tk[idx0][num_states-1];
if (ans < 0) ans += MOD;
cout << ans << endl;
return 0;
}复杂度分析的说
- 时间复杂度: O(n^3 * log k) 的说。 这里的
n实际上是我们状态空间的大小，也就是num_states。因为num_states <= n+1，所以状态空间的规模是O(n)。矩阵乘法的时间复杂度是O(n^3)，矩阵快速幂需要进行O(log k)次矩阵乘法。所以总的时间复杂度就是O(n^3 * log k)啦！ - 空间复杂度: O(n^2) 的说。 我们需要存储几个
num_states * num_states的矩阵，所以空间复杂度是O(n^2)。
知识点与总结
这道题真是一次有趣的冒险呢，主人 sama！通过解决它，我们可以学到很多东西哦：
- 概率 DP: 面对涉及概率和多次操作的问题时，要首先想到 DP。关键是找到一个合适的、能描述系统演化过程的状态。
- 状态压缩/简化: 不要被问题的表面迷惑！有时候一个复杂的状态（比如整个数组）可以被一个或几个关键变量（比如这里的
x）来表示，大大减小状态空间。 - 矩阵快速幂: 当 DP 的转移是线性的，并且转移次数
k非常大时，矩阵快速幂就是我们的屠龙宝刀！它可以把O(k)的线性递推优化到O(log k)的级别。 - 组合数学: 计算状态转移概率时，需要一些基本的组合计数能力，要仔细分析各种情况，不能数错哦。
总而言之，这是一道融合了概率、DP和矩阵代数的经典好题。只要能正确地定义状态、推导出转移概率，再用矩阵快速幂加速，问题就迎刃而解啦！希望这篇题解能帮到你，喵~ ❤️