資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢嚴格遞增的彩色蠟燭序列的數量
假設有n支蠟燭，從左到右排列。從左側數起的第i支蠟燭的高度為h[i]，顏色為c[i]。我們還有一個整數k，表示顏色範圍為1到k。我們需要找到有多少個嚴格遞增的彩色蠟燭序列？遞增序列是根據高度檢查的，如果序列中至少包含1到K範圍內每種顏色的蠟燭，則稱該序列為彩色序列。如果答案過大，則返回結果模10^9 + 7。
所以，如果輸入類似K = 3，h = [1,3,2,4]，c = [1,2,2,3]，則輸出將是2，因為它包含序列[1,2,4]和[1,3,4]。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式read()。它將接收T和i作為輸入。
- s := 0
- 當i > 0時，執行以下操作：
- s := s + T[i]
- s := s mod 10^9+7
- i := i -(i AND -i)
- 返回s
- 定義一個函式update()。它將接收T、i和v作為輸入。
- 當i <= 50010時，執行以下操作：
- T[i] := T[i] + v
- T[i] := T[i] mod 10^9+7
- i := i +(i AND -i)
- 返回v
- 從主方法中執行以下操作：
- L := 2^k，R := 0，N := h的大小
- 對於範圍0到L - 1的i，執行以下操作：
- T := 一個大小為50009的陣列，並用0填充
- t := 0
- 對於範圍0到N - 1的j，執行以下操作：
- 如果(i向右移動(c[j] - 1)位後)為奇數，則
- t := t + update(T, h[j], read(T, h[j] - 1) + 1)
- t := t mod 10^9+7
- 如果(i向右移動(c[j] - 1)位後)為奇數，則
- 如果(i的位數)模2與k模2相同，則
- R := R + t
- R := R mod 10^9+7
- 否則，
- R := (R + 10^9+7) - t
- R := R mod 10^9+7
- 返回R
示例
讓我們看看以下實現，以便更好地理解：
def solve(k, h, c): def read(T, i): s = 0 while i > 0: s += T[i] s %= 1000000007 i -= (i & -i) return s def update(T, i, v): while i <= 50010: T[i] += v T[i] %= 1000000007 i += (i & -i) return v def number_of_bits(b): c = 0 while b: b &= b - 1 c += 1 return c L = 2 ** k R = 0 N = len(h) for i in range(L): T = [0 for _ in range(50010)] t = 0 for j in range(N): if (i >> (c[j] - 1)) & 1: t += update(T, h[j], read(T, h[j] - 1) + 1) t %= 1000000007 if number_of_bits(i) % 2 == k % 2: R += t R %= 1000000007 else: R += 1000000007 - t R %= 1000000007 return R k = 3 h = [1,3,2,4] c = [1,2,2,3] print(solve(k, h, c))
輸入
3, [1,3,2,4], [1,2,2,3]
輸出
2
更新於: 2021年10月23日
178 次瀏覽
廣告