思路：乘法原理+组合数学+贡献法计数

我们考虑第$i(0\le i\le25)$个字符出现两次对答案的贡献

这个需要基于乘法原理去计算，分别去枚举所有字母有多少种情况，然后累乘即可

使用哈希表$cnt$来统计每个字符出现的次数

对于字符$i$来说，它的情况为$C(cnts[i],2)=\frac{cnts[i]\times (cnts[i]-1)}{2}$

那么对于任意一个与$i$不相等的字符$j$，它的出现情况可以是0次，1次，3次，4次...

这个结果不是很好计算，我们换一个角度考虑，考虑它所有的方案数-出现次数为2的方案数

答案则为$2^{cnts[j]}-C(cnts[j],2)$

对于2的幂次，我们可以使用快速幂计算，也可以通过预处理得到对应的结果

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1E5+10;
long long qmi(long long a, long long b,long long p) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main(){
    string s;
    cin>>s;
    vector<int>cnts(26,0);
    for(char &ch:s){
        cnts[ch-'a']++;
    }
    long long res=0;
    for(int i=0;i<26;i++){
        if(cnts[i]<2)continue;
        long long cnt=1ll*cnts[i]*(cnts[i]-1)/2;
        for(int j=0;j<26;j++){  //枚举其他字符出现的次数0,1,3,...(就是不能出现2次)
            if(j==i)continue;
            long long cur=(qmi(2,cnts[j],mod)-1ll*cnts[j]*(cnts[j]-1)/2+mod)%mod;
            cnt=(cnt*cur)%mod;
        }
        res=(res+cnt)%mod;
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int mod = (int)1e9 + 7;
    static final int N = (int)1E5 + 10;

    static long qmi(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int[] cnts = new int[26];
        for(char ch : s.toCharArray()){
            cnts[ch-'a']++;
        }
        long res = 0;
        for(int i = 0; i < 26; i++){
            if(cnts[i] < 2) continue;
            long cnt = 1L * cnts[i] * (cnts[i] - 1) / 2;
            for(int j = 0; j < 26; j++){  //枚举其他字符出现的次数0,1,3,...(就是不能出现2次)
                if(j == i) continue;
                long cur = (qmi(2, cnts[j]) - 1L * cnts[j] * (cnts[j] - 1) / 2 + mod) % mod;
                cnt = (cnt * cur) % mod;
            }
            res = (res + cnt) % mod;
        }
        System.out.println(res);
    }
}

Python

mod = 10**9 + 7
N = 10**5 + 10

def qmi(a, b):
    res = 1
    while b > 0:
        if b & 1: res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

s = input().strip()
cnts = [0]*26
for ch in s:
    cnts[ord(ch)-ord('a')] += 1
res = 0
for i in range(26):
    if cnts[i] < 2: continue
    cnt = cnts[i]*(cnts[i]-1)//2
    for j in range(26):  #枚举其他字符出现的次数0,1,3,...(就是不能出现2次)
        if j == i: continue
        cur = (qmi(2, cnts[j]) - cnts[j]*(cnts[j]-1)//2 + mod) % mod
        cnt = (cnt * cur) % mod
    res = (res + cnt) % mod
print(res)

题目描述

定义特殊的字符串为满足有且仅有一种字符出现了$2$次。

小红得到了一个字符串，他想知道该字符串中有多少个子序列满足特殊条件。答案对$10^9+7$ 取模。

子序列在原串中可以不连续，但相对顺序必须和原串相等。

输入描述

一个长度不超过 $200000$ 的且仅包含小写字母的字符串

输出描述

满足答案的子序列数量。答案对$10^9+7$取模。

样例

输入

abccc

输出

12

说明

子序列“$abcc$"满足要求，有$3$个子序列"$abcc$"

子序列"$bcc$"满足要求，有$3$个子序列"$bcc$"

子序列“$acc$"满足要求，有$3$个子序列"$acc$"。

子序列"$cc$"满足要求，有$3$个子序列"$cc$"。