当前位置: 首页 > news >正文

51nod1144 打字的猴子

1144 打字的猴子

有一个特殊的键盘,上面有n个按键。一个猴子用这个键盘打字,每一秒钟打出其中任何1个字母的概率是1/n,让他无限打下去,可以打出任何文学作品。给出按键的数量n和一个字符串,求猴子打出这个串所需时间的平均期望是多少?例如:2个按键的键盘,打出aa的期望是6秒,而打出ab的期望是4秒。

输入

第1行:1个数N,表示按键的数量。(2 <= N <= 26)。
第2行:一个字符串S(S的长度 <= 30000)。

输出

输出时间期望(结果会是超过Int64的大数)。

输入样例

2
aa

输出样例

6

解析:

记d p [ i ] dp[i]dp[i]为打出前i ii个字符的期望时间,要打出前i + 1 i+1i+1个字符需要先打出前i个字符,而下一个字符打对的概率只有1 /n ,而打错字符会使状态从i ii退回到i ii之前的某个状态,用kmp计算所有打错子符后会退到的状态,根据方程计算即可。

放代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#define rep(i,j,k) for(register int i = j; i <= k; i++)
#define dow(i,j,k) for(register int i = j; i >= k; i--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read() {int s = 0; char c = getchar();while( !isdigit(c) ) c = getchar();while( isdigit(c) ) s = s * 10 + c - 48, c = getchar();return s;
}
const int L = 7000, mod = 1e7;
struct big{ll v[L], fv; int len;big(int _v) { memset(v,0,sizeof(v)); v[len = 1] = _v; } big(int _len,int _v) { memset(v,0,sizeof(v)); v[len = _len] = _v; }big() {}big operator * (const big& x) {big c(len+x.len+1,0);rep(i,1,len) rep(j,1,x.len) c.v[i+j-1] += v[i] * x.v[j];rep(i,1,c.len-1) if( c.v[i] >= mod ) fv = c.v[i] / mod, c.v[i+1] += fv, c.v[i] -= fv * mod;while( c.len > 1 && !c.v[c.len] ) c.len--;return c;}big operator + (const big& x) {big c(max(len,x.len)+1,0);rep(i,1,c.len) c.v[i] = x.v[i] + v[i];rep(i,1,c.len-1) if( c.v[i] >= mod ) fv = c.v[i] / mod, c.v[i+1] += fv, c.v[i] -= fv * mod;while( c.len > 1 && !c.v[c.len] ) c.len--;return c;}
} ans(0), bin[16], fc[27], np;
inline void cheng(big &c,const big x,const big y) {memset(c.v,0,sizeof(c.v)), c.len = x.len + y.len + 1;rep(i,1,y.len) rep(j,1,x.len) c.v[i+j-1] += y.v[i] * x.v[j];rep(i,1,c.len-1) if( c.v[i] >= mod ) c.fv = c.v[i] / mod, c.v[i+1] += c.fv, c.v[i] -= c.fv * mod;while( c.len > 1 && !c.v[c.len] ) c.len--;
}
const int maxn = 3e4+5, p = 2333;
ull hs[maxn] = {0}, hp[maxn] = {1}; char c[maxn];
int now, pos;
inline void add(int x) {int y = x; x -= pos; if( x <= 26 ) np = np * fc[x], ans = ans + np;else {now = 0;while( x ) {if( x & 1 ) np = np * bin[now];now++, x >>= 1;}ans = ans + np;} pos = y;
}
inline void put(big x) {printf("%lld", x.v[x.len]);dow(i,x.len-1,1) printf("%07lld", x.v[i]);puts("");
}
int main() {int n = read(), ml;scanf("%s",c+1); ml = strlen(c+1);rep(i,1,ml) hs[i] = hs[i-1] * p + c[i];rep(i,1,ml) hp[i] = hp[i-1] * p;bin[0] = big(n), now = 1, pos = 1;while( now < ml ) cheng(bin[pos],bin[pos-1],bin[pos-1]), now <<= 1, pos++; fc[1] = big(n);rep(i,2,26) fc[i] = fc[i-1] * bin[0];ull vl; np = big(1), pos = 0;rep(i,1,ml-1) {vl = hs[ml] - hs[ml-i] * hp[i];if( vl == hs[i] ) add(i);}add(ml), put(ans);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-35450.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

Spring都没弄明白凭什么拿高薪?真香系列

正文 二叉树 由 n&#xff08; n > 0&#xff09;个有限节点组成一个具有层次关系的集合&#xff0c;看起来就像一个倒挂的树&#xff0c;因此称这样的数据结构为树。 一个节点的子节点个数叫做度&#xff0c;通俗的讲就是树叉的个数。树中最大的度叫做树的度&#xff0c…...

【DCTWVRP】遗传算法求解带容量+距离+时间窗的车辆路径规划问题【Matlab 1211期】

一、VRP简介 1 VRP基本原理 车辆路径规划问题(Vehicle Routing Problem&#xff0c;VRP)是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况&#xff0c;可以简述为&#xff1a;对一系列发货点和收货点&#xff0c;组织调用一定的车辆&#xff0c…...

一天一道ctf 第36天

[NPUCTF2020]ReadlezPHP 点进源码发现/time.php?source&#xff0c;访问一下得到 <?php #error_reporting(0); class HelloPhp {public $a;public $b;public function __construct(){$this->a "Y-m-d h:i:s";$this->b "date";}public functi…...

从空间角度研究类,类与类之间的关系

class A:address 西安def __init__(self,name):self.name namedef func(self):if self.name dsb:self.skins jlfdef func1(self):print(self.__dict__)A.aaa ysh# obj A(dsb) # 类外面可以给对象封装属性 # respons input(sbs) # if respons s: # obj.wepon AWM #…...

小白都能读懂的2PC原理

2PC通信原理分布式事务的原子性什么是2PC2PC提交事务的过程2PC的全局提交规则2PC通信架构集中式2PC通信架构分层2PC通信架构线性2PC通信架构故障恢复站点故障报文丢失总结分布式事务的原子性 一提到到事务&#xff0c;一般就会想到它的ACID特性&#xff0c;其中A&#xff08;a…...

dockerfile的详细介绍

Dockerfile 关键字作用备注FROM指定父镜像指定dockerfile基于那个image构建MAINTAINER作者信息用来标明这个dockerfile谁写的LABEL标签用来标明dockerfile的标签 可以使用Label代替Maintainer 最终都是在docker image基本信息中可以查看RUN执行命令执行一段命令 默认是/bin/sh…...

nacos心跳

轮询 概括来说是服务端定时主动的去与要监控状态的客户端&#xff08;或者叫其他系统&#xff09;通信&#xff0c;询问当前的某种状态&#xff0c;客户端返回状态信息&#xff0c;客户端没有返回或返回错误、失效信息、则认为客户端已经宕机&#xff0c;然后服务端自己内部把这…...

408数据结构I 数据结构的基本概念

数据结构的基本概念 数据 数据是信息的载体&#xff0c;是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合&#xff0c;数据是计算机程序加工的原料。 数据元素 是数据的基本单位&#xff0c;通常作为一个整体进行考虑和处理。 数…...

C语言实现学生成绩管理系统(Easy图形界面)

我的小站——半生瓜のblog 代码文件下载链接——链接 学生成绩管理系统学生成绩管理系统效果图流程&注意要点代码实现学生成绩管理系统 效果图 流程&注意要点 核心部分——EasyX显示图形界面&#xff0c;结构体数组和文件操作负责对数据进行各种操作。只要一进去程序…...

Unity常见合批失败

测试的时候注意两点&#xff1a; 1 运行起来编辑器在看结果 2 多用framedebuger 3 framedebuger观测结果时主要注意Shadows.RenderShadowMap中的Shadows.RenderJobDir和RenderForward.RenderLoopJob。可以看出来合批主要是在这两个函数中实现作用&#xff0c;分别是描画阴影…...

PHP_JavaScript高级编程(2)

二、今日目标 1、理解什么是面向对象&#xff08;编程&#xff09; 2、掌握定义对象的多种方式&#xff0c;并知道各种方式的优缺点 3、掌握什么是原型对象&#xff08;难点&#xff09; 4、理解原型链的概念&#xff08;或原型链的查找方式&#xff09; 5、掌握什么是回调…...

C++类的讲解(一)(超详细)

C类的讲解 1、面向对象和类的介绍 1&#xff09;面向对象 C语言使用面向过程的编程方式&#xff0c;而C则增加了面向对象的编程方式。 面向过程&#xff1a;分析出解决问题所需要的步骤&#xff0c;然后用函数把这些步骤一步一步实现&#xff0c;使用的时候一个一个依次调用就…...

delphi:临界区对象TCriticalSection(Delphi) 与 TRtlCriticalSection 的区别

临界区对象TCriticalSection(Delphi) 与 TRtlCriticalSection 的区别 TRtlCriticalSection 是一个结构体&#xff0c;在windows单元中定义&#xff1b; 是InitializeCriticalSection&#xff0c;EnterCriticalSection&#xff0c;LeaveCriticalSection, DeleteCriticalSection…...

Linux使用命令行工具管理用户和组

文章目录一、管理用户账户1.查看用户账户2.添加用户账户3.管理用户账户密码4.修改用户账户5.删除用户账户二、管理组账户1.创建组账户2.修改组账户3.删除组账户4.管理组成员一、管理用户账户 1.查看用户账户 Linux没有直接查看用户列表的命令&#xff0c;但是可以查看用户配置…...

C语言 指针声明和定义 - C语言零基础入门教程

目录 一.指针简介 1.内存2.内存地址3.指针声明 二.指针类型三.声明并初始化一个指针 1.声明指针并直接初始化 – 推荐2.先声明指针在初始化 – 不推荐 四.查看指针地址和指针的值五.NULL 指针 – 空指针六.重点总结七.猜你喜欢 零基础 C/C 学习路线推荐 : C/C 学习目录 >&g…...

直面秋招!花了6个月肝完阿里技术官的笔记

2. ZooKeeper 介绍 2.1. ZooKeeper 由来 正式介绍 ZooKeeper 之前&#xff0c;我们先来看看 ZooKeeper 的由来&#xff0c;还挺有意思的。 下面这段内容摘自《从 Paxos 到 ZooKeeper 》第四章第一节&#xff0c;推荐大家阅读一下&#xff1a; ZooKeeper 最早起源于雅虎研究院…...

大数据技术hadoop核心Flume

大家好&#xff0c;我是曜耀。 这几天曜耀开始复习一下自己的专业课&#xff0c;相信看过的都了解&#xff0c;就是当前热门的大数据技术与应用。我对于这门专业来说&#xff0c;一个特色就是都会&#xff0c;你说Linux我懂&#xff0c;你说java这是基操&#xff0c;python不好…...

K-means笔记

K-means算法 算法过程&#xff1a; 从N个样本数据中随机选取K个对象作为初始的聚类中心。分别计算每个样本到这各个聚类中心的距离&#xff0c;并将对象归于距离最短的聚类群中。所有样本计算完后&#xff0c;重新计算K个聚类中心。与前一次计算得到得聚类中心比较。如果聚类中…...

为什么淘宝搜索宝贝排名先后不一样,原理是什么?

为什么淘宝搜索宝贝排名先后不一样&#xff0c;原理是什么&#xff1f;  商品在淘宝搜索的排名前后是决定商品的展示多少的&#xff0c;当买家搜索了商品的相关关键词之后&#xff0c;就可以根据综合、价格、信用和价格四个不同的方式来进行排序&#xff0c;不同排序的情况下商…...

2021制造业数字化案例大会暨探营海尔数字化创新”在青岛盛大开幕

5月29日&#xff0c;“2021制造业数字化案例大会暨探营海尔数字化创新”活动在青岛成功举办。本次活动由由数字产业创新研究中心主办&#xff0c;锦囊专家、首席数字官、承办&#xff0c;海尔集团、山东省CIO联盟、青岛CIO联盟协办&#xff0c;邀请海尔集团的多位数字化高管和十…...

阿里云泄露信息、腾讯视频崩了,抖音使用IPFS存储!IPFS将开启一个更安全的互联网存储时代!

西部世界XLMidsummer了解到&#xff0c;近日&#xff0c;网络流传一份浙江省通信管理局7月5日对投诉人的答复函&#xff0c;核实称此前阿里云计算有限公司未经用户同意擅自将用户留存在的注册信息泄露给第三方合作公司。8月23日&#xff0c;浙江省通信管理局相关负责人独家回应…...

项目上线部署发布流程

发布流程 在已开发完毕的各系统正式部署生产环境前要严格按照以下流程进行上线前检查。 一、 提交测试 a) 开发人员在功能开发完毕后首先配置开发环境&#xff0c;并将系统部署至开发环境。在开发环境经过自测通过后提交测试代码&#xff0c;并开始撰写上线方案。(上线方案须包…...

服务器应该租用哪家好?如何选择适合自己的服务器?

当前正处于云计算的时代。现有的服务器租赁模式已发生变化。云服务器正成为很多个人开发者和企业的选择。今天咱们就简单说一下云服务器租赁哪个比较好&#xff01; 国内云平台IDC每个季度都会统计服务商在市场占有率等方面的排名&#xff0c;据IDC最新数据统计&#xff0c;国…...

MySQL分区表原理详解

分区表是将大表的数据分成称为分区的许多小的子集&#xff0c;分区是将一个表的数据按照某种方式&#xff0c;比如按照时间上的月份&#xff0c;分成多个较小的&#xff0c;更容易管理的部分&#xff0c;但是逻辑上仍是一个表。由于在MySQL数据库中&#xff0c;我们对MySQL分区…...

实现批量自动部署Linux操作系统--UP楠哥

#实战描述&#xff1a; UPWEN公司所服务的用户IT环境中有很多的Linux系统&#xff0c;品种也五花八门&#xff0c;有RHEL、Centos、OpenSUSE甚至还有测试环境使用的RockyLinux。当有大量的计算机需要同时安装操作系统需求的时候&#xff0c;如果通过光驱的方式一个个安装&#…...

Java学习总结8

IO流 常用类 File // 获取分割符合系统相关String str File.pathSeparator;System.out.println(""str"");str File.separator;System.out.println(""str"");System.out.println();StringBuilder sb new StringBuilder();sb.appen…...

Jetson Xavier配置开机启动风扇 (7)

Jetson Xavier 自带ubuntu18.04系统&#xff0c;ubuntu18.04默认不带/etc/rc.local文件&#xff0c;我们需要通过配置来让rc.local.service生效。我们修改/etc/rc.local文件来启动风扇。 1.查找服务 ls /lib/systemd/system | grep rc 找到rc.local.service文件 2.修改rc.l…...

小白都能读懂的2PC原理

2PC通信原理分布式事务的原子性什么是2PC2PC提交事务的过程2PC的全局提交规则2PC通信架构集中式2PC通信架构分层2PC通信架构线性2PC通信架构故障恢复站点故障报文丢失总结分布式事务的原子性 一提到到事务&#xff0c;一般就会想到它的ACID特性&#xff0c;其中A&#xff08;a…...

PyQt5环境Pycharm+anaconda配置

文章目录在pycharm中新建项目安装所需包配置Qt designer和pyUIC首先下载好pycharm和anaconda在pycharm中新建项目 新建项目选择anaconda环境 检查所需包&#xff1a;pyqt5&#xff0c;pyqt5-tools&#xff0c;sip等&#xff0c;注意选择anaconda包管理器 可以在anaconda navi…...

Vue子组件调用父组件的方法

转载至:https://blog.csdn.net/zgrkaka/article/details/100528714 PS:需要说明的一点是关于this.$parent的时候使用方式,我之前一直以为只要父组件里定义了比如下面这样的情况: components:{childNode } 然后在子组件里面就可以直接通过this.$parent获取到父组件的属性和方…...

dbc2000 注册机|dbc2000 注册码注册机下载

点击下载来源&#xff1a;dbc2000 注册机 dbc2000 注册机是同名源程序软件的注册机软件&#xff0c;该源程序软件是一款应用于数据库搭建以及数据写入的数据库架设工具&#xff0c;它拥有强大的数据写入功能&#xff0c;在作为应用程序使用时&#xff0c;它不仅可以充当数据属性…...

秋招面经第八弹:网易二面-数据开发工程师

秋招第八弹&#xff1a;网易二面-数据开发工程师 写在最前&#xff1a;秋招以来一直在冲&#xff0c;因为事情比较多&#xff0c;对于笔试面试一直没有复盘&#xff0c;现在靠仅存的记忆把面试的一些问题记录下来&#xff0c;尽可能记录出能回忆到的问题&#xff0c;但可能记的…...

安卓课程格子APP

https://download.csdn.net/download/weixin_57836618/73810452 功能演示&#xff1a; 查看所有课程 点击主页面空白处即可添加课程 添加课程之后查看课程 查看双周课程 查看单周课程 6.查看课程详情...

强化学习——格子世界

强化学习——格子世界 项目源码地址&#xff1a;https://gitee.com/infiniteStars/machine-learning-experiment 1. 实验内容 2. 实验代码 import numpy as np import matplotlib.pyplot as plt from matplotlib.table import Table from xml.dom.minidom import Document #手…...

华为机试 - 跳格子游戏

目录 题目描述 输入描述 输出描述 用例 题目解析 算法源码 题目描述 地上共有N个格子&#xff0c;你需要跳完地上所有的格子&#xff0c;但是格子间是有强依赖关系的&#xff0c;跳完前一个格子后&#xff0c;后续的格子才会被开启&#xff0c;格子间的依赖关系由多组st…...

php 爬课程表信息,Ruby爬取教务系统生成课程表

我为什么要虐自己最近觉得课程格子广告越来越多&#xff0c;乱七八糟的东西越来越多&#xff0c;完全失去了一开始的存在价值&#xff0c;并且没有电脑端app&#xff0c;想查看课程必须拿出手机&#xff0c;而我使用电脑频率要比手机高&#xff0c;所以才有了折腾的动力。于是我…...

android 课程表 ui,UICollectionViewLayout实现课程表布局

因为项目中有课程表的相关模块&#xff0c;第一时间想到用UICollectionView。然而后期的需求越来越复杂&#xff0c;每个格子需要展示的内容越来越多&#xff0c;所以不得不寻找合适的解决方案。最后发现自定义UICollectionViewLayout可以实现我的需求。先放效果图&#xff1a;…...

Android自定义View课程表,Android 自定义View课程表表格

自己闲下来时间写的一个课表控件使用的自定义LinearLayout 里面View都是用代码实现的 最终效果如下图 写的可能有问题希望多多指点创建一个自定义LinearLayout 控件用来装载课程的信息和课程的周数 和节数大概的布局三这样的根据上面的看来觉得总体布局我分了两个 上面的星期是…...

java课程设计设计_java课程设计

1. 团队课程设计博客链接https://www.cnblogs.com/choco1ate/p/12172223.html2.本组课题及本人任务本组课题&#xff1a;泡泡堂(炸弹人)游戏本人任务&#xff1a;Box类(游戏地图中的每个方格)Bomb类(游戏过程中的)游戏玩家输赢信息的文件储存3.需求分析Box类&#xff1a;该类为…...

《课程格子》的一个笔试题目

题目如下&#xff0c;感觉很适合喜欢琢磨的程序员&#xff0c;也是考验你编码风格的时候。 Lets make a tower defense game&#xff08;塔防游戏):1. You have 1 tower, with H health and D dps(damage per second).2. There are n attackers, each with h_i health and d_i …...

Android仿照超级课程表 or 课程格子 一键提取课表功能(方正系统)

参考文章http://blog.csdn.net/sbsujjbcy ,本文仿照‘ 安卓弟 提供的android 项目实战——打造超级课程表一键提取课表功能文章&#xff0c;对他的代码进行了修改和补充&#xff0c;为什么要修改呢&#xff1f;原因是安卓弟的那个源码版本过于老旧&#xff0c;很多方法已经过…...

虚拟声卡可以用于服务器上吗,什么是虚拟声卡?虚拟声卡可以当声卡使用吗?...

大家都知道&#xff0c;电脑上一般都会安装声卡&#xff0c;但是有些设备无需安装&#xff0c;比如说服务器主板&#xff0c;一般就不会去安装声卡。但是万一我们在使用的时候&#xff0c;可能会用到怎么办&#xff0c;所以在这种情况下&#xff0c;我们会采用虚拟声卡。但是很…...

计算机声卡的步骤,详解win7 32位系统电脑重装声卡的步骤

声卡驱动似乎是win7 32位系统中最容易受到损坏的驱动&#xff0c;不过相对来说&#xff0c;也是最容易重新安装的一个驱动之一&#xff0c;当然&#xff0c;很多朋友说不重装声卡对于电脑的操作也没有太大的影响&#xff0c;这一点倒是真的&#xff0c;只要不使用到声音的话&am…...

服务器装虚拟声卡,虚拟声卡,教您怎么安装虚拟声卡

虚拟声卡可以在没有声卡机器的情况下&#xff0c;实现播放&#xff0c;是我们播放视频、音乐的好帮手。想要让视频音乐更方便的播放&#xff0c;就得使用虚拟声卡。仅仅一个软件就可以搞定&#xff0c;现在就让我们来看看它是怎么安装额呢?下面&#xff0c;小编给大伙演示安装…...

linux切换声卡,Ubuntu中双声卡使用实例

我是一个”声音“爱好者&#xff0c;从事教育事业的同时还有一份传媒方面的兼职&#xff0c;更是喜欢自己做一些声音作品。昨天&#xff0c;我很兴奋&#xff0c;因为我的创新声卡和亲爱的话筒终于从 远方寄到了。迫不及待的将声卡插上去&#xff0c;在WINDOWS下装上驱动&#…...

服务器上安装声卡稳定吗,服务器加装声卡的故障

服务器一般不带声卡&#xff0c;不能发声。要想给服务器加装声卡&#xff0c;就要费一番波折。有时候遇到一些故障在所难免&#xff0c;需要从软硬件两个方面考虑问题。加装PCI接口的声卡之后&#xff0c;会有不兼容现象。如果服务器安装32位Windows系统还好说&#xff0c;但有…...

服务器如何安装虚拟声卡,虚拟声卡安装方法和使用【图文教程】

导读&#xff1a;虚拟声卡可以在没有声卡机器的情况下&#xff0c;实现播放&#xff0c;是我们播放视频、音乐的好帮手。想要让视频音乐更方便的播放&#xff0c;就得使用虚拟声卡。仅仅一个软件就可以搞定&#xff0c;现在就让我们来看看它是怎么安装额呢?让我们用虚拟声卡来…...

系统默认声卡驱动没有均衡器的解决方法

一直声音忽大忽小&#xff0c;爆杂音的问题Nahimic音效弄的我很不舒服。但把Nahimic音效驱动卸载后&#xff0c;系统默认驱动又没有均衡器&#xff0c;调不了音&#xff0c;贼坑。 后来终于找到了开源的音效均衡器 Equalizer APO。 全流程 关掉windows 10的驱动自动更新。 要…...

服务器如何安装虚拟声卡,虚拟声卡如何运作起来 分享介绍虚拟声卡安装使用方法...

虚拟声卡怎么用?当我们在电脑中开启了虚拟声卡之后&#xff0c;该如何进行设置才能让虚拟声卡正常使用呢?虚拟声卡是一个软件&#xff0c;通过这个软件我们可以让电脑中发出各种好玩有趣的声音。那么我们该如何让虚拟声卡运作起来呢?本文中给大家分享介绍下虚拟声卡的使用方…...

Macbook Pro 201 装Win10 声卡_【Macbook安装Win10优化第一弹】用Dolby Atmos恢复应有的音质...

之前一直想做 却没做的一个系列本人因为一些特定原因需要在macbook pro 2015上重度使用win10。一直苦于mac在win10下有很多负优化&#xff0c;包括并且不仅限于音质、触控板、功耗等。在使用win10的过程中&#xff0c;积累了一些干掉负优化的小技巧&#xff0c;故分享给大家。今…...