题解 AT4691 【[AGC031A] Colorful Subsequence】

· · 题解

AT4691 [AGC031A] Colorful Subsequence

虽然这道题是 AGC 中的，但作为A题其实和 ABC 的 B 题难度没区别。。。

关于题意

什么时候我的英语水平才能超越二年级 QAQ

英语真的很重要！！！

简单的说，就是—— 给定字符串 S，求其无重复字符子序列个数

注：不同位置上的同种字符不算同一个字符

比如：在字符串 abbc 中，其无重复字符子序列有 a, b, b, c, ab, ab, ac, bc, bc, abc 和 abc，共11个，所以 ans 为11

分析

由题意得。。。/xk 我们只需要先统计一下 a ~ z 每个字符的出现次数 然后将这些次数全部加上1，最后求积就行了

至于为什么。。。 相信大家用小学二年级学过的组合知识就能想出来啦

还有一件事—— 貌似空集不算在 ans 里面。。。 别问我为啥，反正样例里面没有算/kk

展示一下我的代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 310;//众所周知，ASCII应该不会大于310 
const int mod = 1e9 + 7;
int n, tem, ans = 1;
int cnt[maxn] = {0};
string s;

signed main()
{
    cin>>n;
    cin>>s;
    for(int i = 0; i < s.length(); i ++) {
        tem = s[i];
        cnt[tem] ++;
    }
    for(int i = 'a'; i <= 'z'; i ++) {
        ans *= cnt[i] + 1;
        ans %= mod;
    }
    cout<<ans - 1;//减去空集 
    return 0;
}