hihoCoder #1558 : H国的身份证号码I
2024-08-28 17:15:38
题目链接:https://hihocoder.com/problemset/problem/1558
H国的身份证号码I
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
- 样例输入
-
2 4
- 样例输出
-
12
描述
H国的身份证号码是一个N位的正整数(首位不能是0)。此外,由于防伪需要,一个N位正整数是合法的身份证号码当且仅当每位数字都小于等于K,并且任意相邻两位数字的乘积也小于等于K。
例如对于K=5, 101、211、210等都是合法的号码,而106、123、421等都是非法的号码。
给定一个正整数N以及K,H国总统想知道一共有多少个合法的号码可用。
输入
两个整数N和K。
对于30%的数据,1 ≤ N ≤ 10
对于50%的数据,1 ≤ N ≤ 1000000
对于100%的数据,1 ≤ N ≤ 1012,1 ≤ K ≤ 81。
输出
合法号码的总数。由于答案可能非常大,你只需要输出答案对109+7取模的结果。
解题思路:dfs深搜从小到大遍历一次,满足要求直接输出,结果必定是字典序的排序
\(x_i\)
AC代码:
# include <bits/stdc++.h>
using namespace std;
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
///coding...................................
int n,k,ans=1;
void dfs(int a,int b) { ///b代表当前最后一个数的值
FOR(i,0,k) {
if(a>=ans) { ///如果为n位数直接输出
cout<<a<<endl;
return;
}
if(b*i<=k)
dfs(a*10+i,i);
}
}
int main() {
#ifdef FLAG
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif
cin>>n>>k;
FOR(i,2,n)ans*=10; ///求出最小的n位数作为判断的下限
FOR(i,1,k)dfs(i,i); ///首位数不能为0
return 0;
}
最新文章
- Java入门教程总目录
- javascript加载顺序
- Ubuntu安装Fcitx(小企鹅五笔输入法)
- 使用Web代理实现Ajax跨域
- 14.7.4 InnoDB File-Per-Table Tablespaces
- Oracle exp/imp数据导入导出工具基本用法
- 团队作业8——第二次项目冲刺(Beta阶段)--5.21 second day
- 我的第一个python web开发框架(16)——产品分类管理
- Go 语言基础语法
- 我的博客即将入驻&ldquo;云栖社区&rdquo;,诚邀技术同仁一同入驻。
- Spring在项目中需要的配置
- jq简单仿上传文件
- 【Thymeleaf】常用属性
- 网页图表Highcharts实践教程之图表区
- 7.20 python线程3
- 日期 date +%F-%T-%N
- steam
- 无法安装Java,以下开关中存在错误:“0”
- docker weave安装
- my sql存储过程 基本使用
热门文章
- [Python3] 027 常用模块 time
- (5.1.5)引擎管理——多服务器管理之中央管理服务器(CMS)
- jsp运行环境的安装和配置
- 【6.12校内test】T3 城市交通费
- D - 秋实大哥与快餐店
- vue-cli中开发生产css注入形式不同导致bug
- Redis集群部署一直卡在Waiting for the cluster to join ......(Redis集群总线配置)
- asp.net webApi webconfig配置常见问题
- scp 从另一台linux服务器拷贝文件或文件目录
- 遍历获取html页面所有元素的id