#P14517. [2026年省队模拟联测]尝试了飞行

    ID: 13734 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000图论强连通分量动态规划前缀和拓扑排序树形DP组合数学

[2026年省队模拟联测]尝试了飞行

【题目描述】

给定一张nn个点mm条边的**.简.单.有.向.图**,保证每个点最多在一个简单环内。

给定kk,求有多少个**.有.序**路径对(P1,P2)(P_1,P_2)(不要求是简单路径)满足:

•每个点至少被两条路径中的一条覆盖。

•每个点被两条路径覆盖的次数和不超过kk。

答案对998244353998244353取模。

【输入格式】

第一行三个整数n,m,kn,m,k。

接下来m行,每行两个整数u,vu,v,表示存在一条uu连向vv的有向边。

【输出格式】

一行一个整数,表示答案。

【样例1输入】

5 5 1 
1 2 
2 3 
3 1 
2 4 
3 5 

【样例1输出】

6

【样例1解释】

合法的66种路径对分别是:

•(1→2→4;3→5),(3→5;1→2→4)(1→2→4;3→5),(3→5;1→2→4),

•(1→2→3→5;4),(4;1→2→3→5)(1→2→3→5;4),(4;1→2→3→5),

•(3→1→2→4;5),(5;3→1→2→4)(3→1→2→4;5),(5;3→1→2→4)。

【样例2输入】

3 2 2 
1 2 
2 3 

【样例2输出】

19 

【样例3输入】

3 3 2 
1 2 
2 3 
3 1 

【样例3输出】

105

【数据范围】

对于所有数据,2≤n≤2000,1≤m≤4000,0≤k<998244353,2≤n≤2000,1≤m≤4000,0≤k<998244353。

测试点编号 n≤n \le m≤m \le k≤k\le 特殊性质
11 55 1010 22 无无
22 200200 400400 11 AA
33 20002000 40004000 22
44 200200 400400 11 无无
55 20002000 40004000
6∼76 \sim 7 200200 400400 10910^9
8∼108 \sim 10 20002000 40004000

特殊性质A:图不存在环。