1922. Count Good Numbers

题目信息

题号:

1922

难度:

Medium

主题:

快速幂、组合计数

原题:

LeetCode 1922

重点:

偶数下标放偶数数字,奇数下标放质数数字

题目重述

统计长度为 n 的数字字符串数量,使偶数下标上的数字为偶数,奇数下标上的数字为质数。结果对 10^9 + 7 取模。

自建示例

输入:n = 1
输出:5
解释:唯一位置可选择 0、2、4、6、8。
输入:n = 2
输出:20
解释:首位有 5 种选择,第二位可选 2、3、5、7,共 4 种。