Codeforces 908 D.New Year and Arbitrary Arrangement (概率&期望DP)

时间:2022-04-08 05:42:10

题目链接:New Year and Arbitrary Arrangement

题意:  

 有一个ab字符串,初始为空。 用Pa/(Pa+Pb)的概率在末尾添加字母a,有 Pb/(Pa+Pb)的概率在末尾添加字母b,当出现≥k个ab子串时立即停止添加字母,求最后期望的ab子串个数。(子串ab不要求连续) 例子:当k=1,aab含2个ab,bbabbab时不可能出现的,因为到了bbab就会停止添加字母。

题解: 期望DP

  DP果然是智商的分界线 orz @。@#,这题题意其实我也没看太懂,后来看了别人的博客才勉强写出来。。。

 #include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e3+;
const int MOD = 1e9+;
long long k,pa,pb;
int DP[MAX_N][MAX_N];
long long quick_mod(long long x,int p)
{
long long ans = ;
long long base = x;
while(p)
{
if(p&) ans = ans*base %MOD;
p>>=;
base = (base*base)%MOD;
}
return ans;
}
long long inv(long long x)
{
return quick_mod(x,MOD-);
}
long long make_DP(long long i,long long j)
{
if(i+j>=k)
return (i+j+pa*inv(pb)%MOD)%MOD;
if(DP[i][j] != -)
return DP[i][j];
return DP[i][j] = ((pa*make_DP(i+,j)%MOD) + (pb*make_DP(i,i+j)%MOD))*inv(pa+pb) %MOD;
}
int main()
{
while(cin>>k>>pa>>pb)
{
memset(DP,-,sizeof(DP));
//cout<<"......"<<DP[2][0]<<endl;
cout<<make_DP(,)<<endl;
}
return ;
}

  

Codeforces 908 D.New Year and Arbitrary Arrangement (概率&期望DP)的更多相关文章

  1. Codeforces 908 D New Year and Arbitrary Arrangement

    Discription You are given three integers k, pa and pb. You will construct a sequence with the follow ...

  2. Codeforces - 1264C - Beautiful Mirrors with queries - 概率期望dp

    一道挺难的概率期望dp,花了很长时间才学会div2的E怎么做,但这道题是另一种设法. https://codeforces.com/contest/1264/problem/C 要设为 \(dp_i\ ...

  3. 【CodeForces】908 D&period; New Year and Arbitrary Arrangement

    [题目]Good Bye 2017 D. New Year and Arbitrary Arrangement [题意]给定正整数k,pa,pb,初始有空字符串,每次有pa/(pa+pb)的可能在字符 ...

  4. CF 908 D New Year and Arbitrary Arrangement —— 期望DP

    题目:http://codeforces.com/contest/908/problem/D 首先,设 f[i][j] 表示有 i 个 a,j 个 ab 组合的期望,A = pa / (pa + pb ...

  5. Codeforces 446D - DZY Loves Games(高斯消元&plus;期望 DP&plus;矩阵快速幂)

    Codeforces 题目传送门 & 洛谷题目传送门 神仙题,%%% 首先考虑所有格子都是陷阱格的情况,那显然就是一个矩阵快速幂,具体来说,设 \(f_{i,j}\) 表示走了 \(i\) 步 ...

  6. &lbrack;CodeForces&rsqb;908D New Year and Arbitrary Arrangement

    设状态f[i][j]表示有i个a,j个ab的期望 发现如果i+j>=k的话就再来一个b就行了. #include <iostream> #include <cstdio> ...

  7. Codeforces New Year and Arbitrary Arrangement

    New Year and Arbitrary Arrangement time limit per test2 seconds You are given three integers k, pa a ...

  8. Codeforces Round &num;164 &lpar;Div&period; 2&rpar; E&period; Playlist 贪心&plus;概率dp

    题目链接: http://codeforces.com/problemset/problem/268/E E. Playlist time limit per test 1 secondmemory ...

  9. &lbrack;Codeforces 865C&rsqb;Gotta Go Fast&lpar;期望dp&plus;二分答案&rpar;

    [Codeforces 865C]Gotta Go Fast(期望dp+二分答案) 题面 一个游戏一共有n个关卡,对于第i关,用a[i]时间通过的概率为p[i],用b[i]通过的时间为1-p[i],每 ...

随机推荐

  1. Linux CentOS 7通过yum命令安装Mono4&period;0&period;1

    前言 上一篇中提到的快照方式安装Mono,该方式并不稳定,需要做各种配置,各种修改才能与jexus搭配运行. 一.安装源 rpm --import "http://keyserver.ubu ...

  2. C&plus;&plus;输入输出

    i. C++如何输入一行,按回车键结束 #include <sstream>1 getline(cin, line); istringstream input(line); ii. C++ ...

  3. 读取Assets中的文件数据

    try { // 返回的字节流 InputStream is = getResources().getAssets().open("info.txt"); // 当读取时,属于文本 ...

  4. -ms-viewport的问题

    Windows 8 中的 Internet Explorer 10 和 Windows Phone 8 Internet Explorer 10 doesn't differentiate devic ...

  5. DotNetZip封装类

      DotnetZip是一个开源类库,支持.NET的任何语言,可很方便的创建,读取,和更新zip文件.而且还可以使用在.NETCompact Framework中. 下载地址在这里: http://d ...

  6. 带搜索的下拉框Chosen

    一:参考 https://harvesthq.github.io/chosen/ Chosen是一个jQuery插件 二:引入js文件 <link href="plug-in/chos ...

  7. Xamarin for OSX – SetUp

    正常情况联网会失败 按照安装顺序进行安装(mono framework->java sdk-> android sdk->xamarin studio->xamarin.and ...

  8. grep废弃

    grep -inrw 字符串 .grep -i是忽略大小写的意思cat xxx|grep -i mem 会把文本里的MEM,meM.....等无关乎大小写的内容取出来grep -inrwgrep &q ...

  9. The Non-Inverting Amplifier Output Resistance by Adrian S&period; Nastase &lbrack;转载&rsqb;

    Source Address: http://masteringelectronicsdesign.com/the-non-inverting-amplifier-output-resistance/ ...

  10. AI创业的技术方案选择

    观察了许多初创公司技术方案的选择,我总结基本遵循8个字:快速灵活,物美价廉.我们也应该根据自身实际情况,跳出束缚与时俱进,选择智能互联网时代最有力的技术和工具. 基础编程语言 候选者:C#/C++/P ...