# Luogu P6261 - [ICPC2019 WF]Traffic Blights (thinking questions)

Luogu problem plane portal

Firstly, it is not difficult to find that the period is \ (M=\text{lcm}(r_1+g_1,r_2+g_2,r_3+g_3,\cdots,r_n+g_n) \), that is, the problem is equivalent to finding an arbitrary number \ (X \) from \ ([0,M-1] \), which satisfies \ (\ forall i\in[1,n],(X+x_i)\bmod (r_i+g_i)\ge g_i \) probability.

Consider a special case: \ (r_i+g_i \) is coprime. According to the knowledge of CRT, it can be proved that for \ (\ forall \ {a_n \}, 0 \ Le a_i < r_i+g_i \), a sequence \ (X \) can be found to satisfy \ ((X+x_i)\bmod (r_i+g_i)=a_i \), in other words, for any sequence \ (\ {a_n \} \), it satisfies \ (\ forall I, (X + X_i) \ bmod (r_i+g_i) = a_ The probability of I \) is the same, which is \ (\ prod \ limits {I = 1} ^ n \ dfrac {g_i}{r_i+g_i} \). Therefore, the total probability can be calculated directly according to \ (\ prod \ limits {I = 1} ^ n \ dfrac {g_i}{r_i+g_i} \).

Consider transforming the general situation into this situation. Since \ (r_i+g_i\le 100 \), each number has at most one prime factor of \ (> 10 \). In this way, we take \ (V=2^6.3 ^ 4.5 ^ 2.7 ^ 2 = 6350400 \), and then write the number in each \ ([0,M-1] \) in the form of \ (kV + B (b < V) \). Consider enumerating \ (B \), so according to the congruence theory, if we take \ (k \) as a variable, then the period of \ (kV+b\bmod (r_i+g_i) \) is \ (\ dfrac{r_i+g_i}{\gcd(r_i+g_i,V)} \). Obviously, because \ (2 ^ 7 > 100,3 ^ 5 > 100,5 ^ 3 > 100,7 ^ 3 > 100 \), \ (\ dfrac{r_i+g_i}{\gcd(r_i+g_i,V)} \) certainly does not contain quality factor \ (2,3,5,7 \). Therefore, this number is either \ (1 \) or a prime number of \ (> 10 \). If we take cycles of the same size as a class, the cycle length between different classes must be reciprocal. In this way, for each type of cycle length \ (L \), we can maintain how many \ (\ bmod l \) positions are legal in real time and set it to \ (c_l \), so the probability of legitimacy in this case is \ (\ prod \ limits {l} \ dfrac {c_l} \), which can be maintained in real time. The time complexity \ (6350400 · n · (r_i+b_i) \) cannot pass.

Continue to optimize. In fact, we don't have to make all cycles prime. We find that if a period is a power of another period, we can automatically align the small period with the large period, which can also be transformed into the previous case. Therefore, we can also take an appropriate \ (V \) so that \ (\ dfrac{r_i+g_i}{\gcd(r_i+g_i,V)} \) are prime numbers or powers of prime numbers, and take \ (V=\text{lcm}(1,2,3,\cdots,10) \). In this way, the complexity is reduced to \ (2520 · n · (r_i+b_i) \).

const int MAXN = 500;
const int MAXV = 100;
int n, x[MAXN + 5], r[MAXN + 5], g[MAXN + 5];
bool able[MAXN + 5][MAXV + 5];
double p[MAXN + 5];
int getmax(int x) {return (x == 2) ? 8 : ((x == 4) ? 8 : ((x == 3) ? 9 : x));}
void calc(int x) {
p[0] += 1; double prd = 1; static bool die[MAXV + 5][MAXV * 5 + 5];
memset(die, 0, sizeof(die));
for (int i = 1; i <= n; i++) {
int cnt = 0, tot = 0;
int d = __gcd(2520, r[i] + g[i]), md = (r[i] + g[i]) / d;
int rst = getmax(md), mul = rst / md;
for (int j = 0; j < md; j++) for (int k = 0; k < mul; k++) {
if (!die[rst][j + k * md]) {
if (able[i][(j * 2520 + x) % (r[i] + g[i])]) cnt++;
else die[rst][j + k * md] = 1;
tot++;
}
}
if (!tot) break;
prd = 1.0 * prd * cnt / tot;
p[i] += prd;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &r[i], &g[i]);
for (int i = 1; i <= n; i++) for (int j = r[i]; j < r[i] + g[i]; j++)
able[i][(j - x[i] % (r[i] + g[i]) + r[i] + g[i]) % (r[i] + g[i])] = 1;
for (int i = 0; i < 2520; i++) calc(i);
for (int i = 0; i <= n; i++) p[i] /= 2520;
for (int i = 1; i <= n + 1; i++) printf("%.10lf\n", p[i - 1] - p[i]);
return 0;
}
/*
4
0 15 49
0 13 19
0 33 63
0 27 53
*/


Added by zedan_80 on Wed, 12 Jan 2022 19:35:16 +0200