1313：【例3.5】位数问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在所有的N位数中，有多少个数中有偶数个数字3。由于结果可能很大，你只需要输出这个答案对12345取余的值。
【输入】
读入一个数N(N≤1000)。
【输出】
输出有多少个数中有偶数个数字3。
【输入样例】
2
【输出样例】
73
【来源】
No
1. #include<iostream> 2. #include<stdio.h> 3. using namespace std; 4. int f[1002][2]={0}; 5. int main() 6. { 7. int n,x,i; 8. scanf("%d",&n); 9. f[1][0]=9;//f[i][0]前i位取偶数个3有几种情况 10. f[1][1]=1;//f[i][1]前i位取奇数个3有几种情况 11. for(i=2;i<=n;i++){ 12. x=9;//低于最高位取偶数个3有9种情况 13. if(i==n) x=8;//最高位取偶数个3有8种情况 14. f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;//i是偶数的情况+i为奇数的情况 15. f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;//i是偶数的情况+i为奇数的情况 16. } 17. printf("%d",f[n][0]); 18. return 0; 19. }
