做电商网站运营,如何建立个人网站,谁有人和兽做的网站?,谷歌商店下载不了软件传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个生成器#xff0c;每次生成1−n1-n1−n其中的某个数的概率为pip_ipi#xff0c;生成的规则如下#xff1a; (1)(1)(1)随机生成一个数加入集合。 (2)(2)(2)判断生成的数是否是集合中的最大值思路题意
给你一个生成器每次生成1−n1-n1−n其中的某个数的概率为pip_ipi生成的规则如下 (1)(1)(1)随机生成一个数加入集合。 (2)(2)(2)判断生成的数是否是集合中的最大值如果是返回第一步否则进行下一步。 (3)(3)(3)如果集合中有xxx个数那么将会得到x2x^2x2的分数。 现在让你求期望得到多少分。 n≤100n\le100n≤100
思路
题解是生成函数的做法需要推公式之后可能会补上要是忙的话就了这里介绍期望dpdpdp的做法。 众嗦粥汁期望dpdpdp大部分是需要倒着来的倒着来比较好考虑所以难点就在设计状态上了。我感觉期望dpdpdp能清楚的设计出状态的含义就成功一大半了而不是对于状态的含义模糊不清这样是很难设计初始状态以及计算答案的。 考虑到生成的数是有可能无限的且贡献是x2x^2x2这个x2x^2x2不能直接维护考虑转换。 E((x1)2)E(x22∗x1)E(x2)2∗E(x)1E((x1)^2)E(x^22*x1)E(x^2)2*E(x)1E((x1)2)E(x22∗x1)E(x2)2∗E(x)1 所以我们设计状态dp[i]dp[i]dp[i]表示最大值为iii的时候还能生成数的期望个数f[i]f[i]f[i]表示最大值为iii的时候还能生成数的期望个数的平方。 既然含义有了那么转移方式就是 概率×(贡献下一个状态的期望)转移方程即dp[i]∑jinpj∗(dp[j]1)∑j1i−1pjdp[i]\sum _{ji}^np_j*(dp[j]1)\sum_{j1}^{i-1}p_jdp[i]ji∑npj∗(dp[j]1)j1∑i−1pjf[i]∑jinpj∗(f[j]2∗dp[j]1)∑j1i−1pjf[i]\sum _{ji}^np_j*(f[j]2*dp[j]1)\sum _{j1}^{i-1}p_jf[i]ji∑npj∗(f[j]2∗dp[j]1)j1∑i−1pj 说一下我对这个方程的理解吧每个方程的前一半就是从后面的某个合法状态转移过来注意需要加上相应的贡献。后半部分就是从结束的状态转移过来由于只能执行一步所以贡献是111和121^212。 还有这两个方程不难发现左右都有dp[i],f[i]dp[i],f[i]dp[i],f[i]我们移一下项即可。 维护前缀和和后缀和可以做到O(nlogn)O(nlogn)O(nlogn)但貌似没必要
// Problem: Sample Game
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11255/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N110,mod998244353,INF0x3f3f3f3f;
const double eps1e-6;int n;
LL p[N];
LL f[N],dp[N],pre[N];LL qmi(LL a,LL b) {LL ans1; amod; a%mod;while(b) {if(b1) ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinn;for(int i1;in;i) cinp[i];LL t0; for(int i1;in;i) tp[i]; tqmi(t,mod-2);for(int i1;in;i) (p[i]*t)%mod,pre[i]pre[i-1]p[i];LL suf0,ans0;for(int in;i1;i--) {dp[i](sufpre[i])%mod;(dp[i]*qmi(1-p[i],mod-2))%mod;(sufp[i]*(dp[i]1)%mod)%mod;}suf0;for(int in;i1;i--) {f[i]sufpre[i]2*p[i]*dp[i]%mod; f[i]%mod;(f[i]*qmi(1-p[i],mod-2))%mod;sufp[i]*(f[i]2*dp[i]1)%mod; suf%mod;ans(f[i]2*dp[i]1)*p[i]%mod; ans%mod;}printf(%lld\n,ans);return 0;
}
/**/
