链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1313
在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。
读入一个数N。
输出有多少个数中有偶数个数字3。
2
73
题解：i位数偶数个3：i-1位数偶数3前面加0,1,2，4……九个数，奇数个3前面加3，同理得奇数情况，到最后一次去掉0的情况
#include<iostream> #include<cstdio> #include<cstring> using namespace std; long long f[5001][2]; int main() { int n; cin>>n; f[1][0]=9; f[1][1]=1; int k=9; for(int i=2;i<=n;i++) { if(i==n)k--; f[i][0]=(f[i-1][0]*k+f[i-1][1])%12345; f[i][1]=(f[i-1][1]*k+f[i-1][0])%12345; } cout<<f[n][0]<<endl; }
原文：http://www.cnblogs.com/EdSheeran/p/7672571.html