2018.12.12 codeforces 935D. Fafa and Ancient Alphabet(概率dp)

时间:2022-09-05 16:17:05

传送门

概率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)的更多相关文章

  1. Codeforces 935D Fafa and Ancient Alphabet

    题目链接 题意 给定两个\(n\)位的\(m\)进制数\(s1,s2\),所有出现的\(0\)均可等概率地被其他数字替换,求\(s1\gt s2\)的概率. 思路 从高位到低位,根据每一位上相应的\( ...

  2. CodeForces 935E Fafa and Ancient Mathematics &lpar;树形DP&rpar;

    题意:给定一个表达式,然后让你添加 n 个加号,m 个减号,使得表达式的值最大. 析:首先先要建立一个表达式树,这个应该很好建立,就不说了,dp[u][i][0] 表示 u 这个部分表达式,添加 i ...

  3. Codeforces 935E Fafa and Ancient Mathematics dp

    Fafa and Ancient Mathematics 转换成树上问题dp一下. #include<bits/stdc++.h> #define LL long long #define ...

  4. Codeforces B&period; Bad Luck Island(概率dp)

    题目描述: Bad Luck Island time limit per test 2 seconds memory limit per test 256 megabytes input standa ...

  5. Codeforces 678E&period; Another Sith Tournament(概率DP,状压)

    Codeforces 678E. Another Sith Tournament 题意: n(n<=18)个人打擂台赛,给定任意两人对决的胜负概率,比赛规则:可指定一人作为最开始的擂主,每次可指 ...

  6. 2018&period;12&period;12 codeforces 931E&period; Game with String(概率dp)

    传送门 感觉这题难点在读懂题. 题目简述:给你一个字符串s,设将其向左平移k个单位之后的字符串为t,现在告诉你t的第一个字符,然后你可以另外得知t的任意一个字符,求用最优策略猜对k的概率. 解析: 预 ...

  7. Codeforces 935E Fafa and Ancient Mathematics(表达式转树 &plus; 树型DP)

    题目链接  Codeforces Round #465 (Div. 2) Problem E 题意  给定一个表达式,然后用$P$个加号和$M$个减号填充所有的问号(保证问号个数等于$P + M$) ...

  8. codeforce465DIV2——D&period; Fafa and Ancient Alphabet

    概率的计算答案给出的这张图很清楚了,然后因为要求取模,a/b%M=a*b^-1%M=a*inv(b,M)%M; #include <cstdio> #include <cstring ...

  9. 【学术篇】CF935E Fafa and Ancient Mathematics 树形dp

    前言 这是一道cf的比赛题.. 比赛的时候C题因为自己加了一个很显然不对的特判WA了7次但找不出原因就弃疗了... 然后就想划水, 但是只做了AB又不太好... 估计rating会掉惨 (然而事实证明 ...

随机推荐

  1. 小小改动帮你减少bundle&period;js文件体积(翻译)

    我已经从事过好多年的SPA开发工作,我发现很多的程序猿都从来不往 bundle.js 文件的体积上动脑筋,这让我有点懵逼. “安心洗路,等俺把代码混淆压缩后就一切666了”,若是有人这么说,我会翻白眼 ...

  2. windows下安装python模块

    如何在windows下安装python模块 1. 官网下载安装包,比如(pip : https://pypi.python.org/pypi/pip#downloads) pip-9.0.1.tar. ...

  3. JavaScript 基础第二天

    一.前言 感觉昨天的内容确实是有点细碎.复杂.感觉是没有书上写的那么的细致而且有导入性,但是我还是喜欢这样只说干货.今天的内容将继续接着昨天最后的内容JS中的语言结构继续讲解并且重点讲解一下其中的内容 ...

  4. Hadoop 权威指南学习1 &lpar;主要框架)

    1. Hadoop 最出名的是 MapReduce和 HDFS,不过也有很多其他有用的子项目. 技术栈如下: Core 一系列分布式文件系统和通用I/O的组件和接口(序列化.Java RPC和持久化数 ...

  5. Entity Framework 实体关系总结

    刚开始使用 Entity Framework 的时候,由于没有静下心来认真理清关系,走了一些"痛不欲生"的弯路.而我们目前开发的项目都在使用 Entity Framework,为了 ...

  6. ArcGIS中定义图框样式

    ArcGIS系统中的样式可能不能满足实际生产需要,为了实现快速制图,可自定义一些样式,以便重复利用. 安装字符 因为样式中定义了自定义的符号,这些符号都打包到字体中,所以在使用样式之前,必须安装字体文 ...

  7. 那些年被我坑过的Python——摩拳擦掌(第三章)

    集合类型: 集合类型中的元素是唯一的! 集合的定义与赋值: set_1 = set([1, 3, 5, 7, 2]) set_2 = set([2, 4, 6, 8, 3]) 集合的运算操作 # 交集 ...

  8. restfull环境搭建-helloword(二)

    原文地址:http://only81.iteye.com/blog/1689537 本文描述,获取XML或json格式数据 首先,创建一个bean,比如Todo(JAXB自动将bean文件,转换成xm ...

  9. Codeforces Round &num;519 by Botan Investments F&period; Make It One

    https://codeforces.com/contest/1043/problem/F 题意 给你n个数,求一个最小集合,这个集合里面数的最大公因数等于1 1<=n<=3e5 1&lt ...

  10. 探究Entity Framework如何在多个仓储层实例之间工作单元的实现及原理(2018-05-31修改部分严重错误代码)

    前言 1.本文的前提条件:EF上下文是线程唯一,EF版本6.1.3. 2.网上已有相关API的详细介绍,本文更多的是作为我自己的个人学习研究记录. 3.2018-05-31修改DbSession.cs ...