前言
因为本人太弱，急需锻炼思维，固从现在起开始着手写计数题，并写下题解分析思路的欠缺。另外本文将长时间更新，所以我准备把它置顶，尽量日更！
P3643 [APIO2016] 划艇 2024.8.28
简要题意
现在有 \(n\) 个区间，每个区间范围为 \([l_i,r_i]\)。现在有 \(n\) 个元素需要赋值，每个元素的值要么为零，要么在给定的区间内。对于一个值非零的元素 \(a_i\)，需要满足它的数值严格大于所有标号比它小的元素，即 \(a_i\ge\max_{1\le j<i}\{a_j\}\)。求方案数。
数据范围：\(n\le500,1\le l_i\le r_i\le10^9\)。
题解
首先去想题目性质，然后很高兴地发现根本没有什么性质。然后先考虑朴素 dp，我们令 \(f_{i,j}\) 表示第 \(i\) 个元素值为 \(j\) 的方案数，最后答案为 \(\sum_{i=1}^{i\le n}\sum_{j}f_{i,j}\)。
然后考虑转移，其实转移也很暴力我就直接放式子了：
\[f_{i,j}=\begin{cases} \sum_{k=0}^{i-1}\sum_{l=1}^{j-1}f_{k,l} & j\in[l_i,r_i]\\ 0 & otherwise \end{cases} \]为方便转移，初始 \(f_{0,1}=1\)。
然后不用多说这个肯定爆了。第二维值域是 \(10^9\) 所以能够想到将区间离散化，然后第二维改成区间。这样转移就需要小小的改变一下，因为涉及到了区间选若干点，所以需要加一个系数。那么系数我们怎么求呢？
假设当前区间长度为 \(len\)，元素为第 \(i\) 个。枚举到前 \(j\) 个元素时，现在有 \(i-j\) 个元素将会放在当前区间，我们就把问题抽象成有 \(1\) 到 \(len\) 一共 \(len\) 个数，我们需要从中选出最多 \(m\) 个，选择的方案数就是转化时乘上的系数。考虑对于一次选择，我可以选或不选，若我选就会从中选取一个数就正常做；但如果我不选呢？就把它看成我选了零。于是我们就可以往序列中加入 \(m\) 个零，现在有一共 \(len+m\) 个数，我要从中选出 \(m\) 个，方案为 \({len+m}\choose m\)。然而因为 dp 状态钦定第 \(i\) 个数必选，所以我们实际往序列中加入的零的个数应该会比上述操作少一个（因为保证至少有一个数也就是 \(i\) 不为零）。于是最后的 dp 转移就变成了下面的：
\[f_{i,j}=\begin{cases} \sum_{k=0}^{i-1}\sum_{l=1}^{j-1}f_{k,l}{Len_j+cnt-1\choose cnt} & j\in[l_i,r_i]\\ 0 & otherwise \end{cases} \]但是现在总复杂度还是 \(O(n^4)\) 的，还需要一个小优化，然后考虑哪些状态可以一起考虑。我们可以发现，对于当前的状态 \(f_{i,j}\)，我只要满足一个状态 \(f_{k,l}\) 的第二维小于 \(j\) 也就是 \(l<j\)，就可以将所有的 \(f_{k,l},l<j\) 累加然后整体乘上一个组合数，所以记一个 \(g_{i,j}=\sum_{k=1}^{j-1}f_{i,k}\)，然后就得到了最后的转移式：
\[f_{i,j}=\sum_{k=0}^{i-1}g_{k,j}{Len_j+cnt-1\choose cnt} \]时间复杂度 \(O(n^3)\) 不做过多解释。
代码
int n, l[N], r[N], z[N << 1], tot;
ll f[N], c[N], inv[N], ans;
ll add(ll x, ll y){
x += y; return x >= p ? x - p : x;
}
signed main(){
// fileio(fil);
n = rd();
for(int i = 1; i <= n; ++i){
z[i - 1 << 1 | 1] = l[i] = rd(), z[i << 1] = r[i] = rd() + 1;
}
sort(z + 1, z + 1 + (n << 1));
tot = unique(z + 1, z + 1 + (n << 1)) - z - 1;
for(int i = 1; i <= n; ++i){
l[i] = lower_bound(z + 1, z + 1 + tot, l[i]) - z;
r[i] = lower_bound(z + 1, z + 1 + tot, r[i]) - z;
}
inv[1] = f[0] = c[0] = 1;
for(int i = 2; i <= n; ++i)inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
for(int i = 1; i < tot; ++i){
int len = z[i + 1] - z[i];
for(int j = 1; j <= n; ++j)c[j] = c[j - 1] * (len + j - 1) % p * inv[j] % p;
for(int j = n; j; --j)if(l[j] <= i and i + 1 <= r[j]){
ll s = 0; int cnt = 1;
for(int k = j - 1; ~ k; --k){
s = add(s, c[cnt] * f[k] % p);
cnt += l[k] <= i and i + 1 <= r[k];
}
f[j] = add(f[j], s);
}
}
for(int i = 1; i <= n; ++i)ans += f[i];
printf("%lld", ans % p);
return 0;
}
小结
其实做完这道题时感觉完全不够紫题，但是在看题解之前怎么都切不了。其实暴力 dp 我肯定会，离散化我想到了，后面的组合数也很基础，最后的前缀和相对于其他优化也简单得多。但是，为什么我就是做不出来呢？因为我不熟悉知识间的组合与衔接，不肯从暴力入手，老是想怎么直接出正解，而真正的正解需要前面大量的铺垫。它或许是 OIer 做题时的妙手偶得，但更是大量的经验与积累！
而对于我来说，我拿到一道题应该去做什么？我首先要去分析题目的性质，然后根据性质看看能不能得出进一步结论。有了以上的东西，我就可以去根据已有的东西思考如何得出答案，这一期间可以先将时间复杂度暂放。最后再来慢慢优化求解的过程，方法。还有不要忘了验证正确性！
标签：le,记录,sum,元素,len,计数,区间,dp From： https://www.cnblogs.com/Nekopedia/p/18385654