题解 | 游游的字符重排

//最后一舞
#include<bits/stdc++.h>
using namespace std;
#define out(x) cout << #x << '=' << (x) << endl
#define out2(x, y) cout << #x << '=' << (x) << ',' << #y << '=' << (y) << endl 
#define int long long
#define lc u<<1
#define rc u<<1|1
#define pb push_back
#define vt vector
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define PII pair<int,int>
#define endl "\n"
#define il inline
typedef unsigned long long ULL;
typedef long long ll;
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
mt19937_64 rnd(time(0));
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
const int P = 13331;
const int N = 200005;
string s;
int dp[(1 << 10) + 1][10]; //mask集合,以j结尾的合法串数量
void solve(){
	cin >> s;
	int n = s.size();
	for(int i = 0; i < s.size();i++){
		dp[(1 << i)][i] = 1;
	}
	for(int i = 0; i < (1 << n);i++){
		
		for(int j = 0;j < n;j++) if(!(i & (1 << j))){
			
			map<int,int> mp;
			for(int k = 0;k < n;k++) if((i & (1 << k)) && !mp.count(s[k])){
				mp[s[k]] = 1;
				if(s[j]==s[k]) continue;
				dp[i | (1 << j)][j] += dp[i][k];
			}
		}
	}
	int ans = 0;
	map<int,int> mp;
	for(int i = 0;i < n;i++) {
		if(mp.count(s[i])) continue;
		mp[s[i]] = 1;
		ans += dp[(1 << n) - 1][i];
	}
	cout << ans;

}

signed main(){
	std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
	int times = 1;
	//cin >> times;
	while(times--){
		solve();
	}
	return 0;
}

状压DP,因为子串会重复,所以新枚举的k如果都是同一个字符,那么答案只加一次