蓝桥集训之牛的基因学

蓝桥集训之牛的基因学

• 核心思想：贡献法

  • 考虑t中每个字母对答案的影响
  • 为s中相同字母的数量
  • 所以有多少种方案 即为有几个字母出现次数最多
  • 最终t字符串为最多次数的字母组成 1ⁿ 2ⁿ 3ⁿ 4ⁿ

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010, MOD = 1e9 + 7;
    
    int n;
    int cnt[100];
    char s[N];
    
    int main()
    {
        cin>>n>>s;
        int mx=0,ct=0;
        for(int i=0;i<n;i++)
        {
            int t = ++cnt[s[i]];  //每次找到++
            if(t>mx) mx = t , ct = 1;  //t为新的最值
            else if(t==mx) ct++;  //多个字母都最多次数
        }
        
        LL res=1;
        for(int i=0;i<n;i++)
        {
            res = (LL)res * ct % MOD;  //结果为ct的n次方%MOD
        }
        cout<<res;
    }