[AGC031A] Colorful Subsequence 题解

· · 题解

此题的大致思路：根据加法原理，若这个字符出现 x 次，那么有 x+1 种选择方案（不选或者选第 1 个、第 2 个……第 x 个）；又根据乘法原理，将每个字符的选择方案乘起来就是最终答案。

此题解与其他题解的不同之处在于，还运用了 STL 里的 std::count 函数；在这里给大家介绍一下此函数的用法。

这个函数和 sort 函数类似，原型如下：

count (_InputIterator __first, _InputIterator __last, const _Tp& __value)

具体意思就是，第一个参数给出要查找的容器的开始的迭代器，第二个参数给出要查找的容器的结束的迭代器，第三个参数给出要统计的值。例如，我们要统计一个 std::vector a 中 720 出现的个数，并赋值给变量 c，就可以这么写：

int c=count(a.begin(),a.end(),720);

放代码：

#include<iostream>
#include<algorithm> // count 函数存于 algorithm 头文件中
#define int long long // 本题数据要开 long long
using namespace std;
const int mod=1e9+7;
main(){
  int n,c=1; string s; cin>>n>>s;
  for(char i='a';i<='z';i++)
    (c*=count(s.begin(),s.end(),i)+1)%=mod; // 乘起来并取模
  cout<<c-1<<endl; // 减 1 是为了去掉空串
  return 0;
}