資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告