Python中有用于查找严格增加的彩色蜡烛序列数量的程序
假设有n根蜡烛从左到右对齐。从左侧开始的第i根蜡烛的高度为h[i]，颜色为c[i]。我们还有一个整数k，表示有1到k范围内的颜色。我们必须找出有多少个严格递增的彩色糖果序列？根据高度检查递增序列，如果在1到K范围内至少有一种每种颜色的蜡烛可用，则称该序列是彩色的。如果答案太大，则返回结果mod10^9+7。
所以，如果输入像K=3h=[1,3,2,4]c=[1,2,2,3]，那么输出将为2，因为它有序列[1,2,4]和[1,3,4]。
示例
让我们看看以下实现以获得更好的理解-
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