记录编号	232910	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	zeppoe	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-03-03 14:10:05	内存使用	0.32 MiB

#include<cstdio>  
#include<cmath> 
#include<stdlib.h>
#include<iostream>
using namespace std;  
int dp[1024][2];  //0记录奇数个3的个数，1记录偶数个3的个数  
int main(){  
    freopen("chashu.in","r",stdin);  
    freopen("chashu.out","w",stdout); 
    //ios::sync_with_stdio(false);
    int n;  
    dp[1][0]=1;    dp[1][1]=8;  
    dp[2][0]=17;     dp[2][1]=73;  
    for(int i=3;i<=1000;i++){  
        dp[i][1]=(dp[i-1][1]*9+dp[i-1][0])%12345;  
        dp[i][0]=(dp[i-1][1]+dp[i-1][0]*9)%12345;  
    }  
    scanf("%d",&n);  
    printf("%d\n",dp[n][1]);  
             //system("pause");
        return 0;        
        } 
        //这道题，偶数个三是指一个数如1234有一个三，1233有两个三，1有0个三也算偶数个，
        //而刚开始一位数要记得计算零，所以一位有8个，0,1,2,4,5,6,7,8 .
        //找到的规律是每加一个位数，得到的值等于它前一个位数偶数三的个数乘九加上前一位奇数个三个数 
        //可先枚举找到规律