S国幸运数字计数：动态规划求解

S国是一个爱好数字的国度，总有些人会夜以继日的数着数字以占卜凶吉，凡是数字在十进制表示之下有连续k个4或k个7相连则被认为是幸运的。他们看遍了1到n之间的所有数，想考一考你。因为他们预先知道答案，所以他们只需你告诉他们幸运的数字mod 109+7就行。

输入描述

第一行一个数k。第二行一个数n。

输出描述

一个数，如题所述。

样例输入

1 100

样例输出

数据规模和约定

设t为n的位数 20%的数据n<=10^6 40%的数据n<=10^18 60%的数据t<=5000 100%的数据1<=k<=t<=10^6

思路：

根据题目描述，我们需要找到1到n之间有多少个数字是幸运数字。幸运数字的定义是数字在十进制表示下有连续k个4或k个7相连。

我们可以使用动态规划的思想来解决这个问题。

首先，我们定义一个二维数组dp，dp[i][j]表示数字长度为i，以数字j结尾的幸运数字的个数。其中，i的取值范围是1到n的位数，j的取值范围是0到9。

边界条件是dp[1][j]，当j等于4或7时，dp[1][j]为1，其它情况下dp[1][j]为0。

然后，我们可以通过动态规划的递推关系来计算dp[i][j]。对于dp[i][j]，如果j等于4或7，那么dp[i][j]等于dp[i-1][j] + dp[i-1][(j+1)%10]，即以数字j结尾的幸运数字的个数等于以数字j-1结尾的幸运数字的个数加上以数字j结尾的幸运数字的个数。如果j不等于4或7，那么dp[i][j]等于dp[i-1][j]。

最后，我们可以遍历dp[n]数组，将所有数字的个数相加，并取模109+7，得到最终的答案。

**代码实现如下：**cpp#include #include

using namespace std;

const int MOD = 1e9 + 7;

int countLuckyNumbers(int k, int n) { int t = to_string(n).length(); // n的位数 vector<vector> dp(t + 1, vector(10, 0)); // dp数组 dp[1][4] = dp[1][7] = 1; // 边界条件

for (int i = 2; i <= t; i++) {        for (int j = 0; j < 10; j++) {            if (j == 4 || j == 7) {                dp[i][j] = (dp[i - 1][j] + dp[i - 1][(j + 1) % 10]) % MOD;            } else {                dp[i][j] = dp[i - 1][j];            }        }    }

int ans = 0;    for (int j = 0; j < 10; j++) {        ans = (ans + dp[t][j]) % MOD;    }

return ans;}

int main() { int k, n; cin >> k >> n;

int ans = countLuckyNumbers(k, n);    cout << ans << endl;

return 0;}

复杂度分析：

时间复杂度：O(t)，其中t为n的位数。空间复杂度：O(t)，需要使用一个二维数组dp来保存中间结果