提交数: 8545 通过数: 4621
【题目描述】
在所有的NN位数中，有多少个数中有偶数个数字33?由于结果可能很大，你只需要输出这个答案对1234512345取余的值。
【输入】
读入一个数N(N≤1000)N(N≤1000)。
【输出】
输出有多少个数中有偶数个数字33。
【输入样例】
2
【输出样例】
73
源码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[500],b[500];//n位数中，有偶数个或有奇数个3的数字个数。
int main()
{
a[1]=9,b[1]=1;
int x=9;
long long n;
cin>>n;
for(int i=2;i<=n;i++)
{if(i==n)x=8;//首位不能为0.
a[i]=(x*a[i-1]+b[i-1])%12345;//取模。
b[i]=(x*b[i-1]+a[i-1])%12345;//同上。
}
cout<<a[n];
}