BLSUMSEQ - Sum of subsequences

no tags 

Given an positive integer n and a sequence a1 ... an. 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 al ... ar.
  • Format 1 l r x: you need to output the numbers of ways to partition x into a sum of a subseqence of al ... ar (or the numbers of subsequence that sum of all its elements equal to x) (modulo 232).

Input

  • First line: two positive n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10000)
  • Second line: n positive a1…an­ (0 ≤ ai ≤ 100)
  • Next q lines: each line denotes a query with one of two format listed above (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 109, 0 ≤ x ≤ 109)

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

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

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