官方题解 | 规律数列

显然规律是将上一个数+3,*3,+3,*3...

结果太大了，用 long long 也存不下.

我们可以尝试用数组模拟+3和*3操作.

但是如果每次查询都进行 $N$ 次运算就浪费太大了.

我们可以预处理，这样每次查询就只需要直接输出答案了.

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
struct bigInt{
	int a[1005];
	int len;
	bigInt(){
		memset(a, 0, sizeof(a));
		a[1] = 1;//第一位设为1 
		len = 1;
	}
	void print(){
		for(int i = len; i >= 1; i--) cout << a[i];
		cout << '\n';
	}
	void add_3(){
		a[1] += 3;//末位加3 
		for(int i = 1; i <= len; i++){
			if(a[i] >= 10){//逐位进位 
				if(i == len) len++;//首位进位要把位数+1 
				a[i + 1]++;
				a[i] -= 10;
			}
		}
	}
	void mul_3(){
		for(int i = 1; i <= len; i++){
			a[i] *= 3;//给每个位都乘3 
		}
		for(int i = 1; i <= len; i++){
			a[i + 1] += a[i] / 10;//逐位进位 
			a[i] %= 10;
		}
		if(a[len + 1]) len++;//首位进位要把位数+1 
	}
}a[1005];
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	for(int i = 2; i <= 1000; i++){//预处理
		a[i] = a[i - 1];
		if(i % 2 == 0) a[i].add_3();
		else a[i].mul_3();
	}
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		a[n].print();
	}

	return 0;
}

对于预处理，时间复杂度：$O(N^2)$.

对于每次查询，时间复杂度：$O(N)$.

总时间复杂度：$O(TN+N^2)$.