位数问题

题目描述： 在所有的 n 位数中，有多少个数中有偶数个 数字3，由于结果可能很大，你只需要输出这个答案对 12345取余的值。

输入格式 ： 一个整数 n

输出格式 ： 输出有多少个数中有偶数个数字3。

数据范围 ：1<=n<=1000

考虑这类题，一般来说都是从第 i - 1位推导到 第 i 位，且当前位是去偶数还是去奇数的。

可以用 f[i] [0] 表示前 i 位去偶数 个 3 有几种情况 ， f [i][1] 表示 前 i 位去奇数个 3 有几种情况 ，那么状态 转移方程可以表示为

f[i][0] = f[i-1][0] *9 + f[i-1][1] ; f[i][1] = f[i-1][0] + f[i-1][1] *9 ;

边界条件 ： f[1][1] = 1, f[1] [0] = 9;

#include<bits/stdc++.h>

using namespace std;

int main(){
	int f[1001][2];
	int n;
	cin>>n;
	f[1][1]=1;
	f[1][0]=9;
	for(int i=2;i<=n;i++){
		x = f[1][0];
		if(i == n) x--;
		f[i][0] = (f[i-1][0]*x + f[i-1][1]) % 12345;
		f[i][1] = (f[i-1][1]*x + f[i-1][0]) % 12345; 
	}
	cout<<f[n][0]<<endl; 
	return 0;
}