2024贵州省赛M题

题目描述：

GZU 的农学院在阅湖养了$n$ 只鸭子，每只鸭子的肉质都有其对应的鲜美度，第 $i$ 只鸭子的鲜美度是在$[l_i ,r_i]$中的任意整数。嘴馋的贵大人想知道这 $n$ 只鸭子的鲜美度单调不减的方案数，结果可能很大，请对 $998244353$ 取模。

输入：

第一行一个整数 $n (1≤n≤ 500 )$；

接下来 $n$ 行每行两个整数$l_i ,r_i (1≤l_i,r_i ≤10^9 )$。

输出：

输出满足条件的方案数，对 $998244353$ 取模。

样例：

样例1：

输入:

2
3 6
1 4

输出：

解释：对于第一组样例有以下三种方案：$(3,3),(3,4),(4,4)$。

样例2：

输入：

输出：

// --- 解法二：一维状态 dp[i] ---
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int n;cin>>n;
	vector<long long> l(n+1), r(n+1);
	for(int i = 1; i <= n; i++){
		cin >> l[i] >> r[i];
	}
	// 离散化边界
	vector<long long> coords(2*n);
	for(int i = 1; i <= n; i++){
		coords.push_back(l[i]);
		coords.push_back(r[i] + 1);
	}
	//排序
	sort(coords.begin(), coords.end());
	//去重
	coords.erase(unique(coords.begin(), coords.end()), coords.end());
	
	int segCount = coords.size() - 1;
	// 计算每个离散段长度
	vector<long long> segLen(segCount);
	for(int j = 0; j < segCount; j++){
		segLen[j] = coords[j+1] - coords[j];
	}
	// 每只鸭子可用的段区间 [L[i], R[i]]
	//离散化后重新分配值
	vector<int> L(n+1), R(n+1);
	for(int i = 1; i <= n; i++){
		int Li = lower_bound(coords.begin(), coords.end(), l[i]) - coords.begin();
		int Ri = lower_bound(coords.begin(), coords.end(), r[i] + 1) - coords.begin() - 1;
		L[i] = Li; R[i] = Ri;
	}
	// 预处理逆元，用于组合计算
	vector<long long> inv(n+2);
	inv[1] = 1;
	for(int i = 2; i <= n+1; i++){
		inv[i] = (MOD - (MOD/i) * inv[MOD % i] % MOD) % MOD;
	}
	// dp[j] = 前 j 只鸭子的合法方案数
	vector<long long> dp(n+1, 0), dpnext;
	dp[0] = 1;
	// 遍历所有离散段
	for(int s = 0; s < segCount; s++){
		// 预计算该段上取 t 个值的组合数 f[t] = C(segLen[s] + t - 1, t)
		vector<long long> f(n+1, 0);
		f[0] = 1;
		if(n >= 1) f[1] = segLen[s] % MOD;
		for(int t = 2; t <= n; t++){
			long long mul = (segLen[s] + t - 1) % MOD;
			f[t] = f[t-1] * mul % MOD * inv[t] % MOD;
		}
		// dpnext 初始为 dp（不选取该段）
		dpnext = dp;
		// 尝试在该段上添加更多鸭子（末尾连续 t 只鸭子）
		for(int j = 0; j <= n; j++){
			if(dp[j] == 0) continue;
			if(j == n) continue;
			// 查看第 j+1 只鸭子是否允许落在该段
			if(!(L[j+1] <= s && s <= R[j+1])) continue;
			// 从 j+1 开始尝试连续放鸭子
			for(int t = 1; j + t <= n; t++){
				int duckPos = j + t;
				if(!(L[duckPos] <= s && s <= R[duckPos])) break;
				dpnext[j+t] = (dpnext[j+t] + dp[j] * f[t]) % MOD;
			}
		}
		dp.swap(dpnext);
	}
	cout << dp[n] % MOD << "\n";
	return 0;
}

当然可以，下面我们来非常详细地解释这份采用一维状态 dp[i] 的代码解法，也称为「解法二」。本方法相比三维DP更优雅且节省空间，核心依然是“分段 + 动态规划 + 组合计数”。

🧩 一句话总结：

这个算法通过离散化数轴、将每段看作“等价”的数域，并对每段进行动态规划，维护“前 i 只鸭子选择合法数值的方案数”，最终求得满足所有鸭子鲜美度单调不减的合法选法总数。

🧱 步骤详细拆解：

✅ 1. 输入读取和区间保存

vector<long long> l(n+1), r(n+1);
for(int i = 1; i <= n; i++){
    cin >> l[i] >> r[i];
}

读入每只鸭子的鲜美度区间 $[l_i, r_i]$。数组开到 n+1 是为了从 1 开始编号，简化逻辑。

✅ 2. 离散化

vector<long long> coords(2*n);
for(int i = 1; i <= n; i++){
    coords.push_back(l[i]);
    coords.push_back(r[i] + 1);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());

目的：由于 $l_i$ 和 $r_i$ 范围最大是 $10^9$，直接用这些值建DP数组不现实。因此我们：

把所有区间端点和 $r_i+1$ 加入 coords；
排序 + 去重，构造一个稀疏的、关键的“段落分界点”数组；
最终得到的段数是 segCount = coords.size() - 1，每一段为半开区间 $[x_j, x_{j+1})$。

✅ 3. 计算每个段的长度

for(int j = 0; j < segCount; j++){
    segLen[j] = coords[j+1] - coords[j];
}

段的长度也就是该段中一共包含多少整数（对组合数计算有用）。

✅ 4. 每只鸭子允许的段编号范围

for(int i = 1; i <= n; i++){
    int Li = lower_bound(coords.begin(), coords.end(), l[i]) - coords.begin();
    int Ri = lower_bound(coords.begin(), coords.end(), r[i] + 1) - coords.begin() - 1;
    L[i] = Li; R[i] = Ri;
}

这里将每只鸭子的原始区间 $[l_i, r_i]$ 映射成在离散段上的编号范围 $[L[i], R[i]]$。

注意：r[i]+1 是为了保持半开区间的一致性。

✅ 5. 预处理组合数用的逆元

inv[1] = 1;
for(int i = 2; i <= n+1; i++){
    inv[i] = (MOD - (MOD/i) * inv[MOD % i] % MOD) % MOD;
}

用来求组合数 $C(a + b - 1, b)$ 中除法的逆元（因为模数是质数，用费马小定理即可）。

✅ 6. 动态规划初始化

vector<long long> dp(n+1, 0), dpnext;
dp[0] = 1;

dp[i] 表示前 i 只鸭子构成合法非降序列的方案数。
初始只有 0 只鸭子时方案数为 1（空集）。

✅ 7. 遍历所有段，尝试“集中放一段鸭子”

for(int s = 0; s < segCount; s++){

我们依次枚举每一个段 s，在该段上尝试分配一组连续的鸭子。段的顺序是“从小到大”，天然满足了单调不减性要求。

✅ 8. 预处理该段上的组合数：f[t] 表示从该段中取 t 个非降序数的方式

vector<long long> f(n+1, 0);
f[0] = 1;
if(n >= 1) f[1] = segLen[s] % MOD;
for(int t = 2; t <= n; t++){
    long long mul = (segLen[s] + t - 1) % MOD;
    f[t] = f[t-1] * mul % MOD * inv[t] % MOD;
}

这是关键！

f[t] 表示从该段中取 t 个值（允许重复，非降序）的方法数，等价于隔板法中的：

(segLen+t−1t)\binom{\text{segLen} + t - 1}{t}

为什么用这个组合？因为段内所有数是“等价”的，我们只需要计数 “在这一段上放 t 只鸭子” 的方法总数。

✅ 9. 状态转移：从前 j 只鸭子的状态扩展

dpnext = dp; // 默认继承上次的 dp

for(int j = 0; j <= n; j++){
    if(dp[j] == 0) continue;
    if(j == n) continue; // 已经满了

    // 看第 j+1 只鸭子是否能放在段 s 上
    if(!(L[j+1] <= s && s <= R[j+1])) continue;

    for(int t = 1; j + t <= n; t++){
        int duckPos = j + t;
        if(!(L[duckPos] <= s && s <= R[duckPos])) break;

        // 将 dp[j] 状态扩展 t 个鸭子到当前段
        dpnext[j + t] = (dpnext[j + t] + dp[j] * f[t]) % MOD;
    }
}

每次尝试从已有的 j 只鸭子的状态出发，尝试在当前段 s 上安排 t 只新的鸭子；
必须保证这 t 只新鸭子都允许选在当前段；
然后用组合数 f[t] 更新新的状态 dp[j+t]。

✅ 10. 最终答案

cout << dp[n] % MOD << "\n";

最终 dp[n] 就是我们要的答案：全部 n 只鸭子，满足单调不减，每只鸭子在其合法区间内的总方案数。

🧠 总结重点

模块	核心技巧
离散化	降维处理、减小状态空间
动态规划	状态 `dp[i]`，表示前 i 只鸭子合法方案
状态转移	枚举段，集中安排一段连续鸭子
组合数预处理	使用隔板法 + 模逆元计算
单调性保证	因为按段递增枚举，无需显式检查非降

TangZiFan's Blog

I am not afraid of tomorrow for I have seen yesterday and love today.