시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 21 | 14 | 10 | 83.333% |
As the mayor of the RUN town, you are planning to build a new village. The village consists of houses and roads connecting two different houses. Roads are organized in a way such that no two pairs of roads connect the same pair of houses. In other words, the village can be treated as a simple graph where each house corresponds to vertices, and each road corresponds to edges. Note that the village may be disconnected.
You want your village to be as simple as possible. Therefore, for any distinct houses $i$ and $j$, there should be at most $K$ simple paths from house $i$ to house $j$.
Let $N$ be the number of houses. The score of the village is $\prod_{1\le i<j\le N}A_{f(i,j)}$, where $f(i,j)$ is the number of simple paths from house $i$ to house $j$.
While the number of houses is not determined yet, you know that it will be an integer between $2$ and $M$. You should calculate the sum of the scores for all possible villages with $N$ houses for each $N$ from $2$ to $M$.
Since the answers can be large, output them modulo $998\, 244\, 353$.
The first line contains an two space-separated integers $M$ and $K$.
The second line contains $K+1$ space-separated integers $A_0,\dots ,A_K$.
For each $N$ from $2$ to $M$, output the sum of the scores for all possible villages with $N$ houses, modulo $998\, 244\, 353$. The answers should be separated by a space. $998\, 244\, 353=119\times 2^{23}+1$ is a prime number.
4 0 2
2 8 64
5 1 3 4
7 327 96721 169832849
6 2 5 6 7
11 1566 3000672 306031599 466869291
7 3 8 9 10 11
17 5427 31856976 326774674 449014006 997476587
University > KAIST > 2022 KAIST 12th ICPC Mock Competition L번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 4: KAIST+KOI Contest, Grand Prix of Korea L번