思路
考虑题目要求的是什么。
假设 \(p_i\) 代表通过前 \(i\) 个红绿灯的概率。
那么我们的答案即为 \(p_i-p_{i-1}\)。
不妨设 \(w_i=r_i+g_i\)。
我们的限制条件类似：
\[t\not \equiv a_i\pmod w_i \]那么所有红绿灯会形成周期 \(lcm(w_1,w_2,\cdots,w_n)\)。
由于 \(2019!\) 肯定是这个数的倍数。
所以我们只需要算这个周期内的概率。
考虑一种特殊情况。
假如任意 \(gcd(w_i,w_j)=1\)，也就是 \(w_i\) 全部互质的情况下。
此时 \(lcm(w_1,w_2,\cdots,w_n)=\prod w_i\)。
我们的 \(t\) 在每一个模 \(w_i\) 都可以取任意的值。
也就是每个红绿灯的概率是独立的。
总概率只需要将每个的概率相乘就可以得到。
当 \(w_i\) 不互质怎么办。
我们可以让 \(t\) 有一些特殊性质。
我们设定大模数 \(I\)，令 \(t=k\times I + b~(b<I)\)。
那么我们的每个红绿灯就不再是每 \(w_i\) 一轮了。
添加了 \(t\) 的限制后，周期变为了 \(lcm(I,w_i)\)。
在我们枚举 \(b\) 的时候，周期还会平均分配到每一种上即 \(\frac{lcm(I,w_i)}{I}\)。
考虑 \(\frac{lcm(I,w_i)}{I}=\frac{w_i}{\gcd(I,w_i)}\)。
我们可以让变换后的数互质。
想要做到这一点，\(I\) 至少得是 \(2^6\times 3^4\times 5^2\times 7^2=6350400\)。
复杂度为 \(O(6350400\times n\times w_i)\)。
这肯定是接受不了的。
但是我们还可以做到的条件是什么。
假如一组数中，两两都互为倍数，且组与组之间都互质。
这是的概率在组之间也是相对独立的。
而组内的概率也只需要把小的补大就可以了。
最简单的分组就是把 \(w_i\) 保留成质数的幂。
那么 \(I\) 就只需要是 \(2^3\times 3^2\times 5\times 7=2520\) 即可。
时间复杂度为 \(O(2520\times n\times w_i)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 110;
const int I = 2520;
int n, x[N], r[N], g[N], w[N];
int v[N][M];
int f[M][M << 3];
double p[N];
inline auto mod(int x, int y) { return (x % y + y) % y; }
inline void sol(int x) {
p[0] += 1;
double res = 1;
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++) {
int up = 0, dw = 0, d = g[i], t = r[i];
for (int j = 0; j < d; j++)
for (int k = 0; k < t / d; k++) {
if (!f[t][j + k * d]) {
dw++;
if (v[i][(j * I + x) % w[i]] == 1) up++;
if (v[i][(j * I + x) % w[i]] == 0) f[t][j + k * d] = 1;
}
}
if (!dw) break;
p[i] += (res = res * up / dw);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i] >> r[i] >> g[i], w[i] = r[i] + g[i];
for (int i = 1; i <= n; i++)
for (int j = r[i]; j < w[i]; j++) v[i][mod(j - x[i], w[i])] = 1;
for (int i = 1; i <= n; i++) g[i] = w[i] / __gcd(I, w[i]);
for (int i = 1; i <= n; i++) r[i] = (g[i] == 2 || g[i] == 4) ? 8 : g[i] == 3 ? 9 : g[i];
for (int i = 0; i < I; i++) sol(i);
for (int i = 0; i <= n; i++) p[i] /= I;
for (int i = 1; i <= n + 1; i++) printf("%.9lf\n", p[i - 1] - p[i]);
return 0;
}