#1915. 星辰
星辰
星辰
题目描述
标题: 星辰 - Problem - QOJ.ac
#10350. 星辰
The problem was used in the following contests:
小 Y 是一个富有想象力的女孩子。
一天夜里,小 Y 望着满天的星辰,开始用自己之前学到的天文知识,逐个辨认星座。不过这次,她希望在前人的基础上添加些自己的创意,从而得到属于自己的图案。
天空中共有 n 颗星星。小 Y 通过翻阅古今中外的各种典籍,得到了 m 段资料。其中,第 i 段资料说星星 ai 和星星 bi 之间应该有一条连线。对于每段资料,小 Y 还根据它的年代、出处等信息,给了这条连线一个权值 ci。
小 Y 想从这 m 段资料中选出一些,根据其中的信息将星星连接起来,作为自己的图案。
小 Y 希望这样得到的图案中没有重边,也就是说任意两颗星星之间至多有一条边。并且这个图案应该是连通的。
除此之外,由于今年是 2017 年,小 Y 希望她选出边的权值和对 p=17 取模的结果为某个特定的数。于是小 Y 想知道,对于 0≤k<p 中的每一个 k,满足图案连通,无重边并且边权和对 p 取模的结果为 k 的方案数是多少?
由于答案可能很大,你只需要告诉小 Y 答案对 998244353 取模的结果。
输入格式
从标准输入读入数据。
第一行有两个整数 n,m,含义如题述。
接下来 m 行,每行三个整数 ai,bi,ci,表示有一条连接 ai 和 bi 的,权值为 ci 的边。
输出格式
输出到标准输出。
输出共 p 行,每行一个整数,第 i 表示边权和模 p 为 i−1 的方案数对 998244353 取模的结果。
样例数据
样例输入
4 8
1 2 0
1 2 1
2 3 0
2 3 1
3 4 0
3 4 1
1 4 0
1 4 2
样例输出
5
12
13
11
6
1
0
0
0
0
0
0
0
0
0
0
0
子任务
每个测试点的数据规模及特点如下表所示。
测试点nm其他约定1≤17≤20无2≤253≤304≤105权值均为 056≤14≤50权值均为 178≤1591011≤13≤105无12≤141314≤151516≤1617181920≤172122232425
对于 100% 的数据,保证 1≤n≤17,1≤m≤105,0≤ci<p=17。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 8
1 2 0
1 2 1
2 3 0
2 3 1
3 4 0
3 4 1
1 4 0
1 4 2
5
12
13
11
6
1
0
0
0
0
0
0
0
0
0
0
0