标签：lin   fine   return   isp   题目   暴力枚举   har   line   pac   

计数难题5：[APIO2016]划艇

标签（空格分隔）： 计数难题题选

题目大意：

给定\(n\)个区间\([l_i,r_i]\)。
你可以从第\(i\)个区间中选出一个整数元素\(a_i\in [l_i,r_i]\)，也可以不选。
要求选出的元素按标号顺序排列后构成一个严格单调递增序列。
求至少选出一个元素的合法方案数。
答案对\(10^9+7\)取模。
数据范围：\(n\leq 500\) , \(l_i\leq r_i \leq 10^9\) 。

题解

可以想到把区间离散化。
设\(f_{i,j}\) 表示考虑完前\(i\)个区间，当前区间必须选一个元素，且这个元素在第\(j\)段的方案数。
转移的时候，暴力枚举上一个不在同一区间的元素选在哪个区间\(k\)。
设\([k+1,i]\)范围内能够在第\(j\)段选数的区间个数为\(m\)，设当前这段的长度为\(len\)。
我们再暴力枚举这\(m\)个元素中有\(l\)个元素在当前这段中选了。
那么就可以得到转移方程：
\[f_{i,j} = \sum_{k=0}^{i-1} (\sum_{t=1}^{j-1} f_{k,t})(\sum_{l=1}^{min(m,len)} \binom{m-1}{l-1}\binom{len}{l})\]
显然\(\sum_{t=1}^{j-1} f_{k,t}\) 是可以记前缀和的。
所以我们现在的问题变为求\(\sum_{l=1}^{min(m,len)} \binom{m-1}{l-1}\binom{len}{l}\)。
我们有\(\sum_{l=1}^{min(m,len)} \binom{m-1}{l-1}\binom{len}{l} = \sum_{l=1}^{min(m,len)} \binom{m-1}{m-l}\binom{len}{l}\)
所以可以用范德蒙恒等式化简：

\[\sum_{l=1}^{min(m,len)} \binom{m-1}{m-l}\binom{len}{l} = \binom{m+len-1}{m}\]
现在的转移方程就变为了：
\[f_{i,j} = \sum_{k=0}^{i-1} \binom{m+len-1}{m} (\sum_{t=1}^{j-1} f_{k,t})\]

唯一的问题就是如何求\(\binom{m+len-1}{m}\)了，因为\(len\)可能达到\(10^9\)级别。
注意到组合数的改变只与\(m\)有关。
所以组合数的变化是上下同时\(+1\)。
所以可以套用吸收-归纳恒等式：\(\binom{n+1}{m+1} = \frac{n+1}{m+1} \binom{n}{m}\)。
我们枚举\(k\)，然后在转移前先预处理好组合数即可。

实现代码

#include
#define IL inline
#define _ 1015
#define ll long long
using namespace std ;

IL int gi(){
    int data = 0 , m = 1; char ch = 0;
    while(ch!='-' && (ch'9')) ch = getchar();
    if(ch == '-'){m = 0 ; ch = getchar() ; }
    while(ch >= '0' && ch = 0; k --) {
                if(A[k + 1] = 0; k --) f[i][j] = (f[i][j] + 1ll * Comb[k] * g[k][j-1] % mod) % mod ; 
        }
        g[i][0] = f[i][0] ;
        for(int j = 1; j 

计数难题5：[APIO2016]划艇

标签：lin   fine   return   isp   题目   暴力枚举   har   line   pac   

原文地址：https://www.cnblogs.com/GuessYCB/p/9903606.html