当前位置: 首页 > news >正文

小购物网站建设东莞做网站推广

小购物网站建设,东莞做网站推广,临沂自助建站软件,广东省建设执业资格注册中心官方网站正题 题目链接:https://www.luogu.com.cn/problem/P4548 题目大意 ttt次询问#xff0c;给出一个长度为mmm的串SSS和一个空串TTT#xff0c;每次在TTT后面随机加入1∼n1\sim n1∼n的字符#xff0c;直到TTT中出现SSS为止#xff0c;求期望次数。 1≤n≤105,t≤50,1≤m≤10…正题 题目链接:https://www.luogu.com.cn/problem/P4548 题目大意 ttt次询问给出一个长度为mmm的串SSS和一个空串TTT每次在TTT后面随机加入1∼n1\sim n1∼n的字符直到TTT中出现SSS为止求期望次数。 1≤n≤105,t≤50,1≤m≤1051\leq n\leq 10^5,t\leq 50,1\leq m\leq 10^51≤n≤105,t≤50,1≤m≤105 解题思路 对于一个随机的数字XXX它的概率生成函数是一个形如 F(x)∑i0∞P(Xi)xiF(x)\sum_{i0}^\infty P(Xi)x^iF(x)i0∑∞​P(Xi)xi F′(x)∑i1∞P(Xi)ixi−1F(x)\sum_{i1}^\infty P(Xi)ix^{i-1}F′(x)i1∑∞​P(Xi)ixi−1 不难发现数字XXX的期望值就是E(X)F′(1)E(X)F(1)E(X)F′(1) 然后还有一个不知道有啥用的XXX的方差大概就是离散程度 V(X)F′′(1)F′(1)−F′(1)2V(X)F(1)F(1)-F(1)^2V(X)F′′(1)F′(1)−F′(1)2 这题的话设两个生成函数F(x)F(x)F(x)表示停止时间XXX的概率生成函数还有一个G(x)G(x)G(x)表示没有停止时间的概率不是概率生成函数具体地 G(x)∑i0∞P(iX)xiG(x)\sum_{i0}^\infty P(iX)x^iG(x)i0∑∞​P(iX)xi 然后我们就有两个式子 xG(x)1F(x)G(x)xG(x)1F(x)G(x)xG(x)1F(x)G(x) 这个式子的含义很好理解在还没有结束的序列后面加入一个字符要么结束了要么没结束。 (xn)mG(x)∑i1m(xn)m−ibiF(x)\left(\frac{x}{n}\right)^mG(x)\sum_{i1}^m \left(\frac{x}{n}\right)^{m-i}b_iF(x)(nx​)mG(x)i1∑m​(nx​)m−ibi​F(x) bib_ibi​表示iii是否是串SSS的一个borderborderborder这个式子的意思就是说在直接在未结束的TTT后面插入一个SSS此时可能提前结束。 然后这两个式子怎么用呢我们对第一个式子求导就有 G(x)G′(x)F′(x)G′(x)⇒F′(x)G(x)G(x)G(x)F(x)G(x)\Rightarrow F(x)G(x)G(x)G′(x)F′(x)G′(x)⇒F′(x)G(x) 也就是说我们要求的E(X)F′(1)G(1)E(X)F(1)G(1)E(X)F′(1)G(1) 然后直接带入第二个式子因为有F(1)1F(1)1F(1)1所以 (1n)mG(1)∑i1m(1n)m−ibiF(1)\left(\frac{1}{n}\right)^mG(1)\sum_{i1}^m \left(\frac{1}{n}\right)^{m-i}b_iF(1)(n1​)mG(1)i1∑m​(n1​)m−ibi​F(1) ⇒G(1)∑i1mnibi\Rightarrow G(1)\sum_{i1}^mn^ib_i⇒G(1)i1∑m​nibi​ 用KMPKMPKMP求出bbb数组即可。 时间复杂度O(Tm)O(Tm)O(Tm) code #includecstdio #includecstring #includealgorithm #define ll long long using namespace std; const ll N1e510,P1e4; ll T,m,n,pw[N],a[N],nxt[N]; signed main() {scanf(%lld%lld,m,T);pw[0]1;for(ll i1;iN;i)pw[i]pw[i-1]*m%P;while(T--){scanf(%lld,n);ll ans0;for(ll i1;in;i)scanf(%lld,a[i]);for(ll i2,j0;in;i){while(ja[j1]!a[i])jnxt[j];j(a[j1]a[i]);nxt[i]j;}for(ll in;i;inxt[i])(anspw[i])%P;printf(%04lld\n,ans);}return 0; }
http://www.pierceye.com/news/174048/

相关文章:

  • WordPress站群更新wordpress 图片命名吗
  • 网站建设最好的公司哪家好网站模板下载软件
  • 运输公司网站模板网站建设及使用
  • 哈尔滨cms模板建站网站建设天地心
  • 廊坊代运营公司广东网站se0优化公司
  • 西双版纳建设厅网站宁夏建网站报价
  • 网站优化分析软件手机端网站源码
  • 我想克隆个网站 怎么做网站 运营工作如何做
  • 承德网站制作公司哪家好如何选择邯郸网站建设
  • 网络分析的应用案例广东网络seo推广平台
  • 网站开发设计合同北京网站排名优化公司
  • 免费建立个人网站凡科怎么下载app
  • 网站题头是什么做线上网站需要钱吗
  • 陕西省建设工程监理协会网站 查询动易网站首页错位
  • 老公做网站网站推广wordpress 文件加载顺序
  • 网站开发保存学习进度的方案搭建网站免费
  • 做网站对外贸有什么用网站怎么防k
  • 网站开发网站建设常州建站程序
  • 赤峰建设局网站物流公司网站制作模板
  • 装修第三方平台网站建设网站开发及设计
  • 男女做那个的小视频网站个人如何注册公司流程
  • 机关网站建设前期准备工作wordpress替代
  • 机关网站建设无锡宜兴网站建设
  • 江苏景禾瑜博建设工程有限公司网站做网站注册公司
  • 如何找到做网站的客户贵州二建报名入口官网
  • 网站怎么做301定向wordpress极客式主题
  • 造价工程建设协会网站怎么把做的网站发布
  • 万网网站首页好企业网站
  • 廊坊做网站电话企业网络搭建拓扑图
  • 建设社区网站有什么借鉴之处专业网站制作哪家专业