一、问题核心分析

1. 问题转化

车在时刻 ( k )（( k \in [0, 2019!] ) 均匀随机）出发，速度 1m/s，到达第 ( i ) 个信号灯的时间为 ( k + x_i )（( x_i ) 为信号灯位置）。需计算：

• 第 ( i ) 个信号灯是首次遇到红灯的概率；
• 顺利通过所有信号灯的概率。

核心条件（首次在第 ( i ) 个灯遇红灯）：

1. 到达第 ( i ) 个灯时，灯为红灯：( (k + x_i) \mod T_i \in [0, r_i) )（( T_i = r_i + g_i ) 为周期）；
2. 到达前 ( i-1 ) 个灯时，灯均为绿灯：对所有 ( j < i )，( (k + x_j) \mod T_j \in [r_j, T_j) )。

2. 关键观察

( 2019! ) 是所有 ( T_i )（( T_i \leq 100 \leq 2019 )）的公倍数，因此 ( k ) 在模 ( T_i ) 下的分布均匀。且 ( k ) 的约束条件可通过模运算转化为有限状态空间的筛选，无需遍历无穷区间。

二、核心思路

1. 周期压缩：利用 ( 2019! ) 的公倍数特性，将 ( k ) 的约束转化为“小模空间”（模 2520 + 分组周期）的状态筛选。2520 是 1~10 的最小公倍数，覆盖了 ( T_i ) 的核心因子；
2. 分组处理：将 ( T_i ) 按其因子特性分组，每组对应一个“大周期”因子，通过乘法原理计算各组有效状态的联合概率；
3. 状态动态更新：处理每个信号灯时，更新“满足前 ( i ) 个灯均为绿灯”的有效状态集合；
4. 累积概率计算：用累积概率差求解“首次遇红灯”的概率（如通过前 ( i-1 ) 个灯的概率 - 通过前 ( i ) 个灯的概率 = 首次在第 ( i ) 个灯遇红灯的概率）。

三、算法实现细节

1. 预处理：分组与周期初始化

代码首先对 ( 1 \sim 100 ) 的数进行分组（belong 数组），核心目的是将不同 ( T_i ) 的周期因子归类，便于后续乘法原理计算：

• 筛选素数，对每个素数计算其最高次幂和分组阈值；
• 每个分组对应一个“大周期”因子（tong 数组），相同因子特性的 ( T_i ) 归入同一组；
• 初始化 used（状态有效性）、cnt（有效状态数）、rcnt（总状态数）数组，记录每组的初始状态。

2. 核心逻辑：处理每个信号灯

对每个信号灯 ( i )，需更新“通过前 ( i ) 个灯”的有效状态：

1. 计算约束条件：

   • 绿灯条件：( (k + x_i) \mod T_i \in [r_i, T_i) )，转化为 ( k \mod T_i \in [w, w + g_i) )（( w = (r_i - x_i \mod T_i + T_i) \mod T_i )）；
   • 利用 ( \gcd(T_i, 2520) ) 和 ( \gcd(T_i, 分组周期) )，将约束转化为“同余类筛选”（vis 数组标记有效状态）。

2. 更新有效状态：

   • 将当前信号灯的约束施加到全局状态（used 数组与 vis 数组按位与）；
   • 重新计算当前分组的有效状态数（cnt 数组）。

3. 计算累积概率：

   • 每个模 2520 的剩余类是等概率的（概率 ( 1/2520 )）；
   • 各组有效状态占比的乘积（乘法原理）为该剩余类的有效概率；
   • 累积所有剩余类的概率，得到“通过前 ( i ) 个灯”的概率（ans[i]）。

3. 答案计算

• 首次在第 ( i ) 个灯遇红灯的概率 = 通过前 ( i-1 ) 个灯的概率 - 通过前 ( i ) 个灯的概率（即 ans[i-1] - ans[i]）；
• 顺利通过所有灯的概率 = ans[n]（通过前 ( n ) 个灯的概率）。

四、代码逐段解释

1. 工具函数

• read()：快速读入整数，优化输入效率；
• gcd()：计算最大公约数，用于周期分解和同余类筛选。

2. 预处理分组

for (int i = 2; i <= N; ++i)
    if (!nprime[i]) {
        // 计算素数 i 的最高次幂 x（≤100）和分组阈值 y
        x = y = 1, scnt = 0;
        while (x * i <= N) x *= i, scnt++;
        for (int j = 1; j <= (scnt >> 1) + 1; ++j) y *= i;
        tong[++length] = x;
        // 标记同组的数（周期因子特性相同）
        for (int j = y; j <= N; j += y) belong[j] = length;
        // 筛除合数
        for (int j = (i << 1); j <= N; j += i) nprime[j] = 1;
    }
// 未分组的数归入最后一组（周期因子为1）
tong[++length] = 1;
for (int i = 1; i <= N; ++i)
    if (!belong[i]) belong[i] = length;

3. 初始化状态数组

for (int i = 0; i < 2520; ++i)
    for (int j = 1; j <= length; ++j) {
        ds = gcd(tong[j], 2520);
        // 标记模 tong[j] 与模 2520 同余的状态（初始全部有效）
        for (int k = 0; k < tong[j]; ++k)
            used[i][j][k] = (k % ds == i % ds), cnt[i][j] += used[i][j][k], rcnt[i][j] += used[i][j][k];
    }

4. 处理每个信号灯

n = read(), ans[0] = 1; // ans[0] 为通过 0 个灯的概率（100%）
for (int i = 1; i <= n; ++i) {
    x = read(), r = read(), g = read();
    T = r + g;
    ds = gcd(T, 2520); // 模 2520 的约束步长
    dw = gcd(T, tong[belong[T]]); // 分组周期的约束步长
    memset(vis, 0, sizeof(vis));

    // 计算 k 需满足的绿灯条件对应的同余类
    w = (r - x % T + T) % T; // k mod T 的有效区间起点
    for (int k = w % ds; k < 2520; k += ds)
        for (int t = w % dw; t < tong[belong[T]]; t += dw)
            vis[k][t] = 1; // 标记有效状态

    // 更新当前分组的有效状态
    for (int j = 0; j < 2520; ++j) {
        cnt[j][belong[T]] = 0;
        for (int k = 0; k < tong[belong[T]]; ++k)
            used[j][belong[T]][k] &= vis[j][k], cnt[j][belong[T]] += used[j][belong[T]][k];
    }

    // 计算通过前 i 个灯的累积概率
    for (int j = 0; j < 2520; ++j) {
        res = 1.0;
        // 乘法原理：各组有效状态占比的乘积
        for (int k = 1; k <= length; ++k)
            res *= 1.0 * cnt[j][k] / rcnt[j][k];
        ans[i] += res / 2520.0; // 每个模 2520 剩余类的概率贡献
    }
}

5. 输出答案

for (int i = 0; i <= n; ++i)
    printf("%0.12lf\n", ans[i] - ans[i + 1]);
// ans[i] - ans[i+1]：首次在第 i 个灯遇红灯的概率（i=0 对应第 1 个灯）
// ans[n] - ans[n+1]（ans[n+1]=0）：通过所有灯的概率

五、复杂度分析

• 预处理复杂度：( O(100 \log 100 + 2520 \times 分组数 \times 最大分组周期) )，分组数和最大分组周期均为常数（≤20），预处理代价可忽略；
• 处理每个信号灯：( O(2520 \times 分组数 + 2520 \times 最大分组周期) )，( n \leq 500 )，总复杂度 ( O(n \times 2520 \times 分组数) )，完全可行；
• 空间复杂度：( O(2520 \times 分组数 \times 最大分组周期 + n) )，空间开销可控。

六、关键结论

该算法的核心是利用数论中的公倍数特性和周期分解，将无穷区间的概率问题转化为有限状态空间的筛选问题。通过分组处理和乘法原理，高效计算联合概率，最终通过累积概率差得到目标答案，精度满足题目要求（绝对误差 ≤1e-6）。