#1915. 星辰

    ID: 1915 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1971来源:qoj.ac数据:公开样例动态规划

星辰

星辰

题目描述

标题: 星辰 - Problem - QOJ.ac

#10350. 星辰

Statistics

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