Đếm tập con chẵn

View as PDF

Submit solution

Points: 400 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho dãy số ~a_1, a_2, …, a_n~ và ~q~ thao tác thuộc 1 trong 2 loại sau:

1 k b: gán ~a_k=b~

2 l r: Tính số lương tập con ~\{k_1, k_2, ..., k_m\}~ khác rỗng của tập ~\{l,l+1,…,r\}~ sao cho ~a_{k_1} + a_{k_2} + ... + a_{k_m}~ là số chẵn.

Yêu cầu: Với thao tác loại 2, hãy in ra số dư của kết quả khi chia cho ~10^9+7~.

Dữ liệu

  • Dòng đầu chứa 2 số nguyên ~n,q~.
  • Dòng tiếp theo chứa ~n~ số ~a_1,a_2,…,a_n (1\leq a_i \leq 10^9)~.

  • ~q~ dòng tiếp theo mỗi dòng chứa một trong hai loại thao tác :

    • 1 k b ~(1 \leq k \leq n; 1 \leq b \leq 10^9)~
    • 2 l r ~(1\leq l \leq r \leq n)~

Kết quả: Với mỗi thao tác loại 2, in ra số lượng tập con thỏa mãn ~(mod \ 10^9+7)~ trên một dòng.

Ví dụ

Input

5 6
2 4 6 8 10
2 1 3
2 4 4
2 4 5
1 4 7
2 4 4
2 4 5

Output

7
1
3
0
1

Giới hạn:

  • 20% số test có ~n,q \leq 20~.
  • 20% số test có ~n,q \leq 5000~.
  • 20% số test có ~n \leq 10^5, q \leq 100~.
  • 40% số test có ~n,q \leq 10^5~.

Be the first to comment

Comments

There are no comments at the moment.