传送门
概率dp水题。
题意简述:给你数字表的大小和两个数列,数列中为0的数表示不确定,不为0的表示确定的,求第一个数列字典序比第二个数列大的概率。
fif_ifi表示第i ni~ ni n位第一个数列比第二个数列大的概率。
然后分是否为0的情况讨论一下就行了。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
typedef long long ll;
int n,m,f[N],a[N],b[N],add,inv;
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}
inline int calc(int a,int b){return (ll)a*ksm(b,mod-2)%mod;}
int main(){
freopen("lx.in","r",stdin);
n=read(),m=read(),add=(ll)m*(m-1)/2%mod,inv=ksm(m,mod-2);
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1;i<=n;++i)b[i]=read();
for(ri i=n;i;--i){
if(a[i]&&b[i])f[i]=a[i]==b[i]?f[i+1]:(a[i]>b[i]?1:0);
else if(a[i])f[i]=(ll)(a[i]-1+f[i+1])*inv%mod;
else if(b[i])f[i]=(ll)(m-b[i]+f[i+1])*inv%mod;
else f[i]=(ll)(add+(ll)m*f[i+1]%mod)*inv%mod*inv%mod;
}
cout<<f[1];
return 0;
}
2018.12.12 codeforces 935D. Fafa and Ancient Alphabet(概率dp)的更多相关文章
-
Codeforces 935D Fafa and Ancient Alphabet
题目链接 题意 给定两个\(n\)位的\(m\)进制数\(s1,s2\),所有出现的\(0\)均可等概率地被其他数字替换,求\(s1\gt s2\)的概率. 思路 从高位到低位,根据每一位上相应的\( ...
-
CodeForces 935E Fafa and Ancient Mathematics (树形DP)
题意:给定一个表达式,然后让你添加 n 个加号,m 个减号,使得表达式的值最大. 析:首先先要建立一个表达式树,这个应该很好建立,就不说了,dp[u][i][0] 表示 u 这个部分表达式,添加 i ...
-
Codeforces 935E Fafa and Ancient Mathematics dp
Fafa and Ancient Mathematics 转换成树上问题dp一下. #include<bits/stdc++.h> #define LL long long #define ...
-
Codeforces B. Bad Luck Island(概率dp)
题目描述: Bad Luck Island time limit per test 2 seconds memory limit per test 256 megabytes input standa ...
-
Codeforces 678E. Another Sith Tournament(概率DP,状压)
Codeforces 678E. Another Sith Tournament 题意: n(n<=18)个人打擂台赛,给定任意两人对决的胜负概率,比赛规则:可指定一人作为最开始的擂主,每次可指 ...
-
2018.12.12 codeforces 931E. Game with String(概率dp)
传送门 感觉这题难点在读懂题. 题目简述:给你一个字符串s,设将其向左平移k个单位之后的字符串为t,现在告诉你t的第一个字符,然后你可以另外得知t的任意一个字符,求用最优策略猜对k的概率. 解析: 预 ...
-
Codeforces 935E Fafa and Ancient Mathematics(表达式转树 + 树型DP)
题目链接 Codeforces Round #465 (Div. 2) Problem E 题意 给定一个表达式,然后用$P$个加号和$M$个减号填充所有的问号(保证问号个数等于$P + M$) ...
-
codeforce465DIV2——D. Fafa and Ancient Alphabet
概率的计算答案给出的这张图很清楚了,然后因为要求取模,a/b%M=a*b^-1%M=a*inv(b,M)%M; #include <cstdio> #include <cstring ...
-
【学术篇】CF935E Fafa and Ancient Mathematics 树形dp
前言 这是一道cf的比赛题.. 比赛的时候C题因为自己加了一个很显然不对的特判WA了7次但找不出原因就弃疗了... 然后就想划水, 但是只做了AB又不太好... 估计rating会掉惨 (然而事实证明 ...
随机推荐
-
小小改动帮你减少bundle.js文件体积(翻译)
我已经从事过好多年的SPA开发工作,我发现很多的程序猿都从来不往 bundle.js 文件的体积上动脑筋,这让我有点懵逼. “安心洗路,等俺把代码混淆压缩后就一切666了”,若是有人这么说,我会翻白眼 ...
-
windows下安装python模块
如何在windows下安装python模块 1. 官网下载安装包,比如(pip : https://pypi.python.org/pypi/pip#downloads) pip-9.0.1.tar. ...
-
JavaScript 基础第二天
一.前言 感觉昨天的内容确实是有点细碎.复杂.感觉是没有书上写的那么的细致而且有导入性,但是我还是喜欢这样只说干货.今天的内容将继续接着昨天最后的内容JS中的语言结构继续讲解并且重点讲解一下其中的内容 ...
-
Hadoop 权威指南学习1 (主要框架)
1. Hadoop 最出名的是 MapReduce和 HDFS,不过也有很多其他有用的子项目. 技术栈如下: Core 一系列分布式文件系统和通用I/O的组件和接口(序列化.Java RPC和持久化数 ...
-
Entity Framework 实体关系总结
刚开始使用 Entity Framework 的时候,由于没有静下心来认真理清关系,走了一些"痛不欲生"的弯路.而我们目前开发的项目都在使用 Entity Framework,为了 ...
-
ArcGIS中定义图框样式
ArcGIS系统中的样式可能不能满足实际生产需要,为了实现快速制图,可自定义一些样式,以便重复利用. 安装字符 因为样式中定义了自定义的符号,这些符号都打包到字体中,所以在使用样式之前,必须安装字体文 ...
-
那些年被我坑过的Python——摩拳擦掌(第三章)
集合类型: 集合类型中的元素是唯一的! 集合的定义与赋值: set_1 = set([1, 3, 5, 7, 2]) set_2 = set([2, 4, 6, 8, 3]) 集合的运算操作 # 交集 ...
-
restfull环境搭建-helloword(二)
原文地址:http://only81.iteye.com/blog/1689537 本文描述,获取XML或json格式数据 首先,创建一个bean,比如Todo(JAXB自动将bean文件,转换成xm ...
-
Codeforces Round #519 by Botan Investments F. Make It One
https://codeforces.com/contest/1043/problem/F 题意 给你n个数,求一个最小集合,这个集合里面数的最大公因数等于1 1<=n<=3e5 1< ...
-
探究Entity Framework如何在多个仓储层实例之间工作单元的实现及原理(2018-05-31修改部分严重错误代码)
前言 1.本文的前提条件:EF上下文是线程唯一,EF版本6.1.3. 2.网上已有相关API的详细介绍,本文更多的是作为我自己的个人学习研究记录. 3.2018-05-31修改DbSession.cs ...