重庆住房建设部网站,网站如何上线,深圳网络推广工资,购物网站哪个最好正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/D 题目大意 nnn个数的序列#xff0c;排序后让随机kkk个数加上ddd#xff0c;求依旧满足单调上升的期望概率 解题思路
对于一个位置加上ddd后会让到后面一段范围内都得加上ddd。我们预处理一个lil_ili表示如果ii…正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/D 题目大意
nnn个数的序列排序后让随机kkk个数加上ddd求依旧满足单调上升的期望概率 解题思路
对于一个位置加上ddd后会让到后面一段范围内都得加上ddd。我们预处理一个lil_ili表示如果iii加上ddd后[i1,li][i1,l_i][i1,li]都得加上ddd。
然后设fi,jf_{i,j}fi,j表示到第iii个加了kkk次依旧满足条件的方案数。
然后O(n2)dpO(n^2)dpO(n2)dp即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int N5100,XJQ998244353;
int n,d,l[N],a[N],f[N][N],c[N][N];
int power(int x,int b){int ans1;while(b){if(b1)ans(ll)ans*x%XJQ;x(ll)x*x%XJQ;b1;}return ans;
}
int main()
{scanf(%d%d,n,d);for(int i1;in;i)scanf(%d,a[i]);sort(a1,a1n); for(int in;i1;i--){int z;l[i]i;for(zi;zna[i]da[z];z);z--;l[i]l[z];}f[1][0]c[0][0]1;for(int i1;in;i){for(int j0;jn;j){int wl[i]-i1;(f[l[i]1][jw]f[i][j])%XJQ;(f[i1][j]f[i][j])%XJQ;}}for(int i1;in1;i)for(int j1;jn1;j)c[i][j](c[i-1][j]c[i-1][j-1])%XJQ;for(int i1;in;i)printf(%d\n,(ll)f[n1][i]*power(c[n1][i1],XJQ-2)%XJQ);
}
