SPOJ.com - Problem BLSUMSEQ

BLSUMSEQ - Sum of subsequences

no tags

Given an positive integer n and a sequence a₁ ... a_n. There are q queries. Each query has one of two formats:

Format 0 l r k: you need to output the k-th smallest positive integer that can’t be partition into a sum of any subsequence of a_l ... a_r.
Format 1 l r x: you need to output the numbers of ways to partition x into a sum of a subseqence of a_l ... a_r (or the numbers of subsequence that sum of all its elements equal to x) (modulo 2³²).

Input

First line: two positive n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10000)
Second line: n positive a₁…a_n(0 ≤ a_i ≤ 100)
Next q lines: each line denotes a query with one of two format listed above (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 10⁹, 0 ≤ x ≤ 10⁹)

Output

q lines: the i-th line is the answer of i-th query.

Sample

Input:
5 3
1 0 2 4 1
0 2 3 2
1 1 4 0
1 2 5 3

Output:
3
1
2

Submit solution!

hide comments



	Jacob Plachta: 2014-04-11 23:54:22 I should note that the current data can be used without changes if, for Format 1 queries, the problem statement simply asks for the number of ways modulo 2^32. Kata: Yes, you're right. Sorry about my mistakes. I have edited the problem. Edit: That's okay, but the output for Format 1 should be modulo 2^32, not the output for Format 0. Last edit: 2014-03-22 18:18:21
	Jacob Plachta: 2014-04-11 23:54:22 That's just fantastic... After wasting a very large amount of time, I discovered that the outputs do still overflow. If I use long longs, I find that the outputs exceed 2^32, and I get WA if I output them correctly - but if I use unsigned ints and pay no attention to overflow, I get AC. I expected that this wouldn't be the case after it was already pointed out that outputs were overflowing, and it was promised that they were fixed, but apparently not.
	Min_25: 2014-04-11 23:54:22 Does "k-th smallest positive integer" (in Format 0 l r k) mean "k-th smallest nonnegative integer" ? (... If so, current test cases are not correct because I didn't assume that in ID:11284420.) Kata: No. It's exactly "k-th smallest positive integer". Last edit: 2014-03-22 08:41:54
	Jacob Plachta: 2014-04-11 23:54:22 I assume that subsequences in this problem don't have to be contiguous, but they need to be non-empty? For example, is this input/output correct? Input: 3 2 0 1 0 1 1 3 0 1 1 3 1 Output: 3 4 Kata: Yes. They need to be non-empty. The sample input/output showed this (answer of 2nd query was 1). And your above input/output is correct. Last edit: 2014-03-22 05:17:23
	Min_25: 2014-04-11 23:54:22 I think my code(ID: 11284271) is correct. Could you please check that the test-case is correct ? Edit1: Sorry, my code(ID: 11284271) is not correct when the number of partition is divisible by 2^32. Edit2: Thank you for checking testcases. However, it seems that there are still some invalid (the answer >= 2^31) cases. (checked by ID: 11293800) Could you replace them with correct (< 2^31) cases ? Kata: Increase limit seems a better idea. I have updated it. Last edit: 2014-03-22 01:29:19

Submit solution!

Added by:	Kata
Date:	2014-03-12
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem