2125 d2

A

B

C

容斥原理。

定义一个函数 cal(x) 来 计算 1 ~ x 中 是 2 3 5 7 倍数 的总个数，最后输出 r - cal(r) - (l - 1 - cal(l - 1)) 即可。

可以直接枚举 但是这里讲一下二进制枚举的写法。

auto cal = [&](int n) -> int
{
	vector<int> v = {2, 3, 5, 7};
	int ans = 0;
	// 我们最后要计算 2 + 3 + 5 + 7 - （2 * 3 + 2 * 5 + ...）
	// 所以 奇数加 偶数减
 
	for (int mask = 1; mask < (1ll << v.size()); mask++)
	{
		// 譬如mask的二进制是1011 那么即为选择了2 3 7
		int cur = 1, tot = 0; // cur 表示 选择的数字 tot表示个数
		for (int i = 0; i < v.size(); i++)
		{
			if ((mask >> i) & 1)
			{
				/* 接下来 cur *= v[i] 的操作 有可能会 爆 long long
				所以我们提前判断 如果 cur * v[i] > n
				也就是 cur > n / v[i] 时 我们就直接令cur = n + 1 然后break
				*/
				if (cur > n / v[i])
				{
					cur = n + 1;
					break;
				}
				cur *= v[i];
				tot++;
			}
		}
 
 
		if (tot & 1) // 选择的数字数量是奇数 根据容斥原理 我们应该加上
		{
			ans += n / cur;
		}
		else ans -= n / cur;
	}
 
	// 这里直接return n - ans 省得麻烦
	return n - ans;
};

根据这个代码 最后我们计算 $cal(r)-cal(l-1)$ 即可。

可以做一下 [牛客的题目集]((1条未读私信) 牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ) 加深理解

D

概率怎么算？

比方说有n条线段 选择每一条线段的概率分别是 p[i]

那么我们4条线段 选择2和4 的总概率就是 P = (1 - p[1]) * p[2] * (1 - p[3]) * p[4]

我们钦定一个初始概率 $P_0=\prod (1-p[i])$ 最后要求的概率是上面P 那么每一个概率就要乘上一个系数：

$$P=P_0\times (p[2]\times \frac{1}{1-p[2]})\times (p[4]\times \frac{1}{1-p[4]})$$

又有 $p[i]=\frac{p_i}{q_i}$ 化简即可。

总之 记 $w_i=(p[i]\times \frac{1}{1-p[i]})$ ，下一步就是如何表示从1到m的覆盖了。

设 $dp[i]$ 表示 在变换后的概率空间中，通过激活某些线段，使得位置1到i-1都被恰好覆盖，且在位置i”停下”的概率

我们有 $dp[0]=1$ 作为初始化，接下来 对于每一段 $[l,r,w]$ 组合，都应该有：

$$dp[r]=(dp[r]+dp[l-1]\ast w_i)$$

其中 $dp[l-1]$ 表示 安稳到达 l - 1 的概率，w表示后面这一段存在的概率，二者相乘是因为遵循分步乘法计数原理； $dp[r]$ 加上后面这一段 是因为遵循分类加法计数原理。

最后我们就求得了 $dp[m]$ 作为 从0开始 安稳到达 m 的概率 最后跟 $P_0$ 相乘 取模 即可。

// 快速幂
int power(int base, int exp)
{
    int res = 1;
    base %= MOD;
    while (exp > 0)
    {
        if (exp & 1)
            res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}
 
// 模逆元
int inv(int x)
{
    return power(x, MOD - 2);
}
 
struct datas
{
    int l, r;
    int w; // 存储权重
};
 
void solve()
{
    int n, m;
    cin >> n >> m;
 
    int p0 = 1;
 
    vector<datas> v(n);
    for (int i = 0; i < n; i++)
    {
        int l, r, p, q;
        cin >> l >> r >> p >> q;
        auto curp = p * inv(q) % MOD;
        // p0 *= (1 - curp); 是错的 要特别注意取模
        p0 = (p0 % MOD * (1 + MOD - curp) % MOD) % MOD;
        v[i] = {l, r, curp * inv((1 + MOD - curp) % MOD) % MOD};
    }
 
    map<int, vector<pair<int, int>>> mp;
 
    for (auto [l, r, w] : v)
    {
        mp[l].emplace_back(r, w);
    }
 
    vector<int> dp(m + 1, 0);
    dp[0] = 1;
 
    for (int l = 1; l <= m; l++)
    {
        for (auto [r, w] : mp[l])
        {
            dp[r] = (dp[r] + dp[l - 1] * w) % MOD;
        }
    }
 
    cout << p0 * dp[m] % MOD;
}

上面出现了很多 %MOD 要是图省事可以找哥哥的[Z模板](jiangly算法模板收集 - hh2048 - 博客园) 那样会方便的多。