Choose items
Practice
5 (9 votes)
Algorithms
Fast fourier transform
Hard
Problem
52% Success 680 Attempts 50 Points 8s Time Limit 256MB Memory 1024 KB Max Code

There are $$N$$ different types of items. The $$i^{th}$$ item has $$c_i$$ distinct copies. In this problem, you are going to deal with $$Q$$ queries. The $$i^{th}$$ query is represented by three integers - $$l_i, r_i, k_i$$. For every query, you need to find the number of ways for choosing $$k_i$$ items of different types, and their types must be within the interval $$[l_i, r_i]$$ (inclusive). Since this number might be huge, you are only asked to print its remainder modulo $$998244353$$.

Note that you can't choose two items of the same type $$i$$, i.e., if you want to choose an item of type $$i$$, you can do this in $$c_i$$ ways.

$$\textbf{Input}$$

The first line contains two integers - $$N$$ and $$Q$$ $$(1 \le N,Q \le 2^{14})$$.

The next line contains $$N$$ integers - $$c_1, c_2, \dots, c_N (1 \le c_i \le 10^8)$$.

The next $$Q$$ lines contain three integers - $$a_i, b_i, k_i$$ $$(0 \le a_i, b_i < N, 1 \le l_i \le r_i \le N, 1 \le k_i \le r_i - l_i + 1)$$. If $$last$$ is the answer for $$(i - 1)^{th}$$ (at the beginning $$last = 0$$) query then:

$$1. l_i = ((a_i + last) \mod N) + 1$$

$$2. r_i = ((b_i + last) \mod N) + 1$$

For $$25$$ points you can consider that $$N,Q \le 1024$$.

For another $$25$$ points you can consider that $$k_i \le 20$$.

For another $$25$$ points you can consider that $$k_i \le 256$$.

$$\textbf{Output}$$

Output $$Q$$ lines, the $$i^{th}$$ line constains the answer for the $$i^{th}$$ query in chronological order.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
4 votes
Tags:
AlgorithmsCombinatoricsFast Fourier transformHard
Points:50
8 votes
Tags:
AlgorithmsBinomial CoefficientsEulerian numberFast Fourier transformGenerating FunctionsHardStirling Numbers
Points:50
2 votes
Tags:
AlgorithmsApprovedCombinatoricsFast Fourier transformHardgenerating-functions