[HNOI2019]白兔之舞

题目背景

HNOI2019 day2t2

题目描述

有一张顶点数为 $(L+1)\times n$ 的有向图。这张图的每个顶点由一个二元组$(u,v)$表示$(0\le u\le L,1\le v\le n)$。 这张图不是简单图,对于任意两个顶点$(u1,v1)(u2,v2)$,如果 $u1<u2$,则从$(u1,v1)$到$(u2,v2)$一共有 $w[v1][v2]$条不同的边,如果 $u1\ge u2$ 则没有边。 白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点$(0,x)$。 白兔将会跳若干步。每一步,白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞(也可以没有跳就直接结束)。当到达第一维为 $L$ 的顶点就不得不停止,因为该顶点没有出边。 假设白兔停止时,跳了 $m$ 步,白兔会把这只舞曲给记录下来成为一个序列。序列的第 $i$ 个元素为它第 $i$ 步经过的边。 问题来了:给定正整数 $k$ 和 $y$($1\le y\le n$),对于每个 $t$($0\le t<k$),求有多少种舞曲(假设其长度为 $m$)满足$ m \mod k=t$,且白兔最后停在了坐标第二维为 $y$ 的顶点? 两支舞曲不同定义为它们的长度($m$)不同或者存在某一步它们所走的边不同。 输出的结果对 $p$ 取模。

输入输出格式

输入格式


输入文件名为 dance.in。 第一行五个用空格隔开的整数 $n,k,L,x,y,p$。 接下来 $n$ 行,每行有 $n$ 个用空格隔开的整数,第 $i$ 行的第 $j$ 个数表示 $w[i][j]$。

输出格式


输出文件名为 dance.out。 依次输出 $k$ 行,每行一个数表示答案对 $p$ 取模的结果。

输入输出样例

输入样例 #1

2 2 3 1 1 998244353
2 1
1 0

输出样例 #1

16
18

输入样例 #2

3 4 100 1 3 998244353
1 1 1
1 1 1
1 1 1

输出样例 #2

506551216
528858062
469849094
818871911

说明

【样例解释 1】 t=0: 1.路径长度为0,方案数为1。 2.路径长度为2,一共有六类路径 (0,1)->(1,1)->(2,1) 该路径有w[1][1]*w[1][1]=4条 (0,1)->(1,1)->(3,1) 该路径有w[1][1]*w[1][1]=4条 (0,1)->(2,1)->(3,1) 该路径有w[1][1]*w[1][1]=4条 (0,1)->(1,2)->(2,1) 该路径有w[1][2]*w[2][1]=1条 (0,1)->(1,2)->(3,1) 该路径有w[1][2]*w[2][1]=1条 (0,1)->(2,2)->(3,1) 该路径有w[1][2]*w[2][1]=1条 答案就为1+4+4+4+1+1+1=16 t=1: 1.路径长度为1,一共有3类路径 (0,1)->(1,1) 该路径有w[1][1]=2条 (0,1)->(2,1) 该路径有w[1][1]=2条 (0,1)->(3,1) 该路径有w[1][1]=2条 2.路径长度为3,一共有3类路径 (0,1)->(1,1)->(2,1)->(3,1) 该路径有w[1][1]*w[1][1]*w[1][1]=8条 (0,1)->(1,1)->(2,2)->(3,1) 该路径有w[1][1]*w[1][2]*w[2][1]=2条 (0,1)->(1,2)->(2,1)->(3,1) 该路径有w[1][2]*w[2][1]*w[1][1]=2条 答案就为2+2+2+8+2+2=18 【数据范围】 测试点1,2:$L<=100000$ 测试点3: $n=1,w[1][1]=1$,k的最大质因子为2 测试点4: $n=1,k$ 的最大质因子为2 测试点5: $n=1,w[1][1]=1$ 测试点6: $n=1$ 测试点7,8: $k$的最大质因子为$2$ 对于全部数据: p为一个质数,$10^8<p<2^{30}$ $1\le n\le 3$ $1\le x\le n$ $1\le y\le n$ $0\le w[i][j]<p$ $1\le k\le 65536$, $k$为$p-1$的约数 $1\le L\le 10^8$ 【编译命令】 对于c++语言: g++ -o dance dance.cpp –lm 对于c语言: gcc -o dance dance.c –lm 对于pascal语言: fpc dance.pas