官方题解 | 计数改良

20pts

深搜，参考下面的代码.

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int dfs(int ct, bool a, bool b, bool c){//a代表有没有3，b代表有没有5，c代表有没有7 
	if(ct > n) return (a && b && c);
	return dfs(ct + 1, 1, b, c) + dfs(ct + 1, a, 1, c) + dfs(ct + 1, a, b, 1);
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		cout << dfs(1, 0, 0, 0) << '\n';
	}

	return 0;
}

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

---

40pts

我们发现前四个测试点答案也就不超过 $15$ 种，考虑记忆化.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n;
const int mod = 1e9 + 7;
int ans[1005];
int dfs(int ct, bool a, bool b, bool c){//a代表有没有3，b代表有没有5，c代表有没有7 
	if(ct > n) return (a && b && c);
	return (dfs(ct + 1, 1, b, c) + dfs(ct + 1, a, 1, c) + dfs(ct + 1, a, b, 1)) % mod;
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		if(ans[n]) cout << ans[n] << '\n';//记忆化
		else cout << (ans[n] = dfs(1, 0, 0, 0)) << '\n';
	}

	return 0;
}

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

总时间复杂度：$O(3^N)$.

---

100pts

既然最终答案能记忆化，那能不能每个过程都记忆化一遍呢？

我们可以记录第 $i$ 位每种 $357$​ 出现情况的种类数，分类讨论.

将 $357$ 都出现的情况记作 $A$，将 $357$ 出现两个的情况记作 $B$，将 $357$ 出现一个的情况记作 $C$.

$A$：

1. 可以由上一个 $A$ 填上 $3,5,7$ 获得，情况数 $\times 3$.
2. 可以由上一个 $B$ 填上所缺的数获得.

$B$：

1. 可以由上一个 $B$ 填上 $3,5,7$ 中的两个数字获得，情况数 $\times 2$.
2. 可以由上一个 $C$ 填上所缺的数获得.

$C$：

可以由一个都没有获得.

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
int dp[10000005][8];
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	dp[0][0] = 1;
    for(int i = 1; i <= 10000000; i++){
		for(int j = 1; j <= 7; j++){
			dp[i][j] = 1ll * __builtin_popcount(j) * dp[i - 1][j] % mod;//由上一个相同的
			if(j & 1) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 1]) % mod;//无 -> C
			if(j & 2) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 2]) % mod;//C -> B
			if(j & 4) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 4]) % mod;//B -> A
		}
	}
    int t;
    cin >> t;
    while(t--){
        int n;
    	cin >> n;
    	cout << dp[n][7] << endl;
    }
	return 0;
}

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

预处理时间复杂度：$O(N)$.

总时间复杂度：$O(N)$​.

如果你嫌内存占用太大了，你可以多花费 $O(T\log T)$ 的时间复杂度转离线，把空间复杂度降至 $O(1)$.

---

120pts

Macw老师提出来一个快速的办法，理论上可以通过 $T=1,N\le 10^{10^7}$ 的数据！

首先是随便选取 $357$ 中的任意一位，总共有 $3^N$ 种情况.

然后减去只选择两个数的，即只选 $35$ 的，只选 $37$ 的和只选 $57$ 的，共有 $3\times 2^N$ 种情况.

我们发现只选一个数的情况多选了一次，所以需要加回，即将结果 $+3$.

这样就可以以 $O(\log N)$ 的时间复杂度求出答案了！

我们注意到 $10^9+7$ 与 $2,3$ 均互质，所以对于更大的数可以用费马小定理来将 $N$ 降至 $10^9+5$ 以内.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int pow(int n, int k){//快速幂
	int ans = 1;
	while(k){
		if(k & 1) ans = ans * n % mod;
		n = n * n % mod, k >>= 1;
	}
	return ans;
}
signed main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		if(n < 3) cout << "0\n";//特判不足3的
		else cout << ((pow(3, n) - pow(2, n) * 3 % mod + 3) % mod + mod) % mod << '\n';//计算结果
	}
	
	return 0;
}

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