【CF908D】New Year and Arbitrary Arrangement
2024-09-01 23:59:45
Problem
Description
给定三个数 \(k,pa,pb\) ,每次有 \(\frac{pa}{pa+pb}\) 的概率往后面添加一个 a
,有 \(\frac{pb}{pa+pb}\) 的概率往后面添加一个 b
,当出现了 \(k\) 个形如 ab
的子序列(不用连续)时停止。
求最后子序列 ab
的期望个数。
答案对 \(10^9+7\) 取模。
Sample
Input 1
1 1 1
Output 1
2
Input 2
3 1 4
Output 2
370000006
Range
\(k\le1000,p_a,p_b\le10^6\)
Algorithm
\(DP\),概率与期望
Mentality
设 \(f_{i,j}\) 表示当前有 \(i\) 个 \(a\) ,\(j\) 个子序列 \(ab\) ,在整个序列结束时的子序列 \(ab\) 的期望个数。发现第一维可能无限大,考虑倒推。
\(f_{i,j}\) 的转移有两种情况,一是在末尾加入 \(a\) ,转移至 \(f_{i+1,j}\) ,而是加入 \(b\) 转移至 \(f_{i,j+i}\) 。那么倒推的方程就很明显了:
\[f_{i,j}=\frac{p_a}{p_a+p_b}f_{i+1,j}+\frac{p_b}{p_a+p_b}f_{i,j+1}
\]
\]
不过第一维无限大的问题还是没解决,必须考虑边界的问题。
我们发现,当 \(i+j\ge k\) 的时候,如果我们加入 \(b\) ,则整个串就会立即终止。
那么对于一个状态 \(f_{i,j},(i+j\ge k)\) 来说,设在此状态上连续加入 \(x\) 个 \(a\) 再加入一个 \(b\) ,则:
\[f_{i,j}=\frac{p_b}{p_a+p_b}\sum_{x=0}^\infty(i+j+x)(\frac{p_a}{p_a+p_b})^x
\]
\]
这是一个等比数列,那么我们直接等比数列求和就好了。
算出来得到:
\[f_{i,j}=i+j+\frac{p_a}{p_b}
\]
\]
直接记搜就星了。
Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
long long read() {
long long x = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * w;
}
const int Max_n = 1e3 + 5, mod = 1e9 + 7;
int n, a, b;
int pa, pb, pp;
int f[Max_n][Max_n];
int ksm(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod)
if (b & 1) res = 1ll * res * a % mod;
return res;
}
int DP(int a, int ab) {
int &res = f[a][ab];
if (res != -1) return res;
if (a + ab >= n) {
res = (a + ab + pp) % mod;
return res;
}
return res =
(1ll * pa * DP(a + 1, ab) % mod + 1ll * pb * DP(a, ab + a) % mod) %
mod;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("D.in", "r", stdin);
freopen("D.out", "w", stdout);
#endif
n = read(), a = read(), b = read();
pa = 1ll * a * ksm(a + b, mod - 2) % mod;
pb = 1ll * b * ksm(a + b, mod - 2) % mod;
pp = 1ll * a * ksm(b, mod - 2) % mod;
memset(f, -1, sizeof(f));
printf("%d\n", DP(1, 0));
}
最新文章
- 企业IT管理员IE11升级指南【7】—— Win7和Win8.1上的IE11功能对比
- python之路十
- javascript 杂记
- C#再识委托
- java对象序列化byte[] and byte[]反序列化对象--转
- discuz插件开发新手入门 超详细
- Android 滑动冲突处理
- Ubuntu 下 安装QQ 截图工具
- spring-data-solr官方学习文档介绍
- ORACLE恢复误删除的对象(表、存储过程等)
- 基于Asterisk的VoIP开发指南——(1)实现基本呼叫功能
- WPF 杂谈——Binding表达式
- Orleans简介
- symfony generate bundle autoload failed的解决办法
- Apollo 10 — adminService 全量发布
- 使用PHP对二维索引数组进行排序
- 使用loki+ mtail + grafana + prometheus server分析应用问题
- HBase随机读写
- Hibernate 注解和配置文件两种方法的对比(有实例)
- Notes about Vue Style Guide
热门文章
- webpack学习_模块热替换(Hot Module Peaplacement)
- java基础-初识类
- Windows 10 - 查看系统剪切板历史
- Vue学习笔记:提升开发效率和体验的常用工具
- MongoDB(六):选择字段、限制记录数、排序记录
- 分布式系统的发展演变以及RPC简介
- Dynamics 365中使用计算字段自动编号字段实时工作流自动生成分组编码加流水号的自动编号字段值
- 【转】CAP 定理的含义
- 设置openwrt路由器的防火墙_允许从外网访问内网的ipv6服务
- PHP+jQuery中国地图热点数据统计展示实例