首页 > 其他分享 >牛客练习110-D

牛客练习110-D

时间:2023-04-15 11:13:34浏览次数:56  
标签:int res 练习 long 牛客 110 mod dp qmod

题目链接:https://ac.nowcoder.com/acm/contest/54129/D

比赛的时候dp状态方程想错了,一直在做无用攻。

思路:设\(dp[i]\)为用了i次魔法的期望值,递推地做即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
map<char,int>M;
long long qmod(long long x,long long y){
    long long res = 1;
    while(y){
        if (y&1) res = res*x%mod;
        y = y>>1;
        x = x*x%mod;
    }
    return res;
}
long long dp[2000];
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    M['y'] = 1;
    M['w'] = 1;
    M['i'] = 1;
    M['a'] = 1;
    M['k'] = 1;
    long long v1 = 5*qmod(26,mod-2)%mod;
    long long v2 = 21*qmod(26,mod-2)%mod;
    long long t = qmod(n,mod-2);
    for (int i=0;i<n;i++){
        if (M.count(s[i])) dp[0]++;
    }
    for (int i=1;i<=k;i++){
        dp[i] = dp[i-1];
        dp[i] = (dp[i]-dp[i-1]*t%mod*v2%mod+mod)%mod;
        dp[i] = (dp[i]+(n-dp[i-1]+mod)*t%mod*v1%mod)%mod;
    }
    cout<<dp[k]<<'\n';
}

标签:int,res,练习,long,牛客,110,mod,dp,qmod
From: https://www.cnblogs.com/xjwrr/p/17320698.html

相关文章

  • shell练习3
    1.你需要打印一个给定的数字的反序,如输入10572,输出27501,如果没有输入数据,应该抛出错误和使用脚本说明。   2.写出SHELL函数RevertInput,函数必须获取三个参数,然后将三个参数倒序echo打印出来,函数必须检查参数个数的合法性,如果参数非法,打印”Illegalparameters”,对于下面的......
  • Educational Codeforces Round 110 (Rated for Div. 2) C. Unstable String(状态机)
    https://codeforces.com/contest/1535/problem/C题目大意:给定一个字符串s,由10?组成:?每次都可以任意替换成0或者1问我们这个子字符串中,能够组成010101这样两两互不相等的字符串的数量最大是多少?input30?10????10??1100output8625#include<bits/stdc++.h>usin......
  • 练习——简单的MapExercise
    packagecom.collection_.map_;importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjava.util.Set;/*使用HashMap添加3个员工对象,要求键:员工id值:员工对象并遍历显示工资>18000的员工(遍历方式最少两种)员工类:姓名、工资、员工id*......
  • c++练习打卡(7)
    银行存钱银行一年整存零取的利息每月0.0063,某人存了一笔钱,每年年底取1000,五年取完,问他存了多少?流程图:伪代码:源代码:#include<stdio.h>intmain(){ doublemoney=0.0; for(inti=0;i<5;i++){ money=(money+1000.0)/(1+12*0.0063); }printf("%0.2lf",money); return0;} ......
  • N04.练习
    点击查看代码#include<stdio.h>intmain(void){ intlength,width,height; floatvolume,weight; printf("Length:%d\n",length); printf("Width:%d\n",width); printf("Height:%d\n",height); printf("Volume:%f\n......
  • 第二天练习
    2-26一、问题描述:编写一个完整的程序,运行时向用户提问“你考试考了多少分?(0~100)”,接收输入后判断其等级显示出来。规则如下:优90≤分数≤100良80≤分数<90中60≤分数<80差0≤分数<60二、设计思路:1.先输出提示语句,输入分数2.利用while循环,若输入分数不在范围内,重新提示输入......
  • 集合的练习
    案例一:自动选择器:    案例一代码实现:importjava.util.*;publicclasstext{publicstaticvoidmain(String[]args){//第一种实现方式List<String>list=newArrayList<>();Collections.addAll(list,"张三","李四","王五&......
  • uva 11082 A Plug for UNIX
     #include<iostream>#include<vector>#include<map>#include<queue>#include<cstring>usingnamespacestd;constintN=1e4+2,M=5e5;intn1,n2,n3,len;map<string,int>mp;map<int,int>A,B;constintin......
  • 笨办法学 Python · 续 练习 3:质量
    练习3:质量原文:Exercise3:OnQuality译者:飞龙协议:CCBY-NC-SA4.0自豪地采用谷歌翻译我将提出一个关于认知的科学理论,我并不能证明它:你所做事情的记忆,会让你思考最终产品,这是正确的行为。这基于我所做的,几乎每一个创造性的事情的观察,它是这样:你创造的东西需要很长一段时间。这可......
  • 笨办法学 Python · 续 练习 9:`sed`
    练习9:sed原文:Exercise9:sed译者:飞龙协议:CCBY-NC-SA4.0自豪地采用谷歌翻译使用这些小型项目来研究你自己是有用的,但让我们来看看你主要关注的主题:开始工作的启动流程,例如你的文本编辑器,你可以打字打的多好,以及计算机内部发生的其他事情。心理状态,当你开始工作时,建议将日志作为......