正文 

当前位置： 首页 > java > java教程

cf935dfafaandancientalphabet概率dp(递推)(代码片段)

al76 al76     2022-12-28     282

关键词：

D. Fafa and Ancient Alphabet
(简洁题意请往下翻)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ancient Egyptians are known to have used a large set of symbols 技术分享图片 to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words S1 and S2 of equal lengths on the wall of temple written one below the other. Since this temple is very ancient, some symbols from the words were erased. The symbols in the set 技术分享图片 have equal probability for being in the position of any erased symbol.

Fifa challenged Fafa to calculate the probability that S1 is lexicographically greater than S2. Can you help Fafa with this task?

You know that 技术分享图片, i. e. there were m distinct characters in Egyptians‘ alphabet, in this problem these characters are denoted by integers from 1 to m in alphabet order. A word x is lexicographically greater than a word y of the same length, if the words are same up to some position, and then the word x has a larger character, than the word y.

We can prove that the probability equals to some fraction 技术分享图片, where P and Q are coprime integers, and 技术分享图片. Print as the answer the value 技术分享图片, i. e. such a non-negative integer less than 109?+?7, such that 技术分享图片, where 技术分享图片 means that a and b give the same remainders when divided by m.

Input

The first line contains two integers n and m (1?≤?n,??m?≤?105) — the length of each of the two words and the size of the alphabet 技术分享图片, respectively.

The second line contains n integers a1,?a2,?...,?an (0?≤?ai?≤?m) — the symbols of S1. If ai?=?0, then the symbol at position i was erased.

The third line contains n integers representing S2 with the same format as S1.

Output

Print the value 技术分享图片, where P and Q are coprime and 技术分享图片 is the answer to the problem.

Examples
input
Copy
1 2
0
1
output
Copy
500000004
input
Copy
1 2
1
0
output
Copy
0
input
Copy
7 26
0 15 12 9 13 0 14
11 1 0 13 15 12 0
output
Copy
230769233
Note

In the first sample, the first word can be converted into (1) or (2). The second option is the only one that will make it lexicographically larger than the second word. So, the answer to the problem will be 技术分享图片, that is 500000004, because 技术分享图片.

In the second example, there is no replacement for the zero in the second word that will make the first one lexicographically larger. So, the answer to the problem is 技术分享图片, that is 0.

 

题意:给两个长度为n的数列,每个数列的数字范围是1-m,有可能出现缺失的部分(用0表示),在缺失的部分每个数字出现的概率相同(都是1/m),问最后a的字典序比b的大的概率.输入是 n,m 之后两行每行n个数,分别代表序列a,b.最后输出概率对1e9+7取模

提示:分数无法取模,所以要用逆元~另外要注意一下取模不然会爆

貌似有更简单的转移方式,只用一维就可以,也可以滚动数组写,但是我太弱了qwq

分几种情况讨论然后直接转移就行啦,这道题其实就是一个递推

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 #define mod 1000000007 
 6 #define ll long long
 7 using namespace std;
 8 int n,m;
 9 int a[maxn],b[maxn];
10 ll inv[maxn],f[maxn][2];//f[i][1]表示到i位为止,a>b的概率
11 ll fp(ll x,ll a)//在jms学到的神奇写法
12     ll ret=1;
13     for(x%=mod;a;a>>=1,x=x*x%mod)
14         if(a&1) ret=ret*x%mod;
15     return ret; 
16 
17 int main()
18     scanf("%d%d",&n,&m);//长度为n 字母表中有m个字母
19     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
20     for(int i=1;i<=n;i++) scanf("%d",&b[i]);
21     f[0][0]=1;
22     ll invm=fp(m,mod-2),inv2=fp(2,mod-2);
23     for(int i=1;i<=n;i++)
24         if(a[i]>b[i]&&b[i]) //这一位都已经确定,直接转移即可
25             f[i][1]=(f[i-1][1]+f[i-1][0])%mod;
26         else if(a[i]<b[i]&&a[i]) 
27             f[i][1]=f[i-1][1];//f[i][0]=0
28         else if(a[i]==b[i]&&a[i])
29             f[i][1]=f[i-1][1],f[i][0]=f[i-1][0]%mod;
30         else if(!a[i]&&!b[i])
31             f[i][0]=f[i-1][0]*invm%mod;
32             f[i][1]=(f[i-1][1]+((f[i-1][0]*((1-invm)%mod+mod)%mod)%mod*inv2)%mod)%mod;//相等的概率是1/m,剩下的对半分
33         
34         else if(!a[i])
35             f[i][0]=f[i-1][0]*invm%mod;
36             f[i][1]=(f[i-1][1]+(f[i-1][0]*(invm*((m-b[i])%mod+mod)%mod)%mod)%mod)%mod;
37         
38         else if(!b[i])
39             f[i][0]=f[i-1][0]*invm%mod;
40             f[i][1]=(f[i-1][1]+(f[i-1][0]*(invm*((a[i]-1)%mod+mod)%mod)%mod)%mod+mod)%mod;
41         
42     
43     printf("%lld
",(f[n][1]%mod+mod)%mod);
44     return 0;
45

 







codeforces935dfafaandancientalphabet

?????????c++   ??????   ??????   ??????   pos   ??????   pow   test   std & 查看详情

codeforces935cfifaandfafa

935C题意：Fifa想用wifi下载足球游戏，但是Fafa是个流浪狂魔，所以Fifa想让他的wifi在公寓里尽量覆盖最大的面积，并且不覆盖到Fafa和公寓外的人，fafa的坐标可以在公寓外。题解：求半径最大的地方就好了，这个半径最大的位置一... 查看详情

codeforces935e建树，dp(代码片段)

E.FafaandAncientMathematics题意：给出一串加减表达式，括号可以互相匹配。其中有p个加号，m个减号，问最后的结果最大可能是多少。min(p,m)<=100tags：题目数据范围给了提示。。先按括号匹配建好树，dp1[i][j],dp2[i][j]表示结点i子树下... 查看详情

codeforces935efafaandancientmathematics(树形dp)

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

codeforcesround#465&935c.fifaandfafa计算几何(代码片段)

传送门题意：在平面中，有一个圆，有一个点，问能在这个圆中围出最大的圆的圆心坐标和半径。要求这个最大圆不包含这个点。思路：比较基础的计算几何，要分三种情况，第一种就是这个点在圆外的情况。第二种是点在圆内... 查看详情

codeforces935dfafaandancientalphabet逆元加dp(代码片段)

这道题题意为给两个数，有n位,数是m进制，为零的位置可以填入1到m的任何数，求第一个数大于第二个数个概率设概率为x/y，这题答案为(x/y)%mod，可以拆成两部分x%mod*(1/y)%mod,x%mod部分可以用dp推出，(1/y)%mod的部分可以用n*y=1（%mod... 查看详情

大数据基础原理

 http://yuedu.baidu.com/ebook/d128cf8e33687e21ae45a935?pn=1&click_type=100100022.3　Hadoop原理2.3.1　HadoopHDFS原理HDFS是一个高度容错性的系统，适合部署在廉价的机器上。HDFS能提供高吞吐量的数据访问，非常适合大规模数据集上的应用。HDFS... 查看详情

搜索数据集的高效算法

...117:24:13【问题描述】：给定几组元素，例如：intset1[5]5601,935,4153,2195,422;intset2[5]5601,935,23,44,422;intset3[5]4205,935,4153,2195,15;intset4[5]4205,589,4015,44,422 查看详情

Php，用插入符号（^）计算指数失败

...表示将给出以下公式的正确结果：((0.0004954*($current^2))-((0.935*$current)+378.486))-((0.0004954*($desired^2))-((0.935*$desire 查看详情

2021全球高被引科学家榜单出炉！中国大陆935人入选，全球第二

...球高被引科学家年度榜单重磅出炉！中国大陆地区共935人入选，仅次于美国，位列全球第二，进步最快。其中中科院入选194人，清华58人，中科大41人，浙大29人，北大28人。近日，知名专业信息... 查看详情

htmlhttps://cdn.rawgit.com/msenturk/e1de24b6d5f0c8d5c49e7f1cfb8fb935/raw/9623c967b40667ca529dd98805(

查看详情

关于安排

以下为最近不可能完成的一些目标CF20套题及题解cf1084(5/5)cf989(4/5)cf994(0/5)cf1091(5/6)cf991(0/5)cf1099(0/5)cf447(0/5)cf614(4/5)cf295(1/5)cf544(4/5)cf514(5/5)cf197(5/5)cf160(5/5)cf379(5/5)DE...(PS:题解会一篇篇补上的...)咕咕咕 查看详情

[cf930e]/[cf944g]coinsexhibition(代码片段)

[CF930E]/[CF944G]CoinsExhibition题目地址：CF930E/CF944G博客地址：[CF930E]/[CF944G]CoinsExhibition-skylee题目大意：一个长度为\(k(k\le10^9)\)的\(01\)串，给出\(n+m(n,m\le10^5)\)个约束条件，其中\(n\)条描述区间\([l_i,r_i]\)至少有一个\(0\)，其中\(m\)条描 查看详情

占位cf

占位CFinclude:CF403CF404 查看详情

dp专题

第一课1cf702A最长连续上升子序列难度9002cf894A 简单dp 难度8003at360 简单一维dp4cf987C 难度14005at1071 一维背包6cf327A 难度1200 第二课（5.18）1cf509a2cf846a3cf550C 难度1500（经典，需要倒序dp）4cf474d5cf4d6cf467c71051d8cf1153D 树上dp 难度1800  查看详情

打cf，学算法——二星级cf520btwobuttons

【CF简单介绍】提交链接：TwoButtons题面：B.TwoButtonstimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputVasyahasfoundastrangedevice.Onthefrontpanelofadevicethereare:aredbutto 查看详情

codeforces刷题记录

...分附上一句话题解，每日更新3题，大部分题目较水。1.+CF1073E：状压，数位dp，官方题解std骚操作2.CF1072A3.CF1072B4.CF1072C5.CF1068C：读题恶心6.CF1073D：猜复杂度，模拟7.CF1088A8.CF1088B9.CF1088C：构造思想10.CF1066A11.CF1066B12.C 查看详情

codeforces|cf1028crectangles(代码片段)

...太简单啦...虽说我锤了一上午都没过...我能说这道题和(CF1029C)算是同一道题吗...）按照时间顺序来说...(CF1029)在(CF1028)前面(而且(CF1029)还是(Div3)),前后没差多长时间就惊现高相似度题目(所以CF是有多迫切想让大家上分)CF1029C传送门... 查看详情