#P13781. [2024年山东第二轮集训]粉兔的原神(genshin)

    ID: 12982 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-Dijkstra有序集合二分查找支配关系补集转化

[2024年山东第二轮集训]粉兔的原神(genshin)

题目描述

众所周知,粉兔喜欢打原神。

提瓦特大陆是一个nn个点的有向图,标号从11到nn。提瓦特大陆四通八达,对于点ii,除了kik_i个点以外,ii向其它点都有一条边。边长均为tit_i。

小粉兔每天在提瓦特大陆游玩25小时,所以他可能会从每个点走到每个点。为了统计提瓦特大陆的情况,小粉兔想要知道

$$\sum_{i=1}^n\sum_{i=1}^n dist(i,j) \times B^{(i-1)n+j} \mod 1000000007$$

其中dist(i,j)dist(i,j)为图上ii到jj的最短距离。如果无法到达,则为154154154154154154。

输入格式

第一行输入两个数n,Bn,B。

接下来nn行,第ii行先输入两个数ti,kit_i, k_i,然后输入kik_i个互不相同的数ei,1,⋯ ,ei,kie_{i,1},\cdots,e_{i,k_i}(1≤ei,j≤n,ei,j≠i1\le e_{i,j}\le n, e_{i,j}\ne i)

输出格式

样例1

Input
3 2
1 0
1 2 1 3
1 1 2
Output
332332888
Hint

dist如下

Dist 1,* 2,* 3,*
*,1 0 154154154 1
*,2 1 0 2
*,3 154154154 0

答案为$154154154\times (2^4+2^6) + (2^2+2^3+2^7+2\times 2^8)$。

样例2

Input
6 154
1 1 4 
5 1 4
191981 0
9 2 3 2
6 1 2
154154 3 1 5 4
Output
926990349

数据范围

对于所有数据,有$1\le n\le 5\times 10^5, \sum k_i^2\le 10^7, 2\le B<1000000007, 0\le t_i\le 10^9$。

下表中留空表示无特殊限制。

Test# nn ∑ki2\sum k_i^2 其他
1-5 ≤154\le 154
6 =0=0
7-8 ki≤1k_i\le 1
9-10 ki≤2k_i\le 2
11-13 ti=1t_i=1
14-15 ≤50000\le 50000
16-20