#include <bits/stdc++.h>
#define ll long long
#define R register
#define mk(x,y) make_pair(x,y)
#define PII pair<int,int>
using namespace std;
const int N = 2005, mod = 1e9 + 7, inv2 = (mod + 1 >> 1);
inline ll qmul(ll a, ll b) {
    ll ans = 1;

    while (b) {
        if (b & 1)
            ans = ans * a % mod;

        a = (a * a) % mod;
        b >>= 1;
    }

    return ans;
}
inline ll inv(int x) {
    return qmul(x, mod - 2);
}
struct Vector {
    ll k, b;
} a[N];
int n, k;
ll f[N][N];
inline int find(int x, int all) {
    return ((x - 1) % all + all) % all + 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    f[1][1] = 1;

    for (R int i = 2; i <= n; ++i) {
        int tk = find(k, i);
        int t = __gcd(i, tk), wei;

        for (R int rst = 1; rst <= t; ++rst) {
            ll K = 1, B = 0, wei = find(rst + tk, i);

            do {
                if (wei == tk)
                    a[wei] = {K *inv2 % mod, B *inv2 % mod};
                else
                    a[wei] = {K *inv2 % mod, (f[i - 1][find(wei - tk, i)] + B) *inv2 % mod};

                K = a[wei].k, B = a[wei].b;

                wei = find(wei + tk, i);
            } while (wei != find(rst + tk, i));

            ll x = (mod - B * inv(K - 1) % mod) % mod;
            f[i][rst] = x;
            wei = find(rst + tk, i);

            while (wei != rst) {
                f[i][wei] = (a[wei].k * x % mod + a[wei].b) % mod;
                wei = find(wei + tk, i);
            }
        }
    }

    cout << f[n][1];
    return 0;
}

约瑟夫环存活概率问题题解

题目分析

n 个人逆时针排成环，从编号 1 开始逆时针报数，报到 k 的人有 $\frac{1}{2}$ 概率出局。无论是否出局，下一个人从 1 开始继续报数。求编号 1 最后存活的概率，结果对 $10^9+7$ 取模。

核心难点：

1. $k$ 可达 $10^9$，无法模拟报数过程；
2. 存活概率涉及无穷级数（如样例），需通过数学转化为有限方程求解；
3. 环结构的周期性与状态转移的依赖关系，需高效优化。

算法标签

• 动态规划（DP）
• 约瑟夫环问题
• 数论（gcd、逆元、快速幂）
• 线性方程组求解
• 循环分块优化

动态规划模型

状态定义

设 $f[i][j]$ 表示 i 个人围成环时，编号 j 的人最后存活的概率。

• 边界条件：$f[1][1] = 1$（1 个人时必然存活）；
• 目标答案：$f[n][1]$（n 个人时编号 1 的存活概率）。

关键推导与优化

1. 报数目标位置的周期性

由于环长为 i，报数到 k 的位置具有周期性，可简化为：

$$tk = ((k-1) \mod i) + 1$$

即 i 人环中第一次报数的目标位置（后续报数目标位置按环周期重复）。

2. 环的循环分块（gcd 优化）

每次报数跳 tk 步，在 i 人环中会形成 t 个独立循环，其中 $t = \gcd(i, tk)$。

• 每个循环的长度为 $\frac{i}{t}$，循环间互不影响，可独立求解；
• 分循环处理后，时间复杂度从 $O(n^3)$ 降至 $O(n^2)$（n≤2000 可承受）。

3. 状态转移方程（线性关系推导）

对于 i 人环中的位置 j，第一次报数目标为 tk，分两种情况推导转移关系：

情况 1：j == tk（当前位置是报数目标）

• 有 $\frac{1}{2}$ 概率出局，贡献 0；
• 有 $\frac{1}{2}$ 概率留下，后续存活概率依赖下一个报数周期的状态（即循环中下一个位置的 $f[i][·]$）。
• 转移关系：$f[i][j] = \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot f[i][next_j]$，整理为线性形式：$$f[i][j] = inv2 \cdot f[i][next_j] + 0$$ 其中 $inv2 = 500000004$（$\frac{1}{2}$ 对 $10^9+7$ 的逆元），$next_j$ 是循环中下一个位置。

情况 2：j != tk（当前位置不是报数目标）

• 有 $\frac{1}{2}$ 概率 tk 出局，进入 i-1 人环，j 对应的 i-1 人环位置为 $pos = ((j - tk - 1) \mod (i-1)) + 1$（位置映射），贡献 $\frac{1}{2} \cdot f[i-1][pos]$；
• 有 $\frac{1}{2}$ 概率 tk 留下，后续存活概率依赖循环中下一个位置的 $f[i][·]$。
• 转移关系：$f[i][j] = \frac{1}{2} \cdot f[i-1][pos] + \frac{1}{2} \cdot f[i][next_j]$，整理为线性形式：$$f[i][j] = inv2 \cdot f[i][next_j] + (inv2 \cdot f[i-1][pos]) $$

4. 线性方程组求解

每个循环中的所有位置 $f[i][j]$ 可表示为线性关系：$f[i][j] = k_j \cdot x + b_j$（x 为循环中基准位置的概率值）。

• 遍历循环建立所有线性表达式，形成闭环方程 $x = K \cdot x + B$；
• 求解基准值：$x = B \cdot inv(1 - K) \mod mod$（逆元处理模运算）；
• 回代所有线性表达式，得到循环中所有位置的 $f[i][j]$。

代码解析

核心函数与变量

变量/函数	功能描述
$f[i][j]$	DP 状态：i 人环中位置 j 的存活概率
$tk$	i 人环中报数目标位置
$t = \gcd(i, tk)$	环的独立循环数
$inv2$	$\frac{1}{2}$ 的逆元（$10^9+7$ 模意义下）
$inv(x)$	快速幂求 x 的逆元（基于费马小定理）
$find(x, all)$	计算 x 在 all 个元素的环中的合法位置（避免越界）
Vector $a[wei]$	存储线性系数 $(k, b)$，即 $f[i][wei] = a[wei].k \cdot x + a[wei].b$

关键流程

1. 初始化：$f[1][1] = 1$（边界条件）。
2. 迭代人数 i 从 2 到 n：
   • 计算 i 人环的报数目标位置 $tk$；
   • 分循环处理（按 $\gcd(i, tk)$ 划分循环）；
   • 每个循环内建立线性表达式，求解基准值并回代得到 $f[i][j]$。
3. 输出答案：$f[n][1]$。

代码片段详解

线性表达式建立（循环内）

do {
    if (wei == tk)
        a[wei] = {K * inv2 % mod, B * inv2 % mod};
    else
        a[wei] = {K * inv2 % mod, (f[i - 1][find(wei - tk, i)] + B) * inv2 % mod};
    K = a[wei].k, B = a[wei].b;
    wei = find(wei + tk, i);
} while (wei != find(rst + tk, i));

• 遍历循环中每个位置，根据是否为报数目标，建立线性系数 $(K, B)$；
• $K$ 和 $B$ 迭代更新，传递线性关系至下一个位置。

基准值求解与回代

ll x = (mod - B * inv(K - 1) % mod) % mod;
f[i][rst] = x;
wei = find(rst + tk, i);
while (wei != rst) {
    f[i][wei] = (a[wei].k * x % mod + a[wei].b) % mod;
    wei = find(wei + tk, i);
}

• 闭环方程求解基准值 $x$（模意义下处理负数）；
• 用 $x$ 回代所有线性表达式，得到循环内所有位置的 $f[i][wei]$。

时间复杂度分析

• 对于每个 i（2≤i≤n），环分为 $t = \gcd(i, tk)$ 个循环，总处理次数为 $\sum_{i=2}^n i = O(n^2)$；
• 每个操作（gcd、快速幂、线性表达式建立与回代）均为 $O(1)$；
• 整体时间复杂度：$O(n^2)$，适配 $n≤2000$ 的数据范围。

空间复杂度分析

• DP 数组 $f[i][j]$ 占用 $O(n^2)$ 空间（n≤2000，约 400 万存储单元，可接受）；
• 辅助数组（线性系数 $a$、循环栈等）占用 $O(n)$ 空间；
• 整体空间复杂度：$O(n^2)$。