2025年5月4日 贵州省赛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 取模
题解
解法：离散化 + DP + 组合计数
DP 状态：\(dp[j]\) = 前 j 只鸭子的合法方案数。
由于 l 和 r 的取值范围较大（1e9），使用离散化缩小到 1e3。
核心思路：假设这 n 个数的范围相等，都是 [l,r]，那么方案数可以直接用隔板法求出，为 C(n+r-l, n)。
DP 状态转移：遍历所有离散段，在每个段上尝试集中放一段连续的鸭子，使用组合数更新状态。
完整代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int main(){
int n;cin>>n;
vector<ll> l(n+1),r(n+1),vt;
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
vt.reserve(2*n);
for(int i=1;i<=n;i++){
vt.push_back(l[i]);
vt.push_back(r[i] + 1);
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());
int m = vt.size() - 1;
vector<ll> len(m);
for(int j = 0; j < m; j++)
len[j] = vt[j+1] - vt[j];
vector<int> L(n+1),R(n+1);
for(int i = 1; i <= n; i++){
int Li = lower_bound(vt.begin(), vt.end(), l[i]) - vt.begin();
int Ri = lower_bound(vt.begin(), vt.end(), r[i] + 1) - vt.begin() - 1;
L[i] = Li; R[i] = Ri;
}
vector<ll> inv(n+2);
inv[1] = 1;
for(int i = 2; i <= n+1; i++)
inv[i] = (MOD - (MOD/i) * inv[MOD % i] % MOD) % MOD;
vector<ll> dp(n+1, 0), dpnext;
dp[0] = 1;
for(int s = 0; s < m; s++){
vector<ll> f(n+1, 0);
f[0] = 1;
if(n >= 1) f[1] = len[s] % MOD;
for(int t = 2; t <= n; t++){
ll mul = (len[s] + t - 1) % MOD;
f[t] = f[t-1] * mul % MOD * inv[t] % MOD;
}
dpnext = dp;
for(int j = 0; j <= n; j++){
if(dp[j] == 0) continue;
if(j == n) continue;
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;
dpnext[j+t] = (dpnext[j+t] + dp[j] * f[t]) % MOD;
}
}
dp.swap(dpnext);
}
cout << dp[n] % MOD << "\n";
return 0;
}
发表评论