当前位置：首页 > news >正文

传智杯第六届-复赛-D

news 2025/7/7 16:06:03

题目描述：

        小红定义两个字符串同构，当且仅当对于i∈[1,n],b[i]−a[i]i∈[1,n],b[i]-a[i]i∈[1,n],b[i]−a[i]是定值。例如，"bacd"和"edfg"是同构的。

        现在小红拿到了一个长度为n的字符串a，她想知道，有多少长度为n的字符串b同时满足以下两个条件：
        1.b的每一位都和a不同。
        2.b和a不同构。

输入描述:

输入一个仅由英文小写字母组成的字符串，代表字符串a。字符串长度不超过10^5。

输出描述:

一个整数，代表合法的字符串b的数量。由于答案过大，请对10^9+7取模。

示例1

输入：

输出：

说明：

任意长度为1的字符串都和"a"同构。

示例2

输入：

ab

输出：

解题步骤：

①输入

②计算共有多少个情况的发生：每个位置都会有25中可能，所以是25*n

③计算同构的情况：同构情况就是某种位置上的字符不同就对应1种情况，计算同构情况就是计算在该位置上可以取多少个元素，即25-（最大元素-最小元素）

④计算最终的情况：即总情况-同构情况

⑤输出

注意：

①计算total的时候，可能会出现超出字符长度的情况，所以需要提前对其进行取模的操作，而不是最后才进行取模的操作。

代码：

#include<iostream>
#include<string>
#include<math.h>
#define int long long
using namespace std;
signed  main()
{//输入string str;getline(cin, str);//计算共有多少个情况的发生(25^n个)，每个位置有25种情况int mod = 1e9 + 7;int n = str.length();   //字符串的长度int total = 1;for (int i = 0;i < n;i++){total = (total * 25) % mod;}//计算同构的情况char mi = str[0];   //最小字符char ma = str[0];    //最大字符for (int i = 1;i < n;i++){mi = min(mi, str[i]);   //找到最小字符ma = max(ma, str[i]);   //找到最大字符}int isomorphism = 25 - (ma - mi);//计算最终的情况	int sum = (total - isomorphism) % mod;//输出cout << sum << endl;system("pause");
}