偶数３的个数

时间限制: 1 Sec  内存限制: 64 MB

题目描述

“报告，我军已探出地雷阵中所有的地雷位置，并且还发现了一份使用说明书。”一个黑暗军团的小兵匆忙跑来，交给修罗王一张纸。

只见这张纸上面写道：“我是一颗萌萌的地雷，拆除我很容易，看到我身上标着的整数Ｎ了吗？你只要输入这个Ｎ位数中有多少个数中有偶数个数字3就可以把我拆除哦，加油！你行的。”

 

输入

一个整数Ｎ。

 

输出

输出这个Ｎ位数中有多少个数中有偶数个数字３。

 

样例输入

复制样例数据

2

样例输出

73

在前面加数，先考虑前导0，在代码中我已经写的很详细了

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
 
typedef long long LL;
using namespace std;
 
int n;
LL a[10005], b[10005];//a[i]表示i位有多少个偶数个3的数,b[i]表示i位有多少个奇数个3的数
 
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    scanf("%d", &n);
    a[1] = 9, b[1] = 1;
    for (int i = 2; i <= n; i++){
        a[i] = a[i - 1] * 9 + b[i - 1];//1.本来有偶数个3,在前面加上0~9除去3有9种(先考虑有前导0);2.奇数位3+一个3
        b[i] = b[i - 1] * 9 + a[i - 1];//1.本来有奇数个3,在前面加上0~9除去3有3中;2.有偶数个3，在前面加上一个3
    }
    printf("%lld\n", a[n] - a[n - 1]);//减去前导0
 
    return 0;
}

另外，因为没有范围，我觉得n应该有个10000吧，然后我用的大数，结果疯狂运行错误，我把a开到10000*10000就炸掉了，然后开个100*100就过了。。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
int a[105][105], b[105][105];//这位数有毒

void mul(int ans[], int c[], int d[]){
	for (int i = 1; i <= c[0]; i++){
		ans[i] += c[i] * 9;
		if(ans[i] > 9){
			ans[i + 1] += ans[i] / 10;
			ans[i] %= 10;
		}
	}
	int len = c[0];
	while(ans[len + 1]) len++;
	for (int i = 1; i <= d[0]; i++){
		ans[i] += d[i];
		if(ans[i] > 9){
			ans[i + 1]++;
			ans[i] -= 10;
		}
	}
	len = max(len, d[0]);
	while(ans[len + 1]) len++;
	ans[0] = len;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	a[1][0] = 1, a[1][1] = 9;
	b[1][0] = 1, b[1][1] = 1;
	for (int i = 2; i <= n; i++){
		mul(a[i], a[i - 1], b[i - 1]);
		mul(b[i], b[i - 1], a[i - 1]);
	}
	for (int i = 1; i <= a[n][0]; i++){
		a[n][i] -= a[n - 1][i];
		if(a[n][i] < 0){
			a[n][i] += 10;
			int t = i + 1;
			while(a[n][t] == 0){
				a[n][t] = 9;
				t++;
			}
			a[n][t]--;
		}
		if(i == a[n - 1][0]) break;
	}
	int len = a[n][0];
	while(a[n][len] == 0) len--;
	for (int i = len; i >= 1; i--) printf("%d", a[n][i]);
	printf("\n");

	return 0;
}
/**/