一位一位考虑

• 这道题目我们先看数据范围，(n<=2*10^4)而这里n表示的是位数，2万位，这显然不能用暴力枚举，即使是30年后整100个量子计算机也算不过来。

• 这道题可以用动态规划。 我们看到题目是一位一位看的，所以，我们也该一位一位算。

• 我们先要写出状态转移方程，二写出状态转移方程的关键就是找规律。
• 我们先看一位数。显然，除了3以外其他都有偶数个三（注：0也是偶数，所以，没有三的数也算）。可以得出有8个数有偶数个三，1个有奇数个三。
• 再看2位。
• 以1为十位的两位数。

• 我们再看一个特例：33
• 由于它个位是3，十位也是3，所以它有偶数个三。

总结

从上面可以总结出4种情况

1. 后面有偶数个3，且第一位不是3，那么，这个数仍旧有偶数个三。
2. 后面有奇数个3，且第一位不是3，那么，这个数仍有奇数个三。
3. 后面有偶数个3，第一位是3，那么，这个数就有奇数个三。
4. 后面有奇数个3，第一位是3，那么，这个数就有偶数个三。

• 考虑这4种情况，可得状态转移方程：
• 注：dp[i][0]表示前i位数偶数的个数，dp[i][1]表示前i位数奇数的个数。
  1. dp[i][0]=dp[i-1][0]*9+dp[i-1][1] *1。（1、4两种情况，后面有偶数个三的个数 *第一位不是3的数+后面有奇数个三的个数 *第一位是三的个数）。
  2. dp[i][1]=dp[i-1][0]*1+dp[i-1][1]*9。（2、3两种情况，后面有偶数个三的个数 *第一位是三的个数+后面有奇数的个数 *第一位不是三的个数）。

代码（求赞）

#include <bits/stdc++.h>
using namespace std;
const int mod=12345;
int n;
long long dp[20005][2];
int main()
{
    cin>>n;
    dp[1][0]=8,dp[1][1]=1;
    for (int i=2;i<=n;i++)
    {
        dp[i][0]=(dp[i-1][0]*9+dp[i-1][1])%mod;
        //状态转移方程1。并取模。
        dp[i][1]=(dp[i-1][0]+dp[i-1][1]*9)%mod;
        //状态转移方程2。并取模。
    }
    cout<<dp[n][0];//输出第n位、是偶数的数。
    return 0;
}