AT4691题解

Yukinoshita_Yukino · 2021-07-19 19:59:07 · 题解

一句话题意：给定一个长度为 n 的字符串，求其中不含相同字母子串的个数。

答案子串的长度是一定小于等于原字符串中字符种类数的。

先看一眼样例字符串: abcd

我们可以画一个图感受一下：

上图四个方格代表可以放字符的地方（也可以不放）。方格下面的数代表此方格的情况数。在这个样例中有两种情况，放或者不放，所以情况数是2。

更普遍的，如果有 n 个相同字母，则有 n+1 个情况数。根据小学学过的乘法原理，把以上数连乘起来就好。

PS:十年OI一场空，不开longlong见祖宗

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int t[30];
char str[100010];
const int mod=1e9+7;
signed main()
{
    cin>>n;
    cin>>str;
    for(int i=0;i<26;i++) 
        t[i]=1;
    for(int i=0;i<n;i++) 
        t[str[i]-'a']++;
    int ans=1;
    for(int i=0;i<26;i++) 
    {
        ans*=t[i];
        ans%=mod;
    }
    cout<<ans-1;
    return 0;
}