Description
初始有 \(n\) 个数 \(a_i\)，以及若干条有向边 \((u_i,v_i)\)，保证 \(u_i<v_i\)。
一轮操作会形如下面两个过程：
- 首先 \(\forall i,a_i:= \max(a_i,ia_i)\)。
- 然后 \(\forall i,a'_i:= a_i+\sum\limits_{(i,j)\in E}\max(a_j,0)\)，最后 \(\forall i,a_i:= a'_i\)。
\(q\) 次询问或修改，询问形如 \((k,l,r)\)，你需要回答进行从初始状态操作 \(k\) 轮后的 \(\sum\limits_{i=l}^ra_i\)。修改形如 \((i,x)\)，把初始的 \(a_i\) 加上 \(x\)。
\(1\le n\le 300,|a_i|\le i\)。
\(1\le q\le 2\times 10^5,1\le k,x\le 10^3\)。
Solution
注意到如果 \(i\) 可以复制 \(j\)，且 \(j\) 在 \(d_j\) 天后 \(a_j>0\)，因为 \(i<j,a_i\ge -i\)，所以 \(a_i\) 在 \(d_j+1\) 天后也可以 \(>0\)。所以可以 \(O(n^2)\) 计算出 \(d_i\)。
由于修改 \(x>0\)，所以每个初始的 \(a_i\) 至多只会有一次从 \(\le 0\) 到 \(>0\) 的跨越，所以 \(d_i\) 只会更改 \(O(n)\) 次。所以可以 \(O(n^3)\) 维护出开始和每次修改后的 \(d_i\)。
对于一次询问，考虑所有点对询问的贡献，设 \(A_{i,j}=j[(i,j)\in E\vee i=j]\)，\(e_i\) 为长度为 \(n\) 的列向量且 \(e_{i,j}=[i=j]\)，即 \([e_1,e_2,\cdots,e_n]=I\)。
那么答案就是：
\[\left(\sum\limits_{i=l}^re_i^T\right)\left(\sum\limits_{d_i\le k}A^{k-d_i}e_ia_i\right)+\sum\limits_{i=l}^r[d_i>k]a_i \]右边那个是好求的，每次询问 \(O(n)\) 扫一遍 \([l,r]\) 即可。
左边也是可以求的，但是 \(A\) 太大了，而且分离出右边列向量的 \([l,r]\) 之间的数比较困难，于是进一步化简。
由于 \(A\) 为上三角矩阵，所以其特征多项式为 \(f(\lambda)=\prod\limits_{i=1}^n(\lambda-A_{i,i})\)。又由于 \(\forall i,A_{i,i}=i\)，所以 \(A\) 有 \(n\) 个特征值为 \(1,2,\cdots,n\)。考虑求出每个特征值 \(i\) 的特征向量 \(v_i\)。
由于 \(Av_i=iv_i\)，所以有 \(A\times [v_1,v_2,\cdots,v_n]=[v_1,2v_2,\cdots ,nv_n]\)。设 \(v_{i,i}=1\)，那么根据 \((A-iI)v_i=0\) 可以解方程求出所有的 \(v_i\)。
不难发现 \(V=[v_1,v_2,\cdots,v_n]\) 为上三角矩阵，所以 \(v_i\) 线性无关，所以可以将 \(e_i\) 分解为 \(e_i=\sum\limits_{j=1}^nC_{i,j}v_{j}\) 的形式。那么 \(VC^T=I\)，直接求逆即可得到 \(C\) 矩阵。
带回原式：
\[\begin{aligned}f(k,l,r)&=\left(\sum\limits_{i=l}^re_i^T\right)\left(\sum\limits_{d_i\le k}A^{k-d_i}e_ia_i\right)\\&=\left(\sum\limits_{i=l}^re_i^T\right)\left(\sum\limits_{d_i\le k}A^{k-d_i}\sum\limits_{j=1}^nC_{i,j}v_j\cdot a_i\right)\\&=\left(\sum\limits_{i=l}^re_i^T\right)\left(\sum\limits_{d_i\le k}a_i\sum\limits_{j=1}^nj^{k-d_i}v_jC_{i,j}\right)\quad\quad(Av_i=iv_i)\end{aligned} \]这样的话右边列向量 \([l,r]\) 的值就可以分离了：
\[\begin{aligned}f(k,l,r)&=\sum\limits_{d_i\le k}a_i\sum\limits_{j=1}^nj^{k-d_i}C_{i,j}\sum\limits_{p=l}^rv_{j,p}\\&=\sum\limits_{j=1}^nj^k\left(\sum\limits_{p=l}^rv_{j,p}\right)\sum\limits_{d_i\le k}j^{-d_i}a_iC_{i,j}\end{aligned} \]于是对于每个 \(j\) 开一个树状数组，维护每个 \(1\le k\le n\) 的 \(t_{j,k}=\sum\limits_{d_i\le k}j^{-d_i}a_iC_{i,j}\)，每次询问和修改的时候枚举 \(j\)，修改相当于区间操作，查询相当于单点查询，使用树状数组单次复杂度为 \(O(n\log n)\)，这部分复杂度为 \(O(qn\log n)\)。
每次重新求 \(d_i\) 时重构一次树状数组即可，每次复杂度为 \(O(n^2)\) 或 \(O(n^2\log n)\)。于是总复杂度为 \(O(n^3+qn\log n)\) 或 \(O(n^3\log n+qn\log n)\)。
// Problem: Tasty Dishes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1540E
// Memory Limit: 62 MB
// Time Limit: 10000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define eb emplace_back
#define pb pop_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define pc putchar
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int N = 350;
const int K = 1e3 + 100;
const int P = 1e9 + 7;
int n, q, L, a[N], d[N], pw[N][K], ipw[N][K];
int A[N][N], V[N][N], C[N][N], T[N][N << 1], B[N][N];
vector<int> g[N];
struct BIT {
int t[N];
int lb(int x) { return x & -x; }
void clr() { for (int i = 1; i <= n + 1; i++) t[i] = 0; }
void upd(int x, int y) { for (int i = x; i <= n + 1; i += lb(i)) (t[i] += y) %= P; }
int qry(int x) { int res = 0; for (int i = x; i; i -= lb(i)) (res += t[i]) %= P; return res; }
void add(int l, int x) { l++, upd(l, x); }
int qlr(int x) { return x = min(x + 1, n + 1), qry(x); }
} b[N];
int qpow(int p, int q) {
int res = 1;
for (; q; q >>= 1, p = 1ll * p * p % P)
if (q & 1) res = 1ll * res * p % P;
return res;
}
void init() {
for (int i = 1; i <= n; i++) A[i][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++) T[j][k] = A[j][k];
for (int j = 1; j <= n; j++) (T[j][j] += P - i) %= P;
V[i][i] = 1;
for (int j = i - 1; j; j--) {
int tp = 0;
for (int k = j + 1; k <= i; k++)
(tp += P - 1ll * V[k][i] * T[j][k] % P) %= P;
V[j][i] = 1ll * tp * qpow(T[j][j], P - 2) % P;
}
}
memset(T, 0, sizeof(T));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
T[i][j] = V[i][j];
for (int i = 1; i <= n; i++) T[i][i + n] = 1;
for (int i = 1; i <= n; i++) {
int p = i;
for (int j = i + 1; j <= n; j++)
if (T[j][i]) { p = j; break; }
swap(T[i], T[p]);
int iv = qpow(T[i][i], P - 2);
for (int j = 1; j <= n; j++) {
if (i == j) continue;
int tp = 1ll * T[j][i] * iv % P;
for (int k = i; k <= (n << 1); k++)
(T[j][k] += P - 1ll * tp * T[i][k] % P) %= P;
}
for (int j = 1; j <= (n << 1); j++) T[i][j] = 1ll * T[i][j] * iv % P;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
C[j][i] = T[i][j + n];
memset(T, 0, sizeof(T));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
(V[i][j] += V[i - 1][j]) %= P;
}
void getd() {
for (int i = 1; i <= n; i++)
if (a[i] > 0) d[i] = 0;
else d[i] = 2e9;
for (int i = n; i; i--)
for (int j : g[i]) d[i] = min(d[i], d[j] + 1);
for (int j = 1; j <= n; j++) {
b[j].clr();
for (int i = 1; i <= n; i++)
if (d[i] <= n) b[j].add(d[i], 1ll * (P + a[i]) % P * C[i][j] % P * ipw[j][d[i]] % P);
}
}
void solve() {
n = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
for (int i = 1; i <= n; i++) {
int iv = qpow(i, P - 2);
pw[i][0] = ipw[i][0] = 1;
for (int j = 1; j <= 1000; j++)
pw[i][j] = 1ll * pw[i][j - 1] * i % P,
ipw[i][j] = 1ll * ipw[i][j - 1] * iv % P;
}
for (int i = 1, x, y; i <= n; i++) {
x = rd();
for (int j = 1; j <= x; j++)
y = rd(), g[i].eb(y), A[i][y] = y;
}
init(), getd();
q = rd();
while (q--) {
int op, l, r, k, x, y;
op = rd();
if (op == 1) {
k = rd(), l = rd(), r = rd();
int res = 0;
for (int j = 1; j <= n; j++)
(res += 1ll * (V[r][j] - V[l - 1][j] + P) % P * pw[j][k] % P * b[j].qlr(k) % P) %= P;
for (int i = l; i <= r; i++)
if (d[i] > k) (res += (P + a[i]) % P) %= P;
wr(res), pc('\n');
} else {
x = rd(), y = rd();
a[x] += y;
if (a[x] > 0 && a[x] - y <= 0) getd();
else if (d[x] <= n) {
for (int j = 1; j <= n; j++)
if (d[x] <= n) b[j].add(d[x], 1ll * y * C[x][j] % P * ipw[j][d[x]] % P);
}
}
}
}
bool Med;
int main() {
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int _ = 1;
// cin >> _;
while (_--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}