「NowCoder」配对

题目大意：给出 $N$ 个长度为 $L$ 的字符串，字符集为 $\lbrace a\cdots h\rbrace$，$K$ 次选择两个字符让他们等价，问最多可以让多少对字符串完全等价？$N \leq 100,L\leq 1000,K\leq 28$

直接枚举选择哪些字母配对很慢，可以考虑枚举联通块，当 $K\geq7$ 时，显然所有串都能相同了，因为只需要 $7$ 条边就能让所有字母等价。

考虑枚举字母的联通块情况，而贪心地想，$K$ 肯定用完最好，因此联通块就只有 $S(N,K)$ 种情况。

$N=8$ 时的二类斯特林数为：$0\ 1\ 127\ 966\ 1701\ 1050\ 266\ 28\ 1$，实际可以跑一个爆搜看看要遍历多少个状态。

枚举完联通块情况后，每个字符串中，每种字符替代为对应联通块编号，变成等价的字符串。

然后计算哈希排序算等价对数，但这样可能超时，算一次哈希的复杂度为 $O(L)$，可以按字母分别维护每个字母出现位置的哈希值，重新算时复杂度是 $O(\Sigma)$，而不是 $O(L)$ 的。（$\Sigma$ 表示字符集的大小）

即如果一个字符串为：$abcaac$，那么我们预处理时把它标记为 $\alpha \times 100110+\beta \times 10000+\gamma \times 1001$，其中 $\alpha,\beta,\gamma$ 分别为 $a,b,c$ 所属连通块的编号。

#include <cstdio>
#include <algorithm>

int n, L, K, a[105][10], b[105], be[10], ans;
char s[105][1005];

int max(int x, int y) { return x > y ? x : y; }

void work() {
	int res, cnt;
	for (int i = 1; i <= n; ++i) {
		res = 0;
		for (int j = 0; j < 8; ++j)
			res += a[i][j] * be[j];
		b[i] = res;
	}
	std::sort(b + 1, b + n + 1);
	res = cnt = 0;
	for (int i = 1; i <= n; ++i) {
		++cnt;
		if (b[i] != b[i+1] || i == n) {
			res += cnt * (cnt - 1) / 2;
			cnt = 0;
		}
	}
	ans = max(ans, res);
}
void dfs(int cur, int tot) { //枚举连通块
	if (cur == 8) {
		if (tot >= 8 - K) work();
		return; 
	}
	for (int i = 1; i <= tot; ++i) {
		be[cur] = i;
		dfs(cur + 1, tot);
	}
	be[cur] = tot + 1;
	dfs(cur + 1, tot + 1);
}

int main() {
	scanf("%d%d%d", &n, &L, &K);
	for (int i = 1; i <= n; ++i) scanf("%s", s[i]);
	for (int i = 1; i <= n; ++i) //预处理
		for (int j = L - 1, k = 1; j >= 0; --j, k *= 10)
			a[i][s[i][j]-'a'] += k;
	dfs(0, 0);
	printf("%d\n", ans);
	return 0;
}

时间复杂度 $O\left(NL+S(N,K)\times\Sigma \times N^2\log N\right)$