BLSUMSEQ - Sum of subsequences

Cho số nguyên dương n và dãy số a1...an. Có q truy vấn thuộc hai dạng :

- Dạng 0 l r k : yêu cầu đưa ra số nguyên dương nhỏ thứ k không thể phân tích được thành tổng của một số các số trong dãy al…a.

- Dạng 1 l r x : yêu cầu đưa ra số cách phân tích x thành tổng của một số các số trong dãy al…a(mod 232).

Yêu cầu : cho trước số n và dãy a1…a­n và q truy vấn thuộc hai dạng trên. Hãy lập trình trả lời các truy vấn đó.

Input :

   - Dòng 1 : hai số n và q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10000)

- Dòng 2 : gồm n số mô tả dãy a1…an (0 ≤ ai ≤ 100)

- q dòng còn lại, mỗi dòng gồm 4 số, có dạng 0 l r k hoặc 1 l r x mô tả một truy vấn (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 109, 0 ≤ x ≤ 109)

Output :

  - q dòng, mỗi dòng là trả lời cho một truy vấn theo đúng thứ tự được đưa ra

Ví dụ :

Input :

5 3

1 0 2 4 1

0 2 3 2
1 1 4 0
1 2 5 3

0 2 3 2

1 1 4 0

1 2 5 3

Output :

3

1

2


Được gửi lên bởi:Kata
Ngày:2014-03-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Own problem

hide comments
2014-10-09 12:51:30 Mew.
Cho mình hỏi với truy vấn 1, 1 số có thể được sử dụng nhiều lần hay không ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.