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;
  // 【1】 部分的情况
    for (auto x : st) {
        int a = max(0LL, 18 - x);
        res += C[a][n - 1];
    }

    if (n == m) {
        res += fact(n) - 1;//特殊的阶乘 -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++;
        }
        
        res += fact(n) * C[m][n];
         
    }
    cout << res << endl;
}
signed main() {
    t = 1;
    pre();
    cin >> t;
    while (t--)
        solve();

    return 0;
}