E - Rainbow Strings

本文主要是介绍E - Rainbow Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果字符串中的每个字母都不同，则将字符串定义为彩虹字符串。空字符串也被认为是彩虹字符串。
给定一个小写字母字符串，计算彩虹字符串的不同子序列的数量。如果一个子序列中包含索引，但另一个子序列不包含索引，则即使生成的字符串相同，两个子序列也是不同的。
在第一个示例中，有8个子序列。唯一不是彩虹字符串的子序列是 aa 和 aab。
剩下的6个子序列是彩虹串。

输入
输入将由一行和一个仅由小写字母组成的字符串组成。字符串的长度介于1和100000之间（包括1和100000）。

输出
在一行上 写下彩虹序列的数量，取素数11092019的模。

Input1
aab
Output1
6
Input2
icpcprogrammingcontest
Output2
209952

解析：
对于每个字符都有两种情况，选与不选；
所以记录一下每个字符出现的次数 cnt[N];
对于每个字符 i,不选是一种情况，选是 cnt[i]种情况(因为不同的位置是不同的子序列)，
所以每个字符 i 就是 cnt[i]+1 种情况。
将这些情况相乘即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10,p=11092019;
int cnt[27];
string s;
void solve()
{cin>>s;for (int i=0;i<s.size();i++) cnt[s[i]-'a']++;int ans=1;for (int i=0;i<26;i++){if (cnt[i]>0) ans=(ans*(cnt[i]+1))%p;}cout<<ans;
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve(); return 0;
}

这篇关于E - Rainbow Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---