题目链接：https://codeforces.com/problemset/problem/1153/F。
吓人的题。。其实也没什么难度。
首先显然所有点都是均匀等概率分布的，所以这$2n-1$段每段期望长度是$\dfrac{l}{2n-1}$，那么我们只需要关心相对位置，然后算期望有多少段满足条件即可。
那么问题就转化成了离散的，就比较简单了，设$f_{i,j}$表示填了$i$个点了，前面都是合法匹配，然后多出来了$j$个左端点。
随便转移一下就行了，对于$i,j$这个状态，如果$j\geqslant k$，那么就有$f_{i,j}\cdot f_{2n-i,j}\cdot j!$种情况这一段合法，$f_{2n-i,j}$是后面的填法，那么此时$j$表示多出来的右端点，阶乘是让前后的端点匹配，统计一下就好了。
复杂度$O(n^2)$。
然后写完之后看到了一个暴算积分的做法。。。链接在这里，我就不写(抄)了，中间有一个叫做第一类欧拉积分的玩意，其他部分都是简单运算，(太棒了，学到许多)，而且复杂度比较优秀，是$O(n\log n)$的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define data asd09123jdf02i3h
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
int n,k,l,f[4002][2002],ans,fac[maxn];
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
return res;
}
int main() {
read(n),read(k),read(l);l=1ll*l*qpow(n*2+1,mod-2)%mod;
f[0][0]=fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=n*2;i++)
for(int j=0;j<=min(n,i);j++)
f[i][j]=((j?f[i-1][j-1]:0)+1ll*f[i-1][j+1]*(j+1)%mod)%mod;
for(int i=1;i<=n*2;i++)
for(int j=k;j<=min(n,i);j++)
ans=(ans+1ll*f[i][j]*f[n*2-i][j]%mod*fac[j]%mod)%mod;
ans=1ll*ans*qpow(f[n*2][0],mod-2)%mod*l%mod;
write(ans);
return 0;
}
|