#P6903. 枸杞

    ID: 6734 传统题 4000ms 256MiB 尝试: 9 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-矩阵乘法Newton 恒等式Cayley–Hamilton 降幂线性递推二项式定理卷积转化NTT阶乘逆元预处理一维前缀和克罗内克积

枸杞

题目描述

给定 TT 张无向图。每次询问选取编号在 [l,r][l,r] 内的图,一个位置由在所选的每张图中各取一个顶点组成。

一步游走时,每个坐标可以留在原顶点,或沿所在图的一条边移动。至少一个坐标必须移动。求游走步数为 11 到 kk、最后回到起点的方案总数,对 998244353998244353 取模。选择不同起点得到的方案分别计数。

输入格式

第一行一个正整数 TT,表示无向图数量。

接下来依次输入 TT 张图。第 ii 张图先输入一行 ni,min_i,m_i,分别表示点数和边数。随后 mim_i 行每行两个点编号,表示一条无向边。点从 11 到 nin_i 编号。

接下来一行一个正整数 QQ,表示询问数。

接下来 QQ 行,每行三个正整数 l,r,kl,r,k,表示对应询问。

输出格式

输出 QQ 行,每行一个整数,表示该询问的答案。

样例

2
3 3
1 2
2 3
1 3
3 2
1 2
2 3
3
1 1 4
2 2 4
1 2 2
30
12
54

第一问中,三角形的每个顶点作为起点时,长度 22、33、44 的闭合游走分别有 22、22、66 种,合计 3(2+2+6)=303(2+2+6)=30。

数据范围

1≤T≤201\le T\le20,1≤Q≤2×1051\le Q\le2\times10^5,1≤l≤r≤T1\le l\le r\le T,0≤mi≤ni(ni−1)/20\le m_i\le n_i(n_i-1)/2。

测试点 nin_i 上限 kk 上限 是否保证 l=rl=r
1–2 30 10410^4 是
3–7 10210^2 否
8–12 15 10310^3
13–20 30 10410^4

本站原评测配置为 4 秒、256 MB。

原 PDF 题面

By Anoxx