CCF201312-4 有趣的数(100分)_csp 201312-4-程序员宅基地

技术标签: 201312-4  CCF-CSP认证题解  ccf  有趣的数  


试题编号: 201312-4
试题名称: 有趣的数
时间限制: 1.0s
内存限制: 256.0MB
问题描述:
问题描述
  我们把一个数称为有趣的,当且仅当:
  1. 它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。
  2. 所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。
  3. 最高位数字不为0。
  因此,符合我们定义的最小 有趣的数 是2013。除此以外,4位的有趣的数有两个:2031和2301。
  请计算恰好有n 位的有趣的数个数。由于答案可能非常大,只需要输出答案除以1000000007的余数。
输入格式
  输入只有一行,包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式
  输出只有一行,包括恰好n 位的整 数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3


问题链接: CCF201312试题

原题链接有趣的数

问题描述参见上文。

问题分析:这是一个计算问题,关键在于找到一个递推式。只要找到一个递推式,问题就解决了。有时候这类问题也用DP(动态规划)来解决。

根据题意,有趣的数满足以下约束条件如下:

1.只包含数字0、1、2和3

2.0、1、2和3各自至少出现一次

3.所有的0都出现在1之前

4.所有的2都出现在3之前

5.最高位数字不为0

数(字符串)可以分为以下六种情况(或称为状态):

1.只包含数字2,记为S1

2.只包含数字2和0(0开始的数0个,以此数为前缀的数均不是以0开始),记为S2

3.只包含数字2和3,记为S3

4.只包含数字2、0和1,并且满足所有0在1之前,记为S4

5.只包含数字2、0和3并且满足所有2在3之前,记为S5

6.包含任意数字(包含0、1、2和3满足所有0在1之前满足所有2在3之前,记为S6

考虑递推式:

1.对于S1,考虑其长度l,定义f(l,S1)为长度l的S1数的数量,则f(l,S1)=1。也就是说长度为l的只包含2的数只有1个。

2.对于S2考虑其长度l,定义f(l,S2)为长度l的S2数的数量,当l=1则那么f(l,S2)=0,即f(1,S2)=0,当l>1则f(l,S2)=f(l-1,S2)*2+f(l-1,S1)。这是因为,长度为l的S2数可以是由长度为l-1的S2的数加上2或0构成,例20为长度为2的S2数,那么202和200为长度为3的S2;另外,长度为l的S2数可以是由长度为l-1的S1的数加上0构成,例如22为长度为2S1数,那么220为长度为3的S2数。

3.对于S3考虑其长度l,定义f(l,S3)为长度l的S3数的数量,当l=1则那么f(l,S3)=0,即那么f(1,S3)=0,当l>1f(l,S3)=f(l-1,S3)*2+f(l-1,S1)。这是因为,长度为l的S3数可以是由长度为l-1的S3的数加上2或3构成,例23为长度为2的S3数,那么232和233为长度为3的S3;另外,长度为l的S3数可以是由长度为l-1的S1的数加上3构成,例如22为长度为2S1数,那么223为长度为3的S3数。

4.对于S4考虑其长度l,定义f(l,S4)为长度l的S4数的数量,当l=1则那么f(l,S4)=0,即f(1,S4)=0,当l>1则f(l,S4)=f(l-1,S4)*2+f(l-1,S2)+f(l-1,S3)。这是因为,长度为l的S4数可以是由长度为l-1的S4的数加上2或1构成(满足所有0在1之前,不可以加上0),例201为长度为3的S4数,那么2012和2011为长度为4的S4;另外,长度为l的S4数可以是由长度为l-1的S2的数加上1构成,例如20为长度为2S2数,那么201为长度为3的S4

同理,对于S5S6,可以得到相应的递推公式。详细参见以下的源程序。

有了递推式,程序就可以根据递推式,逐步进行计算。

程序说明:(略)。

提交后得100分的C++语言程序如下:

/* CCF201312-4 有趣的数 */

#include <iostream>
#include <cstring>

using namespace std;

const long long MOD = 1000000007;
const int MAXN = 1000;
const int MAXS = 5;
long long status[MAXN+1][MAXS+1];


int main()
{
    int n;

    cin >> n;

    memset(status, 0, sizeof(status));

    // DP
    status[1][0] = 1;
    for(int i=2; i<=n; i++) {
        status[i][0] = 1;
        status[i][1] = (status[i - 1][1] * 2 + status[i - 1] [0]) % MOD;
        status[i][2] = (status[i - 1][2] + status[i - 1][0]) % MOD;
        status[i][3] = (status[i - 1][3] * 2 + status[i - 1][1] ) % MOD;
        status[i][4] = (status[i - 1][4] * 2 + status[i - 1][1] + status[i - 1][2]) % MOD;
        status[i][5] = (status[i - 1][5] * 2 + status[i - 1][3] + status[i - 1][4]) % MOD;
    }

    cout << status[n][5] << endl;

    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/tigerisland45/article/details/55270910

智能推荐

Paxos_paxos是同步还是异步-程序员宅基地

文章浏览阅读179次。https://www.zhihu.com/topic/19773822/hothttps://zhuanlan.zhihu.com/paxos1、Paxos组成和简介Paxos算法解决的问题正是分布式一致性问题,即一个分布式系统中的各个进程如何就某个值(决议)达成一致。Paxos算法运行在允许宕机故障的异步系统中,不要求可靠的消息传递,可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力,即2F+1个节点的系统最多允许F个节点同时出现故障。..._paxos是同步还是异步

什么是人工智能AI_人工智能ai是什么意思-程序员宅基地

文章浏览阅读9.7k次,点赞2次,收藏11次。  什么是人工智能(AI)?  人工智能(AI)指的是在被编程为像人类一样思考并模仿其行为的机器中对人类智能的模拟。该术语还可以应用于任何表现出与人类思维相关的特征(例如学习和解决问题)的机器。  人工智能的理想特征是其合理化并采取最有可能实现特定目标的行动的能力。    了解人工智能  当大多数人听到人工智能一词时,他们通常想到的第一件事就是机器人。那是因为大型的电影和小说都编造了关于类似人类的机器的故事,这些机器在地球上造成了严重破坏。但是事实离真相还很远。  人工智能._人工智能ai是什么意思

Linux CentOS设置静态获取ip,解决无法上网问题_centos无法获取静态ip-程序员宅基地

文章浏览阅读375次。CentOS6的静态ip配置,解决动态获取ip能连接外网但静态获取ip无法连接外网的问题。_centos无法获取静态ip

鸿蒙运行linux,【鸿蒙资源】已经配置好鸿蒙开发环境的Ubuntu 20.04镜像-程序员宅基地

文章浏览阅读2.3k次。1 、前言:目前鸿蒙系统的开发环境主要分为 windows 和 Linux两个平台。目前编译 鸿蒙系统的代码还是需要在 Linux环境下。关于Linux的环境搭建官方有提供文档说明:https://device.harmonyos.com/cn/docs/start/introduce/oem_quickstart_3861_build-0000001054781998这里推荐大家使用 ubunt..._鸿蒙开发 ide 有linux系统版本么

Keras简介-程序员宅基地

文章浏览阅读7k次。Keras 是一个Python深度学习框架,可以方便地定义和训练几乎所有类型地深度学习模型。Keras最开始是为研究人员开发的,其目的在于快速实验keras具有以下重要特性:1.相同的代码可以在CPU或GPU上无缝切换运行2.具有用户友好的API,便于快速开发深度学习模型的原型3.内置支持卷积网络(用于计算机视觉)、循环网络(用于序列处理)以及二者的任意组合。4.支持任意网络架构:多输入或多输出模型、层共享、模型共享等。1.1Keras\TensorFlow\Theano\CNTK_keras

uniapp 升级后报错 nvue中不支持如下css。如全局或公共样式受影响,建议将告警样式写在ifnd APP-PLUS-NVUE的条件编译中_nvue中不支持如下css。如全局或公共样式受影响,建议将告警样式写在ifndef app-plu-程序员宅基地

文章浏览阅读2w次,点赞8次,收藏11次。问题uniapp在前一个版本里面,在app中引入公共css没有任何问题,后来升级后,突然报错,百度半天有人问,但是好像也没有人回答o(╥﹏╥)o。<style> /* uni.css - 通用组件、模板样式库,可以当作一套ui库应用 */ @import './common/uni.css'; @import './common/iconfont.css'; /*每个页面公......_nvue中不支持如下css。如全局或公共样式受影响,建议将告警样式写在ifndef app-plu

随便推点

python opencv cv2.resize()函数-程序员宅基地

文章浏览阅读2.9k次。**def resize(src, dsize, dst=None, fx=None, fy=None, interpolation=None): # real signature unknown; restored from __doc__ """ resize(src, dsize[, dst[, fx[, fy[, interpolation]]]]) -> dst ..._python opencv cv2.resize(

Java与数据结构的实现:线性表(链式:带头结点的单链表)_java构建完整的带头结点单链表使其拥有插入,删除和遍历三大功能。 并通过main方法-程序员宅基地

文章浏览阅读380次。分析:先要满足以下基本的要求,遇到问题再做完善。单链表的属性 结点类: 数据项 data 结点类型的变量 next &nbs_java构建完整的带头结点单链表使其拥有插入,删除和遍历三大功能。 并通过main方法

matplotlib中使用imshow绘制二维图-程序员宅基地

文章浏览阅读163次。这里所指的二维图,是二维矩阵数据的平面色彩显示[python] view plain copy print?#-*-coding:utf-8-*-frommatplotlibimportmplimportmatplotlib.pyplotaspltimportnumpyasnp#----..._cmap=mpl.cm.hot

Q107:Linux系统下GDB对PBRT-V3进行debug_pbrt ao-程序员宅基地

文章浏览阅读1.4k次。——————-Notes for the first debug of pbrt——————-1.在pbrt-v3下新建一个名为build.debug的文件夹,定位打该文件夹; cd ~/pbrt-v3/build.debug/2.用cmake生成debug版本的makefile; cmake ../ -DCMAKE_BUILD_TYPE=Debug3.编译生成debug般的可执行文件p_pbrt ao

Mybatis中配置文件xml的头部声明_mybatis.xml头部-程序员宅基地

文章浏览阅读925次。Mybatis中配置文件xml的头部<?xml version="1.0" encoding="UTF-8" ?><!DOCTYPE configuration PUBLIC "-//mybatis.org//DTD Config 3.0//EN" "http://mybatis.org/dtd/mybatis-3-config.dtd"><configuration></configuration>Mybatis中映射配置文件 即每个d_mybatis.xml头部

用 Hadoop 进行分布式并行编程_hadoop并行实现-程序员宅基地

文章浏览阅读1.7k次。用 Hadoop 进行分布式并行编程Hadoop 简介摘要:Hadoop 是一个实现了 MapReduce 计算模型的开源分布式并行编程框架,借助于 Hadoop, 程序员可以轻松地编写分布式并行程序,将其运行于计算机集群上,完成海量数据的计算。本文将介绍 MapReduce 计算模型,分布式并行计算等基本概念,以及 Hadoop 的安装部署和基本运行方法。  Hado_hadoop并行实现