自动搬运

查看原文

来自洛谷，原作者为

	tzc_wk **

搬运于2025-08-24 22:19:05，当前版本为作者最后更新于2022-01-12 23:32:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷题面传送门

首先不难发现周期是 $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
*/