RT，看上去像是被卡常了，本地只跑 $3.6$ 秒左右。

求助卡常并求问有无时间复杂度更优秀的做法。

代码：

#pragma GCC optimize("Ofast")

#include <iostream>
#include <algorithm>
#include <map>
#include <bitset>
#include <cstring>

using namespace std;

#define set(a, b) a[b >> 5] |= 1 << (b & 31)

typedef long long ll;
typedef unsigned long long ull;

const int N = 42331 + 7, block = 510510, block_size = block >> 5, M = 9, K = 5e8 + 7, P = 7, Q = 1e9 - 1, seed = 1e9 + 7;
int D;
int prime[N], pre_block[block_size + 7], cur_block[block_size + 7], d[M + 7];
char p[block + 7];
map<ull, int> mp[M + 7];
bitset<K> bs;

inline void init(){
	int cnt = 0;
	p[0] = p[1] = true;
	set(pre_block, 0);
	set(pre_block, block);
	for (register int i = 2; i <= block; i++){
		if (!p[i]){
			prime[++cnt] = i;
			if (i > 2) bs[i >> 1] = true;
			if (cnt <= P) set(pre_block, i);
		}
		for (register int j = 1; j <= cnt && i * prime[j] <= block; j++){
			int t = i * prime[j];
			p[t] = true;
			if (j <= P) set(pre_block, t);
			if (i % prime[j] == 0) break;
		}
	}
	for (register int i = 1; i * block <= Q; i++){
		int end = (i + 1) * block - 1, start = i * block;
		memcpy(cur_block, pre_block, sizeof(cur_block));
		for (register int j = P + 1; prime[j] * prime[j] <= end; j++){
			int t1 = max((start - 1) / prime[j] + 1, prime[j]) * prime[j], t2 = prime[j] << 1;
			for (register int k = (t1 & 1 ? t1 : t1 + prime[j]) - start; k < block; k += t2){
				set(cur_block, k);
			}
		}
		for (register int j = 0; j <= block_size; j++){
			int t1 = ~cur_block[j];
			while (t1){
				int t2 = __builtin_ctz(t1);
				if ((j << 5) + t2 >= block) break;
				int cur = start + (j << 5) + t2;
				if (cur > Q) break;
				bs[cur >> 1] = true;
				t1 -= t1 & ((~t1) + 1);
			}
		}
	}
}

int main(){
	int t;
	cin >> t;
	init();
	for (register int i = 1; i <= t; i++){
		ull hash_val = 0;
		cin >> D;
		for (register int j = 1; j <= D; j++){
			cin >> d[j];
		}
		if (D == 1){
			if (!p[d[1]]){
				cout << 1 << endl;
			} else {
				cout << 0 << endl;
			}
			continue;
		}
		sort(d + 1, d + D + 1);
		for (register int j = 1; j <= D; j++){
			hash_val = hash_val * seed + d[j];
		}
		if (mp[D].count(hash_val)){
			cout << mp[D][hash_val] << endl;
			continue;
		}
		int ans = 0;
		for (register int j = D + 1; j <= M; j++){
			d[j] = 0;
		}
		do {
			ans += (d[1] & 1) && (d[1] ^ 5) && d[D] && bs[(d[1] + 10 * d[2] + 100 * d[3] + 1000 * d[4] + 10000 * d[5] + 100000 * d[6] + 1000000 * d[7] + 10000000 * d[8] + 100000000 * d[9]) >> 1];
		} while (next_permutation(d + 1, d + D + 1));
		mp[D][hash_val] = ans;
		cout << ans << endl;
	}
	return 0;
}