蓝桥杯 k好数

刺骨的言语ヽ痛彻心扉 2022-08-27 10:00 185阅读 0赞

问题描述

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式

输入包含两个正整数，K和L。

输出格式

输出一个整数，表示答案对1000000007取模后的值。

样例输入

4 2

样例输出

7

数据规模与约定

对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

思路：

一位的时候0~9都行，两位的时候就是一位的所有情况的和减去相邻的数，三位之后类似，相邻的数的意思是前面情况开头的数和我当前枚举的数的关系。

opt\[i\]\[j\]表示，i位，开头为j，的情况数。

代码：

1.#include <iostream>
    2.#include <cstring>
    3.using namespace std;
    4.
    5.int M=1000000007;
    6.
    7.int x,y,k,l,i,j;
    8.long long opt[101][101],s,sum;
    9.
    10.int main()
    11.{
    12.    memset(opt,0,sizeof(opt));
    13.    cin >> k >> l;
    14.    for (i=0;i<=k-1;i++)
    15.        opt[1][i]=1;
    16.    sum=k;
    17.    for (i=2;i<=l;i++)
    18.    {
    19.        s=0;
    20.        for (j=0;j<=k-1;j++)
    21.        {
    22.            if (j==0)
    23.                x=0;
    24.            else x=opt[i-1][j-1];
    25.            if (j==k-1)
    26.                y=0;
    27.            else y=opt[i-1][j+1];
    28.            opt[i][j]=(sum-x-y+M)%M;
    29.            s=(s+opt[i][j]+M)%M;
    30.        }
    31.        sum=s;
    32.    }
    33.    long long  ans=(sum-opt[l][0]+M)%M;
    34.    cout << ans << endl;
    35.    return 0;
    36.}

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯幸运数

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,… 1 就是第一个幸运数。我们从2这个数开始。把所

超、凢脫俗/ 2024年03月30日 16:48/ 0 赞/ 107 阅读

相关【蓝桥杯】K倍区间

\[蓝桥杯 2017 省 B\] k 倍区间题目描述给定一个长度为 N N N 的数列， A 1 , A 2 , ⋯ A N A\_1,A\_2, \\cdo

本是古典何须时尚/ 2024年03月24日 10:07/ 0 赞/ 52 阅读

相关对蓝桥杯算法练习 003 K好数的理解

ALG\_003\_K好数问题：如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例

阳光穿透心脏的1/2处/ 2022年12月12日 01:53/ 0 赞/ 122 阅读

相关蓝桥杯 k好数

问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候

刺骨的言语ヽ痛彻心扉/ 2022年08月27日 10:00/ 0 赞/ 186 阅读

相关蓝桥杯之幸运数

PREV-10 幸运数问题描述：幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,…. 1

小咪咪/ 2022年06月18日 09:53/ 0 赞/ 258 阅读

相关蓝桥杯K好数（动态规划）

1、背景：动态规划是在20世纪50年代由美国数学家贝尔曼为研究最优控制问题而提出的，英文叫dynamic programming。在计算机

古城微笑少年丶/ 2022年06月01日 10:47/ 0 赞/ 162 阅读

相关蓝桥杯算法训练（三） K好数（动态规划） C语言

K好数 C语言问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L

蔚落/ 2022年03月20日 17:56/ 0 赞/ 324 阅读

相关蓝桥杯方格填数

如图，如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的

素颜马尾好姑娘i/ 2022年03月08日 13:08/ 0 赞/ 300 阅读

相关蓝桥杯煤球数

煤球数目有一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个（排列成三角形

Dear 丶/ 2022年03月08日 04:34/ 0 赞/ 212 阅读

相关蓝桥杯 k倍区间

题目描述给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称

迷南。/ 2022年03月08日 03:40/ 0 赞/ 225 阅读