H题解
我太菜了,只会这题。。。坐牢坐了两个小时,不写个题解不足以发泄我的怒火
题意
给定 一个模板字符串 s 和目标长度 n , 求 美丽字符串的数量
满足下列两个条件中 任意一个 并且字符各不相同的字符串 被称为美丽的字符串
【1】第一个字符必须在 s 中 , 并且后续字符的字典序满足严格 严格单调递增
【2】所有字符都出现在 s 中 , 对于字典序大小没有要求
分析
因为【1】的限制条件多,先从 【1】 入手
第一个字符必须出现在s中,那么我们可以枚举 s中出现的字符作为 新的字符串中的第一个
后续的字符不需要出现在 s中,那么直接组合数计算
C(18-x , n-1) x是第一个字符 ,
C(18-x,n-1) 表示 从 18-x 中选择 n-1个
18-x , 意味着 小于 x 的数字不会被选择
n-1个,意味着 最终长度为 n
st 为 s字符串中出现的字符 构成的字符集 枚举 x ,代表枚举第一位的字符 for (auto x :st){ res += C(18-x , n-1); }
接着分析条件【2】
每一个字符必须出现在s中,排列顺序无所谓
那就是阶乘嘛 , 每一个数字各不相同,顺序无所谓
m = st.size(); res = fact[m];
但是注意 【1】 【2】 中存在重复的部分
样例中 ,s=ar , n = 2
[ar] 这个子串,在 【1】 【2】中都会被枚举到一次
需要考虑去重
分类讨论
令 n 为给定的长度 , m 为 字符集的数量
根据 n,m的大小关系进行讨论,便于去重
n > m
很明显,此时不需要去重
【2】要求 字符串中每个字符都出现在 s中
但是 字符串又需要满足 各不相同
那么就不可能出现满足【2】的字符串
也就是不需要去重
n == m
此时需要去重
但是注意,此时 仅仅存在一种重复的情况
条件【1】要求严格递增 , 也就是 形如 abcde
而【2】所有情况为 abcde 的阶乘, 仅有 abcde会出现重复
那么只需要加上 阶乘的数量再减去1即可
n<m
此时情况较为复杂
m > n, 但是 【2】的阶乘只需要 n个字符
那么,就是枚举从m个字符中,选择了n个的方案数量 ,再乘以阶乘
C[m][n] * fact[n]
然后再减去 【1】中重复的部分
cnt=1; for(auto x:st){ res -= C( m - cnt , n-1); cnt++; }
表示,枚举第一位 x
重复的部分为 , 后续 (m-cnt) 个字符中,选择 n-1个的方案数量
代码
#include <bits/stdc++.h> #define endl "\n" #define ls p << 1 #define rs p << 1 | 1 #define int long long #define pb push_back #define mem(a, b) memset(a, b, sizeof(a)) #define Ror(i, b, a) for (int i = (b); i >= (a); --i) #define For(i, a, b) for (int i = (a); i <= (b); i++) #define io \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0) using namespace std; typedef pair<int, int> PII; typedef unsigned long long u64; typedef long long ll; mt19937_64 mrand(random_device{}()); void random_shuffle(); template <typename T> inline void read(T& x) { int f = 1; x = 0; char c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } x = f * x; } template <typename T> inline void print(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0'); } // long long long // 数组开够 N+10 // 有向图 or 无向图 // 多组数据,初始化 // LLLLLLLLLLLLL const int N = 1e6 + 10, M = 1e3 + 10; const ll inf = 8e18; const int mod = 1e9 + 7; int t, n, m; int ar[N], br[N]; void No() { cout << "No\n"; } void Yes() { cout << "Yes\n"; } int fact(int x) { int ans = 1; for (int i = 2; i <= x; ++i) ans = ans * i; return ans; } int C[30][30]; void pre(int n = 20) { for (int i = 0; i <= n; ++i) { For(j, 0, i) { if (j == 0) C[i][j] = 1; else { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; } } } } void solve() { string s; cin >> s >> n; set<int> st; for (auto x : s) { st.insert(x - 'a' + 1); } m = st.size(); int res = 0; for (auto x : st) { int a = max(0LL, 18 - x); res += C[a][n - 1]; } if (n == m) { res += fact(n) - 1; } else if (n > m) { ; } else { int cnt = 1; for (auto x : st) { auto a = max(0LL, m - cnt); res -= C[a][n - 1]; cnt++; } // cout << res << " "; res += fact(n) * C[m][n]; // res -= (n * m) / 2; // cout << C(m, n) << " " << m << " " << n << endl; } cout << res << endl; } signed main() { t = 1; pre(); cin >> t; while (t--) solve(); return 0; }