问题 A: Colorful Subsequence

题目描述

You are given a string S of length N. Among its subsequences, count the ones such that all characters are different, modulo 109+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.

Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.

Constraints
·1≤N≤100000
·S consists of lowercase English letters.
·|S|=N

输入

Input is given from Standard Input in the following format:

N
S

输出

Print the number of the subsequences such that all characters are different, modulo 109+7.

样例输入

4
abcd

样例输出

15

提示

Since all characters in S itself are different, all its subsequences satisfy the condition.

题目大意：

要找出符合要求的所有子串的个数，要求是这个子串中没有相同的字母，如果位置不同但子串元素相同，我们把它看作是不同的子串。

思路：

每一个字母出现的次数，因为字串中不能出现相同的字母，所以对于一种字符，出现的情况是出现次数（在这些位置出现）加一（不出现），利用组合数学的思想，乘法原理，最后，再减去所有字母都不出现的情况。

AC代码：

#include<bits/stdc++.h>
using namespace std;
long long book[100];
int main()
{
    long long n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        int pos=s[i]-'a';
        book[pos]++;
    }
    long long ans=1;
    for(int i=0;i<100;i++)
    {
        ans=(ans*(book[i]+1))%(1000000007);
    }
    cout<<ans-1;
    return 0;
}