hihoCoder #1558 : H国的身份证号码I

题目链接：https://hihocoder.com/problemset/problem/1558

H国的身份证号码I

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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 ≤ 10，1 ≤ K ≤ 81。

输出

合法号码的总数。由于答案可能非常大，你只需要输出答案对10+7取模的结果。

样例输入

2 4

样例输出

12

解题思路：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;

}