自己做网站吗,电子商务网站建设工具都有那些,公司注册代理免费咨询,网站建设方案开发正题
题目链接:https://www.luogu.com.cn/problem/P4707 题目大意 nnn个物品#xff0c;每次生成一种物品#xff0c;第iii个被生成的概率是pim\frac{p_i}{m}mpi#xff0c;求生成至少kkk种物品的期望次数。 1≤n≤1000,max{n−10,1}≤k≤n,1≤m≤100001\leq n\leq 100…正题
题目链接:https://www.luogu.com.cn/problem/P4707 题目大意
nnn个物品每次生成一种物品第iii个被生成的概率是pim\frac{p_i}{m}mpi求生成至少kkk种物品的期望次数。
1≤n≤1000,max{n−10,1}≤k≤n,1≤m≤100001\leq n\leq 1000,max\{n-10,1\}\leq k\leq n,1\leq m\leq 100001≤n≤1000,max{n−10,1}≤k≤n,1≤m≤10000 解题思路
求的是E(mink{S})E(min_k\{S\})E(mink{S})但是kkk很大如果令kn−k1kn-k1kn−k1的话就是求E(maxk{S})E(max_k\{S\})E(maxk{S})了
然后就可以用min−maxmin-maxmin−max容斥的扩展了
maxk(S)∑T∈S(−1)∣T∣−k(∣T∣−1k−1)min(T)max_k(S)\sum_{T\in S}(-1)^{|T|-k}\binom{|T|-1}{k-1}min(T)maxk(S)T∈S∑(−1)∣T∣−k(k−1∣T∣−1)min(T)
然后minminmin的话挺好搞的因为这个集合中的所有物品都可以视为一个物品所以期望就是m∑i∈Tpi\frac{m}{\sum_{i\in T}p_i}∑i∈Tpim
然后因为显然不能暴力枚举集合所以我们考虑dpdpdp。设fk,i,jf_{k,i,j}fk,i,j表示做到第kkk个物品目前的∑i∈Tpim\sum_{i\in T}p_im∑i∈Tpim然后上面那个式子的′k′k′k′的值是jjj时上面那个式子的和。
因为有个组合数转移起来挺麻烦的不选的话就是fk−1,i,jf_{k-1,i,j}fk−1,i,j不再多说但是如果选的话那个(−1)∣T∣−k(-1)^{|T|-k}(−1)∣T∣−k直接取反就好了但是那个组合数的上那个也加了111。
这里我们直接用那个组合数的式子(nm)(n−1m−1)(n−1m)\binom{n}{m}\binom{n-1}{m-1}\binom{n-1}{m}(mn)(m−1n−1)(mn−1)。虽然上面那个式子的kkk是不变的但是我们记录了其他的kkk的值其实如果选的话转移就是 fk,i,jfk−1,i,jfk−1,i−pk,j−1−fk−1,i−pk,jf_{k,i,j}f_{k-1,i,j}f_{k-1,i-p_k,j-1}-f_{k-1,i-p_{k},j}fk,i,jfk−1,i,jfk−1,i−pk,j−1−fk−1,i−pk,j 这样我们的式子就是O(nmk)O(nmk)O(nmk)的了。
然后初始化的话为了满足后面的定义让所有的f0,0,i−1(i∈[1,m])f_{0,0,i}-1(i\in[1,m])f0,0,i−1(i∈[1,m])就好了。 #includecstdio
#includecstring
#includealgorithm
using namespace std;
const int P998244353;
int n,k,m,f[11000][11],ans;
int power(int x,int b){int ans1;while(b){if(b1)ans1ll*ans*x%P;x1ll*x*x%P;b1;}return ans;
}
int main()
{scanf(%d%d%d,n,k,m);kn-k1;for(int p1;pk;p)f[0][p]-1;for(int p1;pn;p){int x;scanf(%d,x);for(int im;ix;i--)for(int jk;j1;j--)(f[i][j](f[i-x][j-1]-f[i-x][j]P)%P)%P;}for(int p1;pm;p)(ans1ll*f[p][k]*power(p,P-2)%P)%P;printf(%d\n,1ll*ans*m%P);return 0;
}
