[Codeforces 1295F]Good Contest(DP+组合数学)
[Codeforces 1295F]Good Contest(DP+组合数学)
题面
有一个长度为\(n\)的整数序列,第\(i\)个数的值在\([l_i,r_i]\)中随机产生。问这个序列是一个不上升序列的概率(模\(998244353\)意义下)。
\(n \leq 50,l_i,r_i \leq 998244351\)
分析
和[APIO2016]划艇几乎一模一样。可惜比赛的时候时间不够。
首先把问题转化成求最长不上升序列的数量。
我们把这些区间离散化,分割成两两之间不互相覆盖的若干个区间，把这些分割后的区间从被拆分成编号在\([l_i,r_i)\)的新区间。如原来的区间为\([1,4],[2,3],[4,5]\).那么拆分出来的新区间有\(1:[1,1],2:[2,3],3:[4,4],4:[5,5]\).而新的\(l_i,r_i\)对应为\([1,3),[2,3),[3,5)\).下面的代码实现了该过程.
void discrete(){
dn=0;
for(int i=1;i<=n;i++){
tmp[++dn]=a[i].l;
tmp[++dn]=a[i].r+1;//转成开区间
}
sort(tmp+1,tmp+1+dn);
dn=unique(tmp+1,tmp+1+dn)-tmp-1;
for(int i=1;i<=n;i++){
a[i].l=lower_bound(tmp+1,tmp+1+dn,a[i].l)-tmp;
a[i].r=lower_bound(tmp+1,tmp+1+dn,a[i].r+1)-tmp;
}
}设\(dp[i][j]\)表示前\(i\)个数,第\(i\)个数在第\(j\)个新区间或之后的新区间内的方案数。那么从前面转移过来时的区间编号一定\(\geq j\). 于是可以写出转移方程:
\[dp[i][j]=\sum_{1 \leq k \leq i,j \in[l_k,r_k] } dp[k-1][j+1] \times C_{i-k+len(j)}^{i-k+1}\]
我们枚举最前面的与\(i\)在同一个新区间\(j\)的位置\(k\), 那么 比\(k\)小的位置所在区间编号一定\(>j\),所以乘上\(dp[k-1][j+1]\). 而\(len(j)\)表示的是第\(j\)个新区间的实际长度,组合数表示的是从区间\(j\)里选出\(i-k+1\)个递增的数.
注意到上面的转移方程只求出了第\(i\)个数恰好在区间\(j\)里的方案数。所以枚举完\(j\)后还要求一遍后缀和。
最终答案为\(\frac{dp[n][1]}{\prod_{i=1}^n (r_i-l_i+1)}\)
dp转移的复杂度为\(O(n^3)\),但是由于\(len(j)\)比较大而\(i-k+1\)比较小.,求组合数需要\(O(n)\)的时间枚举。总复杂度为\(O(n^4)\)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 998244353
#define maxn 1000
using namespace std;
typedef long long ll;
inline ll fast_pow(ll x,ll k){
ll ans=1;
while(k){
if(k&1) ans=ans*x%mod;
x=x*x%mod;
k>>=1;
}
return ans;
}
inline ll inv(ll x){
return fast_pow(x,mod-2);
}
ll fact[maxn+5],invfact[maxn+5],invx[maxn+5];
void ini_inv(int n){
fact[0]=1;
for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
invfact[n]=inv(fact[n]);
for(int i=n-1;i>=0;i--) invfact[i]=invfact[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++){
invx[i]=invfact[i]*fact[i-1]%mod;
}
}
inline ll C(ll n,ll m){
ll ans=1;
for(int i=n;i>=n-m+1;i--) ans=ans*i%mod;
for(int i=1;i<=m;i++) ans=ans*invx[i]%mod;
return ans;
}
int n;
struct seg{
int l;
int r;
}a[maxn+5];
int dn=0;
int tmp[maxn+5];//离散化用
void discrete(){
dn=0;
for(int i=1;i<=n;i++){
tmp[++dn]=a[i].l;
tmp[++dn]=a[i].r+1;//转成开区间
}
sort(tmp+1,tmp+1+dn);
dn=unique(tmp+1,tmp+1+dn)-tmp-1;
for(int i=1;i<=n;i++){
a[i].l=lower_bound(tmp+1,tmp+1+dn,a[i].l)-tmp;
a[i].r=lower_bound(tmp+1,tmp+1+dn,a[i].r+1)-tmp;
}
}
ll dp[maxn+5][maxn+5];//dp[i][j]表示前i个数,第i个数在j及之后区间内的方案数
//枚举放在第j个区间里的个数,dp[i][j]+=dp[k-1][j+1]*C
ll sum[maxn+5];
int main(){
ini_inv(maxn);
scanf("%d",&n);
ll all=1;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].l,&a[i].r);
all=all*(a[i].r-a[i].l+1)%mod;
}
discrete();
for(int j=1;j<=dn;j++) dp[0][j]=1;
for(int i=1;i<=n;i++){
for(int j=a[i].l;j<a[i].r;j++){
for(int k=i;k>0;k--){
if(j<a[k].l||j>=a[k].r) break;
dp[i][j]+=dp[k-1][j+1]*C(i-k+tmp[j+1]-tmp[j],i-k+1)%mod;
//插板法,把n个物品分成m份,允许有空,C(n+m-1,m)
//也就是说把r-l+1分成i-k+1份,再加上l,就可以保证在[l,r]内
dp[i][j]%=mod;
}
}
for(int j=dn-1;j>=1;j--){
dp[i][j]+=dp[i][j+1];
dp[i][j]%=mod;
}
}
printf("%lld\n",dp[n][1]*inv(all)%mod);
}