[数学记录]CF1295F Good Contest
command_block
2020-06-05 12:03:22
**题意** : 有一个数组 $A$ ,满足 $A[i]$ 的值在 $[L[i],R[i]]$ 的整数中随机。
问最终 $A$ 不增的概率,对 $998244353$ 取模。
$n\leq 50$ ,时限$\texttt{3s}$。
------------
求出方案数后除以 $\prod(R_i-L_i+1)$ 即为概率。
首先不难想到一个 $O(nR)$ 的`DP`。
设 $f[i][j]$ 为第 $i$ 个数为 $j$ ,且前面的情况已确定的方案数。
有转移 $f[i][j]=\sum\limits_{k=1}^{j}f[i-1][k]$ ,可以前缀和优化。
但是本题 $R$ 的范围很大,不可能完整记录在状态中。
注意到我们的限制只涉及到相对大小关系,考虑离散化,每次观察“段”的贡献(区间左闭右开)。
改设 $f[i][j]$ 为第 $i$ 个数在第 $j$ 个区间内，且下一个数不在 $j$ 区间内的方案数。
转移时,需要得知前面有多少个学校已在 $j$ 区间内。
一种方法是,直接枚举上一个在 $j$ 区间之前的位置,然后把一个区间内的位置都安排到 $j$ 区间内。
在 $[1,c]$ 内选择 $k$ 个不增的数,可以使用插板法,方案数为 $\dbinom{c+k-1}{k}$。
( 这里 $c$ 很大而 $k$ 较小,需要使用递推求组合数 )
可以写出转移方程 :
设 $len[i]$ 为第 $i$ 段的长度。
$$f[i][j]=\sum\limits_{k=0}^{i-1}\sum\limits_{t=1}^{j-1}\dbinom{len+i-k}{i-k}f[k][t]$$
$$=\sum\limits_{k=0}^{i-1}\dbinom{len+i-k}{i-k}\sum\limits_{t=1}^{j-1}f[k][t]$$
前缀和优化即可做到 $O(n^3)$。(本题代码没有使用这个优化)
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 55
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll inv[MaxN];
void Init(int n){
inv[1]=1;
for (int i=2;i<=n;i++)
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}
ll f[MaxN][MaxN*2],C[MaxN];
int n,m,l[MaxN],r[MaxN],x[MaxN*2];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
l[i]=mod-l[i];r[i]=mod-r[i];
swap(l[i],r[i]);
x[i*2-1]=--l[i];x[i*2]=r[i];
}sort(x+1,x+(m=n+n)+1);
Init(n);
f[0][1]=1;l[0]=0;r[0]=mod;
for (int i=1;i<=n;i++){
for (int j=2;j<=m;j++)
if (l[i]<x[j]&&x[j]<=r[i]){
int len=x[j]-x[j-1];
if (!len)continue;
C[0]=1;
for (int k=1;k<=i;k++)
C[k]=C[k-1]*(len+k-1)%mod*inv[k]%mod;
for (int k=i-1;k>=0;k--){
ll sav=0;
for (int t=1;t<j;t++)
sav+=f[k][t];
f[i][j]=(f[i][j]+sav%mod*C[i-k])%mod;
if (!(l[k]<x[j]&&x[j]<=r[k]))break;
}
}
}
ll buf=1;
for (int i=1;i<=n;i++)
buf=buf*powM(r[i]-l[i])%mod;
ll ans=0;
for (int i=2;i<=m;i++)ans+=f[n][i];
printf("%lld",ans%mod*buf%mod);
return 0;
}
```
## + P3643 [APIO2016]划艇
和上一题基本相同,只是多了一个不参加的情况,而且要求严格递增。
设 $f[i][j]$ 为第 $i$ 个数参加，且在第 $j$ 个区间内，下一个数不在第 $j$ 个区间内的方案数。
在 $[1,c]$ 内选择 $k$ 个严格递增的数,可以使用插板法,方案数为 $\dbinom{c}{k}$。
然后考虑除了末尾的位置插入 $0$ 。枚举 $0$ 的个数求和，可以得到方案数为 $\sum\limits_{i=0}^{k-1}\dbinom{k-1}{i}\dbinom{c}{k-i}$
这是范德蒙德卷积,总的方案数是 $\dbinom{c+k-1}{k}$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 505
using namespace std;
const int mod=1000000007;
ll inv[MaxN];
void Init(int n){
inv[1]=1;
for (int i=2;i<=n;i++)
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}
ll f[MaxN][MaxN*2],g[MaxN][MaxN*2];
int n,m,l[MaxN],r[MaxN],x[MaxN*2];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
x[i*2-1]=--l[i];x[i*2]=r[i];
}sort(x+1,x+n+n+1);
m=unique(x+1,x+n+n+1)-x-1;
Init(n);
for (int i=1;i<=m;i++)g[0][i]=1;
for (int i=1;i<=n;i++)
for (int j=2;j<=m;j++){
if (l[i]<x[j]&&x[j]<=r[i]){
int len=x[j]-x[j-1],o=1;
ll C=len;
for (int k=i-1;k>=0;k--){
f[i][j]=(f[i][j]+g[k][j-1]*C)%mod;
if (l[k]<x[j]&&x[j]<=r[k]){
o++;
C=C*(len+o-1)%mod*inv[o]%mod;
}
}
}g[i][j]=(g[i][j-1]+f[i][j])%mod;
}
ll ans=0;
for (int i=1;i<=n;i++)
ans+=g[i][m];
printf("%lld",ans%mod);
return 0;
}
```
### 另解
利用分段多项式函数。
设 $f_i(n)$ 表示前 $i$ 个数已经确定，末尾为 $n$ 的方案数，写出暴力 $\rm DP$ 式 ：
$$f_i(x)=f_{i-1}(x)+\big[n\in[L_i,R_i]\big]\sum\limits_{k<x}f_{i-1}(k)$$
可以证明 $f_i(x)$ 是分段的多项式函数，具体做法就是一种构造证明。
也可以通过前缀和变换归纳证明，这里就不详细展开了。
对于一个分段函数，我们要支持简单加法，以及 $g(x)=\sum\limits_{k<x}f_{i-1}(k)$ 的点值前缀和计算。
不难发现点值前缀和就是离散微积分，为了方便积分，将多项式写成下降幂的形式即可。
```cpp
```