A26462. 位数问题
题目描述
位数问题
题目描述
在所有的N位数中，有多少个数中有偶数个数字3? 由于结果可能很大，你只需要输出这个答案对12345取余的值。
输入
读入一个数N(N≤1000)。
输出
输出有多少个数中有偶数个数字3。
输入样例
2输出样例
73参考答案
#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define M 12345
int main()
{
int a[N], b[N], n, x = 9;
a[1] = 9, b[1] = 1;//如果只有1位数字，有偶数个3的数字个数确实为9，因为包括了0。如果不是1位数字，最高位不能为0。
cin >> n;
for(int i = 2; i <= n; ++i)
{
if(i == n)//最后一次添加数字，添加的是最高位数字，不能添加0，所以不添加3的情况只有8种
x--;
a[i] = (a[i-1]*x + b[i-1])%M;
b[i] = (a[i-1] + b[i-1]*x)%M;
}
cout << a[n];
return 0;
}答案解析
递推思路
当 N=1，数字范围为 0 ~ 9，合计 9-0+1=10 个。
（1）含有偶数个 3 数字有 9 个（0、1、2、4、5、6、7、8、9）。
（2）含有奇数个 3 数字有 1 个（3）。
当 N=2，数字范围为 10 ~ 99，合计 99-10+1=90 个。
（1）含有偶数个 3 数字的构成：前面一位数中含有奇数个 3 数字，在其前面加上数字 3 的组合，有 1*1=1个，即数字 33，这样有 1 个数字；前面一位含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，有 8*9=72 个。合计 72+1=73。
（2）含有奇数个 3 数字的构成：前面一位数中含有奇数个 3 ，在其前面加上数字为（1、2、4、5、6、7、8、9）的组合，有 8*1=8 个。前面一位数中含有含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上数字为 3 的组合，有 9*1=9 个。合计 8+9=17 个。
当 N=3，数字范围为 100 ~ 999，合计 999-100+1=900 个。
（1）含有偶数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上数字 3 的组合，合计 18*1=18 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字） ，数字前加上不是 3 的数字（1、2、4、5、6、7、8、9），有 82*8=656。合计有 18+656=674 个。
（2）含有奇数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，合计 18*8=144 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字） ，数字前加上数字 3，有 82*1=82。合计有 144+82=226 个。
以此类推。这样我们就可以推倒出如下的递推公式：
N 表示位数，a[i] 表示到第 i 位包含偶数个 3 的数字数量，b[i] 表示到第 i 位包含奇数个 3 的数字数量
a[1] = 9 b[1] = 1
当 i<N 的时候
a[i] = a[i-1]*9 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*9
当 i==N 的时候，由于首位不能为零
a[i] = a[i-1]*8 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*8