题目:http://codeforces.com/contest/908/problem/D

注意是子序列。加一个a对ab个数无影响;加一个b使ab个数多出它前面的a那么多个。所以状态里记录有多少个a和ab。

当 i+j>=k 的时候,再加一个b就结束了。用式子算一下期望,发现一个等比数列;用等比数列的公式算一下,变成一个值减去一个无限小的值,所以就是那个值了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,mod=1e9+;
int n,A,B,tmp,C,dp[N][N];
bool vis[N][N];
int pw(int x,int k)
{
int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;
}
int dfs(int i,int j)
{
if(vis[i][j])return dp[i][j];
vis[i][j]=;
if(i+j>=n) return dp[i][j]=(i+j+C)%mod;
dp[i][j]=((ll)A*dfs(i+,j)+(ll)B*dfs(i,i+j))%mod;
return dp[i][j];
}
int main()
{
scanf("%d%d%d",&n,&A,&B);
tmp=pw(A+B,mod-); C=(ll)A*pw(B,mod-)%mod;
A=(ll)A*tmp%mod; B=(ll)B*tmp%mod;
printf("%d\n",dfs(,));
return ;
}

最新文章

  1. Oracle【IT实验室】数据库备份与恢复之四:RMAN(备份与恢复管理器)
  2. Task&lt;TResult&gt;的使用
  3. SAP 默认的连接端口
  4. poj 3686
  5. 通过Javascript模拟登陆Windows认证的网站
  6. Java官方Demo Mark
  7. Kettle中通过触发器方式实现数据 增量更新
  8. onContextItemSelected 用法
  9. RequireJS进阶(三)
  10. (收藏)KMP算法的前缀next数组最通俗的解释
  11. Android推断程序前后台状态
  12. 【C++自我精讲】基础系列四 static
  13. SharePoint 2013 APP 开发示例 (二)获取用户信息
  14. Taro-ui TabBar组件使用路由跳转
  15. centos7 Mycat/MySQL/MariaDB安装部署
  16. Django REST Framework限速
  17. flask通过form表单一次上传多个文件
  18. ImageView setImageURI图片不改变\NetWorkImageView 不显示的问题
  19. (总结)CentOS 6.x使用yum快速安装Apache+PHP+Tomcat(JSP)+MySQL
  20. HTML引入JS文件

热门文章

  1. STM32 I2C
  2. MySQL的几种登陆方式
  3. 开源监控软件ganglia
  4. XMPP资源绑定(Resource Binding)
  5. Java 获取本地IP地址
  6. 18- php Redis扩展编译
  7. 高速修复汉澳sinox命令解释程序bash shell漏洞
  8. 【bootstrap】右侧sidebar不跟着内容滚动的异常
  9. Epplus使用技巧
  10. iPhone与iPad开发实战读书笔记