루미 알고리즘

#1612다이아Hair Dyeing

PO 2025 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Your friend has grown tired of their natural hair color and has decided it's time for a change.

Every day, your local hair salon has a big discount on one of its 10 hair dyes (none of which match your friend's natural hair color). They maintain a preliminary schedule of their discounts for the next N days but warn that the schedule may change in the future. Dyeing hair is, of course, not something to be done half-heartedly, so your friend wants to make a plan for how to dye their hair in the coming days.

Such a plan determines on which days your friend will go to dye their hair. When dyeing, they always choose the discounted color since it would be too expensive otherwise. In total, there are 2^N possible plans. However, they do not accept all plans: naturally, they do not want to dye their hair the same color two days in a row.

You have been asked by your friend to calculate how many different such plans they could create. However, each time you provide an answer, your friend informs you that the salon has updated its schedule, changing which color is on discount on one of the days.

Since the answer can be very large, you should output it modulo 2^64. This means the remainder of the answer after dividing by 2^64. In most programming languages, all calculations are automatically performed modulo 2^64 when using unsigned 64-bit integers. In C++, you can use unsigned long long.

Input

The first line of input contains two integers, N and Q (1 ≤ N ≤ 10^5, 0 ≤ Q ≤ 10^5), representing the number of days in the schedule and the number of schedule updates.

Next, there are N integers a_i (0 ≤ a_i ≤ 9), where a_i indicates that color a_i is on discount on day i.

After that, there are Q lines, each containing the integers i and v (1 ≤ i ≤ N, 0 ≤ v ≤ 9), meaning that on day i, the discount is now on color v.

Note that both a_i and v are very small.

Output

First, print the number of hair-dyeing plans that can be created from the original schedule, modulo 2^64.

Then, after each update, print the number of plans that can be created modulo 2^64.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
13Q=0, N ≤ 15
27Q=0, N ≤ 1000
38Q=0
415Q ≤ 6000
530a_i, v ≤ 1
620a_i, v ≤ 3
77a_i, v ≤ 6
810No additional constraints.

Explanation of Sample 1

There are 4 plans: either the friend can choose not to dye their hair at all or dye their hair exactly once.

Explanation of Sample 2

The 7 plans are:

  • []
  • [0]
  • [1]
  • [0 1]
  • [0]
  • [1 0]
  • [0 1 0]

Note that plans that contain only the color 0 are counted twice since dyeing hair on different days counts as different plans, even if the color is the same.

예제

예제 1

입력
3 0
0 0 0
출력
4

예제 2

입력
3 0
0 1 0
출력
7

예제 3

입력
4 2
0 1 2 0
1 1
4 1
출력
15
12
10

출처 표기

출처: Programmeringsolympiaden 2025년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.