『JROI-4』傀影与猩红孤钻

## 我们在题目描述的最下方提供了形式化题意，若您不想阅读整活部分可以直接跳到题目描述的最下方。 神在猩红剧团的探索中取回了自己一部分的力量，不多，但够用。 神见到了傀影。准备使用辉煌裂片对他进行审判。 但是傀影躲进了一个被分成 $d$ 层的 DAG 中。 具体地，DAG 上第 $i$ 层的节点只会连向第 $i+1$ 层的节点。 “那就陪你继续玩玩吧。”神心想。 神决定了一种审判的方式。 具体地，神最开始有一些辉煌裂片。神认为，多项式具有强大的力量，所以辉煌裂片就是多项式。~~我才不告诉你是我懒得编题面。~~ 神有三种对辉煌裂片的操作： 1. “无度” 可以让辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F^2(x)$。 2. “文明的存续” 可以让“无度”后的辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F(x^2)$。 3. “夜骇” 可以让两个辉煌裂片进行融合，变得更加强大。具体地，如果对 $F(x)$ 和 $G(x)$ 进行这个操作会返回一个多项式为 $F(x)+G(x)$。 神决定这样对傀影进行审判： 在第一层的节点放置辉煌裂片。 当辉煌裂片进入一个节点前，对自身进行“无度”。 当两个辉煌裂片相遇，对这两个辉煌裂片进行“夜骇”，只会留下一个辉煌裂片为这两个辉煌裂片进行“夜骇”的结果。 辉煌裂片只会在连接该节点的所有边都有辉煌裂片通过后，才会离开该节点。当辉煌裂片离开一个节点时，辉煌裂片会对进行“文明的存续”，然后分裂成若干个和原辉煌裂片相同的辉煌裂片，留下一个辉煌裂片在该节点。然后，每条边都将通过恰好一个辉煌裂片。 若傀影在节点 $u$，而神有一个审判指数（execution points，EXP）$k$，该节点留下的辉煌裂片为 $F_u(x)$，那么傀影将会受到 $F_u(k)$ 伏特的电流。 现在神有一些提问。每个提问类似于，若傀影藏在节点 $u$，且审判指数为 $k$，那么傀影将会受到多少伏特的电流？ 神是怜悯的。答案可能过大，他只要求你输出答案对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。 ### 形式化题意 给你一张分为 $d$ 层的 DAG，每个节点都有一个多项式 $F_u(x)$。**可能会有重边。** 这个 DAG 上第 $i$ 层的节点只会向第 $i+1$ 层的节点连边。 若 $S_u$ 包含所有连向点 $u$ 的节点，那么满足 $F_u(x)=\sum_{v \in S_u}F_v^2(x^2)$。 给出第一层节点的多项式，每次询问会给你 $u,k$，然后询问 $F_u(k)$ 对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。 **请注意，重边算作一条边。** ## Input 第一行一个整数 $d$，表示 DAG 的层数。 接下来一行会有 $d$ 个整数，第 $i$ 个数 $n_i$ 表示第 $i$ 层有 $n_i$ 个节点。 接下来 $n_1$ 行，第 $i$ 行有若干个数表示第一层的 $i$ 号节点的多项式。 具体地，每行第一个数 $p$ 表示多项式的最高次，接下来 $p+1$ 个数表示这个多项式的系数，若其中第 $i$ 个数（不包括 $p$）为 $f_{i-1}$，那么该多项式为 $\sum_{i=0}^pf_ix^i$。 接下来的输入分为 $d$ 段。第 $i$ 段的开头有两个数 $m,q$ 表示第 $i$ 层有 $m$ 条边，以及神在第 $i$ 层的点中有 $q$ 个询问。 接下来 $m$ 行，每行两个数 $u,v$ 表示第 $i$ 层编号为 $u$ 的点连接了第 $i+1$ 层编号为 $v$ 的点。 接下来 $q$ 行每行两个整数 $u,k$ 表示神询问当傀影在第 $i$ 层编号为 $u$ 的节点上时，且审判指数为 $k$ 时，傀影受到电流的伏特对 $7340033$ 取模后的结果。 ## Output 由于输出可能过大，你需要对输出加密。 具体地，对于第 $k$ 层的询问，若第 $i$ 个询问的答案为 $a_i$，你只需要输出 $(k \times \bigoplus_{i=1}^q(q-i) \times a_i)\bmod 2^{32}$ 即可。 请注意，输出一共 $d$ 行，每行一个数字。 [samples] ## Background “水……” 在沙尘暴中跋涉许久，又整整一天没有饮水，身体已经逐渐支撑不住了。 凯尔希没有拿水瓶，而是冷冷地说了一句“再撑一会”，随后就自顾自继续向前赶路。 我们已经在沙暴里跋涉了多久？三个小时？还是五个小时？黄沙不停往衣物里涌，狂风则不停将沙尘甩在脸上，刮得眼睛都睁不开。但我们还不能停步，后面的萨卡兹雇佣兵还在紧追不舍，他们尽职尽责，即使是沙暴都阻挡不了他们的脚步。 至于水……或许早就喝完了吧。 听说沙漠里有在空水壶中灌沙来给人以希望的传统，可现在，沙子我已经喝够了，水，我只想喝口水，哪怕用身上所有的硬币去换，我也愿意。 只是在这荒野里，闪亮的金属毫无意义。 紧紧抱着银色的手提箱，我咬紧牙关继续迈步。 耳边都是凄厉的呼啸，像是亡者的哭号，又像是鬼魂的呼唤。索恩教授或许也在其中，呼唤着我的名字？ 但我听不太清了。 脑中满是这样的响声，已经多久了？三分钟？三小时？还是三年？ 沙尘遮蔽了天空，白天和黑夜已经毫无区别，时间似乎都已凝滞，只有在其中求生的人们，还在忍受着此间种种刑罚。 我只是想做研究，我只是想为科学进步奉献自己的力量，而不是像现在这样，倒在沙海里风干。 脑袋又酸又胀又痛，身体好像早就没了知觉，我是在行走吗，还是在看着这具名为艾利奥特的躯壳蠕动？ 不……思考也成为了一种奢求，现在徘徊在脑袋里的，只有一个指令：移动。 移动……移动……移动…… ……但沙海是无垠的。 “艾利奥特，张嘴。” 张嘴？ 我下意识地放松肌肉，让嘴唇和牙齿露出一条通往口腔的通道。 一串沾满沙土的果实落到了口中。 有些酸涩？有些甘甜？哦，是水，是水。 是水啊。 …… 不知从什么时候开始，耳边再也没有风声，大地回复了寂静，只有阳光，沙漠，和两个在沙丘间徒步的凡人。 …… 我望向远方，除了黄沙，还是黄沙。 一眼望不到尽头，就像散落满地又被浸湿的皮鞋踩上几脚的技术文件，再也归不拢，再也理不齐。 我忿忿地踢了一脚沙子，看着它们从沙丘尖端翻滚滑落，然后重新融到沙漠中，好似什么都没有发生过。 沙子，沙子。 我生平第一次开始痛恨沙子。 “走吧，很快就能获得补给了。” 凯尔希打断了我的思绪。 可，很快？能有多快？ 一些补给？又有多少呢？ 呵，凯尔希从来不向人许诺希望。 但至少…… 我似乎看见了一颗仙人掌。 ## Note - Subtask1（7pts）$1\leq d\leq 2$。 - Subtask2（20pts）$1\leq d\leq 10,\sum q=1$。 - Subtask3（13pts）$n_1=2$，且时间限制为 5s。 - Subtask4（60pts）无特殊限制。 - Subtack5（0pts）Hack 数据。 对于 $ 100\% $ 的数据，满足 $1\leq\sum n<5060$，$1\leq d\leq 10$，$\sum q\leq 1.5 \times 10^6$，$1\leq w,k<7340033$，$0 \leq p \leq 2$。 若第 $i$ 层有 $m_i$ 条边，对于 $i\neq d$ 保证有 $n_i<n_{i+1}\leq2\times n_i$ 和 $n_i\leq m_i\leq 3\times n_i$，且 $m_d=0,1 \leq n_1 \leq 5$。