传智杯省赛第一次(C题)

题目大致意思:

给你一个字符串s1,长度为n, 让你求存在多少个个符串s2(小写的字母)使得,二者满足以下条件

• s2中每个元素都和s1不一样
• s1和s2同构, 同构的意思是 s1[i] - s2[i] = s1[i +1] - s2[i + 1]...... 也就是s2和s1对应的相减的值是一样的 比如s1 = "abc" 和s1同构的之一是 "bcd" 也就是b-a = c-b = d-c

分析:

间接的去做 先去考虑满足条件1 也就是元素都不一样 也就是说 s2数组每一位都有25种选择,比如当前s1[i] = 'a' 那我的s2[i] 除了'a'其他都是可以去选择的 那么只考虑条件1,获得的总数是 25^n 然后再去减去同构的 那么剩下的就是不同构的了 也就是满足条件的了

同构的个数 就是这个s1字符串里面最大的字符c 到'z'的距离dis 原因是 当这个同构的距离大于dis是 字符串里面最大的这个字符c加上dis是大于'z'的(不再是小写字母的范围了) 也就是构不成同构的了?

代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int a[N];
int n, m, ret = 1;
string s;

signed main() {
	cin >> s;
	n = s.size();
	if(n == 1) {
		cout << 0 << endl;
	}
	sort(s.begin(), s.end() );
	for(int i = 1; i <= n; ++ i ) {
		ret *= 25;
		ret %= mod;
	} 
	ret -= ('z' - s[n - 1]);
	cout << ret << endl;
	return 0;
}