#P9695. 概率期望

    ID: 6317 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-几何概率条件概率二项分布普通生成函数线性递推逆元线性递推

概率期望

题目描述

在一条长度为 ll 的线段上独立生成 nn 个区间。每个区间的两个端点独立、均匀地从 [0,l)[0,l) 中选取,端点可以是实数。若第一个端点大于第二个端点,就交换它们。

求被至少 kk 个区间覆盖的点所组成的集合的期望长度,答案对 998244353998244353 取模。

输入格式

一行三个整数 n,k,ln,k,l,满足 1≤k≤n≤1071\le k\le n\le 10^7,1≤l≤1091\le l\le 10^9。

输出格式

输出一个整数,表示期望长度模 998244353998244353 的结果。

样例

1 1 1
332748118
6 2 1
760234711
7 5 3
223383352
97 31 9984524
267137618
10000000 581 100000
111498399

原 PDF 的第五组样例输出已按题意校正。

子任务

子任务 nn 上限 特殊性质 依赖 分值
1 10
2 1 15
3 1、2
4 2×1032\times10^3 l=1l=1
5 1、2、3、4
6 5×1045\times10^4 1、2、3、4、5
7 10710^7 1、2、3、4、5、6

本站原 PDF · Codeforces 原题