题解 P6261 [ICPC2019 WF]Traffic Blights

· · 题解

洛谷题面传送门

首先不难发现周期是 M=\text{lcm}(r_1+g_1,r_2+g_2,r_3+g_3,\cdots,r_n+g_n)​​​​，也就是说问题等价于求从 [0,M-1]​​​​ 任选一个数 X​​​​，满足 \forall i\in[1,n],(X+x_i)\bmod (r_i+g_i)\ge g_i​​​​ 的概率。

考虑一种特殊情况：r_i+g_i 两两互质，根据 CRT 的知识可以证明，对于 \forall\{a_n\},0\le a_i<r_i+g_i，都可以找到一个序列 X 满足 (X+x_i)\bmod (r_i+g_i)=a_i，换句话说，对于任意序列 \{a_n\}，满足 \forall i,(X+x_i)\bmod (r_i+g_i)=a_i 的概率都是相同的，为 \prod\limits_{i=1}^n\dfrac{g_i}{r_i+g_i}。因此总概率就可以直接按 \prod\limits_{i=1}^n\dfrac{g_i}{r_i+g_i} 来计算。

考虑将普遍的情况转化为这种情况，由于 r_i+g_i\le 100，因此每个数最多只有一个 >10 的质因子。这样，我们取 V=2^6·3^4·5^2·7^2=6350400，然后将每个 [0,M-1] 中的数写成 kV+b(b<V) 的形式。考虑枚举 b，这样根据同余论，如果我们把 k 当作变量，那么 kV+b\bmod (r_i+g_i) 的周期为 \dfrac{r_i+g_i}{\gcd(r_i+g_i,V)}。显然，由于 2^7>100,3^5>100,5^3>100,7^3>100，\dfrac{r_i+g_i}{\gcd(r_i+g_i,V)} 肯定不含质因子 2,3,5,7。故这个数要么为 1，要么为 >10 的质数。如果我们把大小相同的周期当作一类，那么不同类之间周期长度肯定是两两互质的。这样我们再对于每一类周期长度 l，实时维护有多少个 \bmod l 的位置是合法的，设为 c_l，那么对于这种情况合法的概率就是 \prod\limits_{l}\dfrac{c_l}{l}，实时维护一下即可，时间复杂度 6350400·n·(r_i+b_i)，无法通过。

继续优化。事实上，我们其实并不一定要让所有周期都是质数。我们发现如果一个周期是另一个周期的幂，那么我们将小的周期自动与大的周期对齐也可以转化为上一种情况，因此我们也可以取合适的 V 使得 \dfrac{r_i+g_i}{\gcd(r_i+g_i,V)} 都是质数或质数的幂，取 V=\text{lcm}(1,2,3,\cdots,10) 即可。这样复杂度就降到了 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
*/