NC224877. RainbowStrings
描述
Define a Rainbow String as a string where every letter in the string is distinct. The empty string is a Rainbow String.
Given a string of lower-case letters, compute the number of different subsequences which are Rainbow Strings. Two subsequences are different if letter at a specific position is included in one subsequence but not the other. Thus, two different subsequences may result in the same string.
For example, consider the string aab. The following six subsequences (in bold and underlined) are the only Rainbow Strings in aab:
aab aab aab aab aab <empty>
The answer may be large, so output the answer modulo 11092019.
输入描述
The single line of input contains a string s (1 ≤ |s| ≤ 105) which consists only of lower-case letters.
输出描述
Output a single integer, which is the number of subsequences of s which are Rainbow Strings.
示例1
输入:
aab
输出:
6
示例2
输入:
icpcprogrammingcontest
输出:
209952
Pascal 解法, 执行用时: 2ms, 内存消耗: 332K, 提交时间: 2021-08-31 13:05:24
var s:ansistring;
n,i,ans:longint;
a:array ['a'..'z'] of longint;
j:char;
begin
readln(s);
fillchar(a,sizeof(a),0);
for i:=1 to length(s) do
inc(a[s[i]]);
ans:=1;
for j:='a' to 'z' do
ans:=(ans mod 11092019)*((a[j]+1) mod 11092019) mod 11092019;
write(ans);
end.
C++ 解法, 执行用时: 4ms, 内存消耗: 520K, 提交时间: 2021-08-31 15:42:40
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
map<char,LL> m;
string s;
int main()
{
cin>>s;
for(int i=0;i<s.size();i++) m[s[i]]++;
LL res=1;
for(auto i:m) res=res*(i.second+1)%11092019;
cout<<res<<endl;
}
Python3 解法, 执行用时: 54ms, 内存消耗: 7052K, 提交时间: 2021-08-31 15:56:09
s = input()
result = 1
for i in range(26):
ch = chr(ord('a') + i)
result *= s.count(ch) + 1
print(result % 11092019)