数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找长度为n、由m个字母组成的字母表中的字母构成且不包含回文子串的字符串
假设我们有m个字母和另一个值n。我们必须计算使用这些m个字母创建的长度为n的字符串的数量，并且字符串不包含长度大于1的回文子串。如果答案太大，则将结果模10^9+7。
因此，如果输入类似于n = 2 m = 3，则输出将为6，因为m = 3，所以如果字母表为{x,y,z}，我们可以生成如下字符串：[xx,xy,xz,yx,yy,yz,zx,zy,zz]，但[xx,yy,zz]无效，因此有6个字符串。
为了解决这个问题，我们将遵循以下步骤：
- p := 10^9+7
- 如果n等于1，则
- 返回m mod p
- 如果n等于2，则
- 返回m *(m - 1) mod p
- 如果m <= 2，则
- 返回0
- 返回m*(m-1) * ((m-2)^(n-2) mod p) mod p
示例
让我们看下面的实现以更好地理解：
def solve(n, m):
p = 10**9+7
if n == 1:
return m % p
if n == 2:
return m * (m - 1) % p
if m <= 2:
return 0
return m * (m - 1) * pow(m - 2, n - 2, p) % p
n = 2
m = 3
print(solve(n, m))输入
3, [1,2,3,4,1]
输出
6
更新于：2021年10月25日
264 次浏览
广告