Tasty Dishes
Contest: Codeforces Round 728 (Div. 1)
Difficulty rating: 3500
Tags: math, matrices

Note that the memory limit is unusual.

There are $$$n$$$ chefs numbered $$$1, 2, \ldots, n$$$ that must prepare dishes for a king. Chef $$$i$$$ has skill $$$i$$$ and initially has a dish of tastiness $$$a_i$$$ where $$$|a_i| \leq i$$$. Each chef has a list of other chefs that he is allowed to copy from. To stop chefs from learning bad habits, the king makes sure that chef $$$i$$$ can only copy from chefs of larger skill.

There are a sequence of days that pass during which the chefs can work on their dish. During each day, there are two stages during which a chef can change the tastiness of their dish.

1. At the beginning of each day, each chef can choose to work (or not work) on their own dish, thereby multiplying the tastiness of their dish of their skill ($$$a_i := i \cdot a_i$$$) (or doing nothing).
2. After all chefs (who wanted) worked on their own dishes, each start observing the other chefs. In particular, for each chef $$$j$$$ on chef $$$i$$$'s list, chef $$$i$$$ can choose to copy (or not copy) $$$j$$$'s dish, thereby adding the tastiness of the $$$j$$$'s dish to $$$i$$$'s dish ($$$a_i := a_i + a_j$$$) (or doing nothing). It can be assumed that all copying occurs simultaneously. Namely, if chef $$$i$$$ chooses to copy from chef $$$j$$$ he will copy the tastiness of chef $$$j$$$'s dish at the end of stage $$$1$$$.

All chefs work to maximize the tastiness of their own dish in order to please the king.

Finally, you are given $$$q$$$ queries. Each query is one of two types.

1. $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ — find the sum of tastiness $$$a_l, a_{l+1}, \ldots, a_{r}$$$ after the $$$k$$$-th day. Because this value can be large, find it modulo $$$10^9 + 7$$$.
2. $$$2$$$ $$$i$$$ $$$x$$$ — the king adds $$$x$$$ tastiness to the $$$i$$$-th chef's dish before the $$$1$$$-st day begins ($$$a_i := a_i + x$$$). Note that, because the king wants to see tastier dishes, he only adds positive tastiness ($$$x > 0$$$).

Note that queries of type $$$1$$$ are independent of each all other queries. Specifically, each query of type $$$1$$$ is a scenario and does not change the initial tastiness $$$a_i$$$ of any dish for future queries. Note that queries of type $$$2$$$ are cumulative and only change the initial tastiness $$$a_i$$$ of a dish. See notes for an example of queries.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of chefs.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-i \le a_i \le i$$$).

The next $$$n$$$ lines each begin with a integer $$$c_i$$$ ($$$0 \le c_i < n$$$), denoting the number of chefs the $$$i$$$-th chef can copy from. This number is followed by $$$c_i$$$ distinct integers $$$d$$$ ($$$i < d \le n$$$), signifying that chef $$$i$$$ is allowed to copy from chef $$$d$$$ during stage $$$2$$$ of each day.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains a query of one of two types:

- $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 1000$$$);
- $$$2$$$ $$$i$$$ $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 1000$$$).

It is guaranteed that there is at least one query of the first type.

Output format:
For each query of the first type, print a single integer — the answer to the query.

Constraints:
Time limit: 10.0 s
Memory limit: 64.0 MB

Note:
Below is the set of chefs that each chef is allowed to copy from:

- $$$1$$$: $$$\{2, 3, 4, 5\}$$$
- $$$2$$$: $$$\{3\}$$$
- $$$3$$$: $$$\{4\}$$$
- $$$4$$$: $$$\{5\}$$$
- $$$5$$$: $$$\emptyset$$$ (no other chefs)

Following is a description of the sample.

For the first query of type $$$1$$$, the initial tastiness values are $$$[1, 0, -2, -2, 4]$$$.

The final result of the first day is shown below:

1. $$$[1, 0, -2, -2, 20]$$$ (chef $$$5$$$ works on his dish).
2. $$$[21, 0, -2, 18, 20]$$$ (chef $$$1$$$ and chef $$$4$$$ copy from chef $$$5$$$).

So, the answer for the $$$1$$$-st query is $$$21 + 0 - 2 + 18 + 20 = 57$$$.

For the $$$5$$$-th query ($$$3$$$-rd of type $$$1$$$). The initial tastiness values are now $$$[1, 0, 0, 1, 4]$$$.

Day 1

1. $$$[1, 0, 0, 4, 20]$$$ (chefs $$$4$$$ and $$$5$$$ work on their dishes).
2. $$$[25,0, 4, 24, 20]$$$ (chef $$$1$$$ copies from chefs $$$4$$$ and $$$5$$$, chef $$$3$$$ copies from chef $$$4$$$, chef $$$4$$$ copies from chef $$$5$$$).

Day 2

1. $$$[25, 0, 12, 96, 100]$$$ (all chefs but chef $$$2$$$ work on their dish).
2. $$$[233, 12, 108, 196, 100]$$$ (chef $$$1$$$ copies from chefs $$$3$$$, $$$4$$$ and $$$5$$$, chef $$$2$$$ from $$$3$$$, chef $$$3$$$ from $$$4$$$, chef $$$4$$$ from chef $$$5$$$).So, the answer for the $$$5$$$-th query is $$$12+108+196=316$$$.

It can be shown that, in each step we described, all chefs moved optimally.

Example input:
5
1 0 -2 -2 4
4 2 3 4 5
1 3
1 4
1 5
0
7
1 1 1 5
2 4 3
1 1 1 5
2 3 2
1 2 2 4
2 5 1
1 981 4 5

Example output:
57
71
316
278497818

Editorial:
All operations are conducted under a modulo, it can be proven that each operation we conduct is valid within the modulo.
Key Idea 1 It's optimal to perform each operation if the number being added/multiplied is strictly positive. Specifically, it's optimal to do $$$a_i := i\cdot a_i$$$ and $$$a_i := a_i+a+j$$$ iif $$$a_i > 0$$$ and $$$a_j > 0$$$ respectively.
Key Idea 2 A chef's dish $$$i$$$ becomes positive after the $$$d$$$'th day where $$$d$$$ is the closest distance of chef $$$i$$$ from a positive element. We call this value $$$d_i$$$ for the $$$i$$$'th chef. Initial observations, there are only $$$O(N^2)$$$ pairs of $$$(i, d_i)$$$ where $$$d_i$$$ is not infinite (never reaches positive value and thus never changes).
Key Idea 3 We refer to a vector of length $$$n$$$ with $$$n-1$$$ zeros and a single $$$1$$$ at the $$$i$$$'th index as $$$\vec{e}_i$$$. If we assume that all chefs are currently positive then every chef takes every opportunity copy and the transition matrix $$$T$$$ is well defined and obvious.
We can represent the final array at time $$$k$$$ as $$$a = T^k \sum_{d_i \leq k} T^{-d_i} \vec{e}_i a_i$$$ + $$$\sum_{d_i>k} \vec{e}_i a_i$$$. This immediately offers a $$$O(QN^2+N^4)$$$ potential solution with very good constant. Because $$$T$$$ is diagonal, its inverse can with respect to a vector $$$\vec{v}$$$ be calculated in $$$O(N^2)$$$. So, we can precalculate $$$T^-k \vec{e}_i$$$ for all valid numbers in $$$O(N^2)$$$. In fact, this ends up being $$$N^4/12$$$ total operations if optimized. We can then answer each query in $$$O(N^2)$$$ by simply iterating over each chef and finding it's contribution to the answer. Multiplying a matrix $$$O(N^2)$$$ will be explained later.
With some special hacks, it may even be possible to get this to pass.
Key Idea 4 An arbitrary matrix $$$T$$$ has eigenvalues $$$\lambda_i$$$ and their paired eigenvectors $$$\vec{v}_i$$$. Ignoring how we find eigenvectors and eigenvalues, the point of the two is that they are pairs such that $$$T \vec{v}_i = \vec{v}_i \lambda_i$$$. Notably, given a eigenvector and its respective eigenvalue, we can calculate $$$T^k \cdot \vec{v}_i$$$ in $$$O(N \log k)$$$.
In our case, the transition matrix $$$T$$$ is a diagonal matrix. A basic result in linear algebra is that the eigenvalues of a diagonal matrix is exactly the numbers on it's diagonal. In our case, this means that $$$\lambda_i = i$$$ for $$$1 \le i \le n$$$. Finding the eigenvectors is left as an exercise to the reader. We henceforth denote the eigenvector paired with the $$$i$$$'th eigenvalue as $$$\vec{v}_i$$$.
Key Idea 5 Decompose $$$\vec{e}_i$$$ into a linear combination of eigenvectors. This can be precalculated in $$$O(N^3)$$$. Let's denote another vector $$$\vec{c}_i$$$ as this linear combination i.e. $$$\vec{c}_i$$$ satisfies $$$\vec{e}_i = \sum \vec{v}_i \vec{c}_{i, j}$$$. In fact, this is almost all we need. Let's return to to $$$a = T^k \sum_{d_i \leq k} T^{-d_i} \vec{e}_i a_i$$$ (the second part can be trivially calculated). We can calculate almost "separately" for each eigenvector $$$j$$$. In fact, the contribution of the $$$j$$$'th eigenvector from the $$$i$$$'th chef after the $$$k$$$'th day is $$$\lambda_j^k c_{i, j} a_i \lambda_j^{-d_i}$$$. Let's store $$$c_{i,j}a_i \lambda_j^-{d_i}$$$ in a segment tree/BIT on $$$d_i$$$. We can extract in $$$O(N \log N)$$$ total or $$$O(\log N)$$$ for a single eigenvector then find the total contribution by multiplying by $$$\lambda_j^k$$$ and using prefix sums on the eigenvector to extract the relevant range $$$[l, r]$$$. We can also process $$$O(N log N)$$$ per update if $$$d_i$$$ stays constant trivially. This is more than enough to pass, but a further optimization is that the array $$$d$$$ only changes at most $$$O(N)$$$ time (whenever a new element becomes positive). So, we can simply rebuild our segment tree/BIT in $$$O(N)$$$ to reach $$$O(N^3)$$$ complexity.
Final complexity: $$$O(N^3 + QN\log N)$$$.
It's also worth noting that several nonoptimal solutions can pass. We attempted to cut off any solutions that explicitly use matrix multiplication. However, solutions with complexity such as $$$O(QN^2)$$$ can pass in 64 bit C++ if only additions are used. The only way we found to do only additions was by making the same eigenvector reduction, so we were not too worried. It seems impossible to fail such solutions while maintaining a reasonable TL.