重庆市做网站的公司有哪些,网站建设服务代理商,常见c2c网站有哪些,海搜网做的网站怎么样正题
题目链接:https://www.luogu.com.cn/problem/CF1153F 题目大意
在有nnn个区间的左右端点在[0,l)[0,l)[0,l)范围内随机#xff0c;求被至少kkk个区间覆盖的期望长度。 1≤n,k≤2000,1≤l≤1091\leq n,k\leq 2000,1\leq l\leq 10^91≤n,k≤2000,1≤l≤109 解题思路
长度…正题
题目链接:https://www.luogu.com.cn/problem/CF1153F 题目大意
在有nnn个区间的左右端点在[0,l)[0,l)[0,l)范围内随机求被至少kkk个区间覆盖的期望长度。
1≤n,k≤2000,1≤l≤1091\leq n,k\leq 2000,1\leq l\leq 10^91≤n,k≤2000,1≤l≤109 解题思路
长度为lll上的数轴上2×n2\times n2×n个随机点的话期望距离都是l2n1\frac{l}{2n1}2n1l。
所以我们只需要考虑期望有多少个相邻点对之间被kkk个区间覆盖然后再乘上上面那个长度就行了。
然后考虑dpdpdp设fi,jf_{i,j}fi,j表示现在到第iii个端点前面有jjj个区间延伸过来之后还剩n−j−i−j2n-j-\frac{i-j}{2}n−j−2i−j个还没有出现的区间jjj个还待结束的区间。
然后每次转移完加上不小于kkk个区间延伸到下一个的概率即可。
时间复杂度O(nk)O(nk)O(nk) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4100,P998244353;
ll n,k,l,ans,inv[N],f[N][N];
signed main()
{scanf(%lld%lld%lld,n,k,l);inv[1]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;f[0][0]1;for(ll i0;i2*n;i){for(ll j0;jmin(i,n);j){if((i-j)1)continue;ll wn-j-(i-j)/2;if(j)(f[i1][j-1]f[i][j]*j%P*inv[w*2j]%P)%P;(f[i1][j1]f[i][j]*w*2ll%P*inv[w*2j]%P)%P;}for(ll jk;jmin(i,n);j)(ansf[i][j])%P;}for(ll jk;jn;j)(ansf[2*n][j])%P;printf(%lld\n,ans*l%P*inv[2*n1]%P);return 0;
}
