Upd：可以使用 AtCoder Lib 打表，可以在几秒内得到结果，详见文章末尾。

打表做法（~可能~不太具有普遍性，但确实可以）~114514114514 是一个很好的随机种子~。

首先，做一个非常简单的优化：为了使拼接后的子串种类不重复，可以构造使得其中一种符号远少于另一种，减少打表的次数（我的程序里控制比例为一比十）。

除此之外，其他所有内容都使用了暴力做法，求值函数为 O(n3)O(n^3)，判断函数为 O(n2log⁡n)O(n^2\log n)（使用了 map），最终单次枚举时间复杂度约为 O(n5log⁡n)O(n^5\log n)，在机房的 Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz 上花了几分钟时间。

这个算法中最重要的是选择正确的随机种子，在多次尝试后，我们发现将 114514114514 作为 mt19937 的种子来运行只需要一次枚举即可得出答案！

这是打表程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
int n;
mt19937 Rand();
string random(int size){
	string s="";
	for(int i=1;i<=size;i++){
		if(Rand()%10){
			s+='X';
		}
		else{
			s+='O';
		}
	}
	return s;
}
int getVal(string s){
	int tot=0;
	map<string,int>mp;
	for(int i=0;i<s.size();i++){
		for(int j=1;j<=s.size()-i;j++){
			string ss=s.substr(i,j);
			mp[ss]=1;
		}
	}
	for(auto _:mp){
		tot++;
	}
	return tot;
}
int N=30,mxl=5,mnl=1;
string s[10001];
int ans[1001][1001];
void init(){
	for(int i=1;i<=N;i++){
		mxl=i*20-1;
		mnl=min(i,15)*20-2;
		s[i]=random(Rand()%(mxl-mnl+1)+mnl);
	}
}
bool check(){
	map<int,int>mp;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=i;j++){
			cerr<<"#";
		}
		for(int j=i+1;j<=30;j++){
			cerr<<"-";
		}
		cerr<<endl;
		for(int j=1;j<=N;j++){
				if(mp[getVal(s[i]+s[j])]!=0){
					return 0;
				}
				else{
					mp[getVal(s[i]+s[j])]=1;
					ans[i][j]=getVal(s[i]+s[j]);
				}
		}
	}
	cerr<<endl;
	return true;
}
int main(){
	freopen("114514.txt","w",stdout);
	cerr<<"input the seed:"<<endl;
	int sd;
	//cin>>sd;
  sd=114514
	Rand.seed(sd);
	cerr<<"now use seed "<<sd<<endl;
	int tot=0;
	while(1){
		tot++;
		init();
		if(check()){
			cerr<<"#"<<tot<<" "<<"OK!"<<endl;
			cout<<"string s["<<N+10<<"]={\"\",";
			for(int i=1;i<=N;i++){
				cout<<"\""<<s[i]<<"\",";
			}
			cout<<"};";
			cout<<endl;
			for(int i=1;i<=N;i++){
				for(int j=1;j<=N;j++){
					cout<<"    ans["<<i<<"]"<<"["<<j<<"]="<<ans[i][j]<<";"<<endl;
				}
			}
			while(1);
			return 0;
		}
		else{
			cerr<<"#"<<tot<<" "<<"Fail!"<<endl;
		//	for(int i=1;i<=N;i++){
		//		cout<<s[i]<<" ";
		//	}
		//	cout<<endl;
		}
	}

	return 0;
}

运行情况：

输出：

最终代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
string s[40]={"","XXXXXOXXXXXXXOXXX  ......"};
int ans[40][40];
int main(){
  	ans[1][1]=414;
    ans[1][2]=1258;
    ......
    int n,k,q;
	cin>>n;
	for(int i=1;i<=n;i++){
		cout<<s[i]<<endl;
	}
	cin>>q;
	while(q--){
		cin>>k;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(ans[i][j]==k){
					cout<<i<<" "<<j<<endl;
				}
			}
		}
	}
	return 0;
}

另：我们发现@徐振轩2011的 UID（1334925）也是一个很好的种子

AtCoder Lib 优化

1
2
3
4
5
6
7
8
int getVal(string s){
    vector<int> sa = suffix_array(s);
    long long answer = 1LL * s.size() * (s.size() + 1) / 2;
    for (auto x : lcp_array(s, sa)) {
        answer -= x;
    }
	return answer;
}