[CF1153F]Serval and Bonus Problem(dp/积分+OGF)

其实这道题已经在我的学习笔记里面口胡过了…
但由于某种特殊原因…我写了一篇博客。

题面

Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length of a random subsegment of a given segment. Then he left a bonus problem as homework, with the award of a garage kit from IOI. The bonus is to extend this problem to the general case as follows.

You are given a segment with length $l$ . We randomly choose n n segments by choosing two points (maybe with non-integer coordinates) from the given segment equiprobably and the interval between the two points forms a segment. You are given the number of random segments $n$ , and another integer $k$ . The $2n$ endpoints of the chosen segments split the segment into $(2n+1)$ intervals. Your task is to calculate the expected total length of those intervals that are covered by at least $k$ segments of the $n$ random segments.

You should find the answer modulo $998244353$ .

翻译

有一段长为$l$的线段，有$n$个区间，左右端点在$[0,l)$间均匀随机（可能不是整数）。
求期望被至少$k$段区间覆盖的长度，对$998244353$取膜。
来源:洛谷

题解

动态规划

首先将线段长度看成$1$，最后乘以$l$即可。
利用某结论，随机选的$2n$端点在期望下可以被看成将线段划分为长度相等的$2n+1$段。
接下来我们考虑dp:
定义$f_{i,j}$,$g_{i,j}$分别为还未/已经存在一段覆盖次数不小于$k$，确定了前$i$个端点，还有$j$个左端点未被匹配的方案数。
但是这样做显然有问题:一个方案可能有多个覆盖次数不小于$k$的段，因此我们还需要乘上覆盖次数。
不过有个更巧妙的做法:我们可以新增一个点(具体体现在下面的第三个转移方程)，它在每次向$f$转移到$g$的时候出现。
可以发现这样做等价于乘上一个系数。
然后列好转移方程就做完了:
$$\begin{gathered} f_{i,j}?>f_{i+1,j+1},g_{i,j}?>g_{i+1,j+1} \\ {f}_{i,j}?>j\times f_{i+1,j?1},g_{i,j}?>j\times g_{i+1,j?1} \\ {f}_{i,j}?>g_{i+1,j}(k\le j) \end{gathered}$$
最终答案是:$\frac{g_{2n+1,0}\times 2^n\times n!}{2n!\times (2n+1)}$。
[注意乘的$\frac{1}{2n+1}$是线段的平均长度]
复杂度:$O(n^2)$

积分+多项式

使用微元法，设离散变量$x(0\le x\le 1)$，算完离散概率再用积分积起来。
那么一段区间覆盖该位置的概率就是$2x\times (1?x)$(乘2是因为左右端点可以交换)。
我们枚举$k$，可以很容易算出恰好覆盖$k$的次的概率:
$$E[X]={\int }_0^1\sum _{m\le k}\left(\genfrac{}{}{0ex}{}{n}{k}\right)(2x\times (1?x){)}^k\times (1?2x\times (1?x){)}^{n?k}\mathrm{d}x$$
直接爆算是$O(n^3)$的。
用NTT优化乘法就是$O(n^2\log n)$的了。
然而会被毒瘤出题人卡掉。
但是我们可以一开始就把多项式化为点值形式最后再还原。
这样就是$O(n^2)$了。
如果你定积分相当熟练地话…你可以利用Beta Function推式子，得到一个$O(n\log n)$的方法。可以参考一下这位大佬的博客(我懒得写了)。

实现

太懒了…只有第一种方法。

/*Lower_Rating*/
/*probaility*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 998244353
#define Pr pair<LL,int>
#define X first
#define Y second
#define MAXN 5000
#define MAXM 400000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,l,k;
int dp[MAXN+5][MAXN+5][2],fac[MAXN+5],pw[MAXN+5];
int main()
{
    n=read(),k=read(),l=read();fac[0]=pw[0]=1;for(int i=1;i<=2*n+1;i++)fac[i]=mul(fac[i-1],i),pw[i]=mul(pw[i-1],2);dp[0][0][0]=1;for(int i=0;i<=2*n;i++)for(int j=0;j<=i;j++){
    if(j>=k)dp[i+1][j][1]=add(dp[i+1][j][1],dp[i][j][0]);for(int k=0;k<=1;k++){
    if(j)dp[i+1][j-1][k]=add(dp[i+1][j-1][k],mul(dp[i][j][k],j));dp[i+1][j+1][k]=add(dp[i+1][j+1][k],dp[i][j][k]);}}printf("%d",mul(mul(mul(dp[2*n+1][0][1],pw[n]),mul(fac[n],inv(fac[2*n+1]))),l));
}