왼쪽에서 오른쪽으로 정렬된 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]인 경우 시퀀스가 [1,2,4]이기 때문에 출력은 2가 됩니다. 및 [1,3,4].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- read() 함수를 정의합니다. T, 나
- s :=0
- 내가> 0일 때
- s :=s + T[i]
- s :=모드 10^9+7
- 나는 :=나는 -(나는 AND -i)
- 반환
- update() 함수를 정의합니다. T, i, v
- 내가 <=50010인 동안
- T[i] :=T[i] + v
- T[i] :=T[i] 모드 10^9+7
- 나는 :=나는 +(나는 그리고 -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 모드 10^9+7
- i(비트를 오른쪽으로 (c[j] - 1)번 이동한 후)가 홀수이면
- 만약 (i의 비트 수) mod 2가 k mod 2와 같으면
- R :=R + t
- R :=R 모드 10^9+7
- 그렇지 않으면
- R :=(R + 10^9+7) - t
- R :=R 모드 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