字符变换

题目链接：YBT2022寒假Day7 A

题目大意

给你一个只包含四种字符的字符串，和一些二元组 (x,y)，x,y 为两个等长的字符串。
一个二元组的作用是可以选择字符串中一个与 x 相同的子串把它变成 y。
你也可以任意交换字符串两个位置的字符。
然后问你从任意字符串开始进行任意次变换，最多能得到多少个字符串。

思路

你考虑因为可以交换位置，所以字符串我们只需要关心它每个字符的个数，至于这个的方案你就可以用 $\frac{n!}{a!b!c!(n-a-b-c)!}$ 来求。
然后要注意的是因为 $n$ 有三十，不能直接预处理阶乘，我们就分解质因数之类的搞即可。

然后你发现如果通过变换某个状态 $x$ 可以变到某个状态 $y$，那我们可以把它们连一条有向边，代表如果你变换到 $x$，你可以继续变换到 $y$。
然后你可以用 Tarjan 缩点，然后我们考虑这个状态的数量。

然后发现字符串长度很小，我们考虑状压，发现状态数不多可以搞，设 $f_x$ 为从任意点开始走到 $x$ 的最大数量。
（压三个数的即可，第四个直接用 $n$ 减去前三个就是了）

然后这么搞 Tarjan 完 DP 一下就得到答案了。

代码

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define ll long long
#define MAXN ((n + 1) * (n + 1) * (n + 1))using namespace std;struct awa {int a[4];
};
struct node {int to, nxt;
}e[6000001], e_[6000001];
int n, m, le[1000001], KK, a[1001][5], b[1001][5], sz[1001];
int le_[1000001], KK_;
char s[31], ss[31];
ll val[1000001];vector <int> q;int get_(int a, int b, int c, int d) {return a * (n + 1) * (n + 1) + b * (n + 1) + c;
}ll clac(awa now) {q.clear();for (int i = 0; i < 4; i++) {for (int j = 2; j <= now.a[i]; j++) q.push_back(j);}
//	__int128 re = 1;ll re = 1;for (int i = 2; i <= n; i++) {re *= i;for (int j = 0; j < q.size(); j++)if (q[j] != 1 && re % q[j] == 0) {re /= q[j]; q[j] = 1;}}return (ll)re;
}int dfn[1000001], low[1000001], col[1000001], tmpt, sta[1000001], tot;
ll vals[1000001];void add(int x, int y) {e[++KK] = (node){y, le[x]}; le[x] = KK;
}void add_(int x, int y) {e_[++KK_] = (node){y, le_[x]}; le_[x] = KK_;
}void tarjan(int now) {dfn[now] = low[now] = ++tmpt;sta[++sta[0]] = now;for (int i = le[now]; i; i = e[i].nxt)if (!dfn[e[i].to]) {tarjan(e[i].to);low[now] = min(low[now], low[e[i].to]);}else if (!col[e[i].to]) low[now] = min(low[now], low[e[i].to]);if (dfn[now] == low[now]) {col[now] = ++tot;vals[tot] = val[now];while (sta[sta[0]] != now) {vals[tot] += val[sta[sta[0]]];col[sta[sta[0]]] = tot;sta[0]--;}sta[0]--;}
}queue <int> qq;
ll f[1000001], ans;
int du[1000001];int main() {
//	freopen("character.in", "r", stdin);
//	freopen("character.out", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1; i <= m; i++) {scanf("%s %s", s + 1, ss + 1); sz[i] = strlen(s + 1);for (int j = 1; j <= sz[i]; j++) a[i][s[j] - 'A']++, b[i][ss[j] - 'A']++;}for (int i = 0; i < MAXN; i++) {awa now;now.a[0] = i / (n + 1) / (n + 1) % (n + 1);now.a[1] = i / (n + 1) % (n + 1);now.a[2] = i % (n + 1);if (now.a[0] + now.a[1] + now.a[2] > n) continue;now.a[3] = n - now.a[0] - now.a[1] - now.a[2];val[i] = clac(now);for (int j = 1; j <= m; j++) {bool yes = 1;for (int k = 0; k < 4; k++)if (now.a[k] < a[j][k]) {yes = 0; break;}if (yes) {int to = get_(now.a[0] - a[j][0] + b[j][0], now.a[1] - a[j][1] + b[j][1], now.a[2] - a[j][2] + b[j][2], now.a[3] - a[j][3] + b[j][3]);if (i != to) add(i, to);}}}for (int i = 0; i < MAXN; i++) {awa now;now.a[0] = i / (n + 1) / (n + 1) % (n + 1);now.a[1] = i / (n + 1) % (n + 1);now.a[2] = i % (n + 1);if (now.a[0] + now.a[1] + now.a[2] > n) continue;now.a[3] = n - now.a[0] - now.a[1] - now.a[2];if (!dfn[i]) tarjan(i);}for (int i = 0; i < MAXN; i++) {awa now;now.a[0] = i / (n + 1) / (n + 1) % (n + 1);now.a[1] = i / (n + 1) % (n + 1);now.a[2] = i % (n + 1);if (now.a[0] + now.a[1] + now.a[2] > n) continue;now.a[3] = n - now.a[0] - now.a[1] - now.a[2];for (int j = 1; j <= m; j++) {bool yes = 1;for (int k = 0; k < 4; k++)if (now.a[k] < a[j][k]) {yes = 0; break;}if (yes) {int to = get_(now.a[0] - a[j][0] + b[j][0], now.a[1] - a[j][1] + b[j][1], now.a[2] - a[j][2] + b[j][2], now.a[3] - a[j][3] + b[j][3]);if (col[i] != col[to]) add_(col[i], col[to]), du[col[to]]++;}}}for (int i = 1; i <= tot; i++)if (!du[i]) {qq.push(i);f[i] = vals[i]; ans = max(ans, f[i]);}while (!qq.empty()) {int now = qq.front(); qq.pop();for (int i = le_[now]; i; i = e_[i].nxt) {int x = e_[i].to;f[x] = max(f[x], f[now]);du[x]--;if (!du[x]) {qq.push(x);f[x] += vals[x]; ans = max(ans, f[x]);}}}printf("%lld", ans);return 0;
}