any solution/idea for this hard problem?

Revision en4, by tynker, 2023-08-27 05:32:54

you have $$$n$$$ $$$(1 \leq n \leq 7000)$$$ days and $$$m$$$ $$$(1 \leq m \leq 10^{18})$$$ songs labeled from 0 to $$$m-1$$$.

you're given two parameters $$$k$$$ and $$$p$$$. $$$(0 < k \le m)$$$ and $$$(1 \leq p \leq 4)$$$.

on each day $$$i$$$ you're given 3 parameters $$$x_i$$$ $$$a_i$$$ and $$$b_i$$$. meaning $$$x_i$$$ songs will be played starting from $$$b_i$$$-th song, and stepping by $$$k$$$. So songs with indexes $$$b_i, b_i + k (mod \; m), ..., b_i + (x_i - 1) * k (mod \; m)$$$ will be played. Each one of them will be played $$$a_i$$$ times.

you need to select $$$p$$$ different songs with non-adjacent labels. The value of each selection is defined by multiplying the number of times each of the $$$p$$$ songs is played.

Compute the sum of the values for all possible selections, modulo $$$10^9 + 7$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English tynker 2023-08-27 05:33:26 4 Tiny change: '. $(0 < k \le m)$ and $' -> '. $(0 < k < m)$ and $'
en4 English tynker 2023-08-27 05:32:54 4 Tiny change: ' $p$. $(0 \le k \le m)$' -> ' $p$. $(0 < k \le m)$'
en3 English tynker 2023-08-27 04:35:56 6 Tiny change: 'different **with no' -> 'different songs **with no'
en2 English tynker 2023-08-27 04:31:11 311 Tiny change: 'fferent \textbf{with ' -> 'fferent \txtbf{with ' (published)
en1 English tynker 2023-08-27 04:24:35 476 Initial revision (saved to drafts)