<<信息学奥赛一本通>> 位数问题题解

1313：【例3.5】位数问题

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3907 通过数: 2025

【题目描述】

在所有的 $N$

【输入】

读入一个数 $N (N \leq 1000)$

【输出】

输出有多少个数中有偶数个数字 $3$

【输入样例】

【输出样例】

73

题解：

仔细观察，嗯....
!!!! 我知道了，当位数是 1 的时候 , 有 9 个符合条件的。只有1个 数字3 不符合。
(因为根据题意，含有0个3也是含有偶数个3)

　　那么接下来，数字3 是含有奇数个3(不符条件 false) 的但是数字33 是含有偶数个3 (符合条件 true)

　　又就是说数字3 在增加了一位数后变成了符合条件的数字33。

　　符合条件的数的个数为 T[0]

　　不符合条件的数的个数为 F[0]

　　T[0] 与 F[1] 是有关联的，我们就需要2个数组。

　　再由于要记录是第N位数。

　　所以引入二维数组，F[i][0] 表示第 i 位数的时候，符合条件的数的个数。

　　再仔细观察，发现 1（true）分别和 0,1,2,4,5,6,7,8,9 结合可以变成 10,11,12,14,15,16,17,18,19 ( true ) (9个)

　　　　　　　　　　　　　　　　　　　　　和 3 结合变成 13 ( false ) (1个)

　　同理:

　　　　3 (false) 与 3 -> 33 (true) (1个)

　　　　　　　与除3外的其他数结合 -> （false） (9个)

　　就可以列出递推式:

　　　　T[i] = (T[i-1]*9 + F[i-1])%12345;
　　　　F[i] = (T[i-1] + F[i-1]*K=9)%12345;

　等等...然后...
　因为012不构成三位数，也就是说 第 N 位（最后一位的时候），不能把0算进去。
　所以要把 *9 变成 *8

#include <iostream>
using namespace std;
long long T[1001],F[1001];
int N;
int main(){
    int K = 9; 
    cin >> N;
    T[1] = 9;
    F[1] = 1;
    for(int i=2;i<=N;i++){
        if(i==N)
            --K;
        T[i] = (T[i-1]*K + F[i-1])%12345;
        F[i] = (T[i-1] + F[i-1]*K)%12345;
    }
    cout << T[N] << endl;
    return 0;
}