#3058. 「HNOI2019」白兔之舞

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一张顶点数为 (L+1)\times n 的有向图。这张图的每个顶点由一个二元组 (u,v) 表示 (0\le u\le L,1\le v\le n) 。这张图不是简单图,对于任意两个顶点 (u_1,v_1),(u_2,v_2) ,如果 u_1<u_2 ,则从 (u_1,v_1) (u_2,v_2) 一共有 w(v_1,v_2) 条不同的边,如果 u_1\ge u_2 则没有边。

白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点 (0,x)

白兔将会跳若干步。每一步,白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞(也可以没有跳就直接结束)。当到达第一维为 L 的顶点就不得不停止,因为该顶点没有出边。

假设白兔停止时,跳了 m 步,白兔会把这只舞曲给记录下来成为一个序列。序列的第 i 个元素为它第 i 步经过的边。

问题来了:给定正整数 k y\ (1\le y\le n) ,对于每个 t\ (0\le t<k) ,求有多少种舞曲(假设其长度为 m )满足 m \bmod k=t ,且白兔最后停在了坐标第二维为 y 的顶点?

两支舞曲不同定义为它们的长度( m )不同或者存在某一步它们所走的边不同。

输出的结果对 p 取模。

输入格式

第一行六个用空格隔开的整数 n,k,L,x,y,p

接下来 n 行,每行有 n 个用空格隔开的整数,第 i 行的第 j 个数表示 w(i,j)

输出格式

依次输出 k 行,每行一个数表示答案对 p 取模的结果。

样例

样例输入 1

2 2 3 1 1 998244353
2 1
1 0

样例输出 1

16
18

样例说明 1

t=0

  1. 路径长度为 0 ,方案数为 1
  2. 路径长度为 2 ,一共有六类路径:
    • (0,1)\to (1,1)\to (2,1) 该路径有 w(1,1)\times w(1,1)=4 条;
    • (0,1)\to (1,1)\to (3,1) 该路径有 w(1,1)\times w(1,1)=4 条;
    • (0,1)\to (2,1)\to (3,1) 该路径有 w(1,1)\times w(1,1)=4 条;
    • (0,1)\to (1,2)\to (2,1) 该路径有 w(1,2)\times w(2,1)=1 条;
    • (0,1)\to (1,2)\to (3,1) 该路径有 w(1,2)\times w(2,1)=1 条;
    • (0,1)\to (2,2)\to (3,1) 该路径有 w(1,2)\times w(2,1)=1 条;

答案就为 1+4+4+4+1+1+1=16

t=1

  1. 路径长度为 1 ,一共有三类路径:
    • (0,1)\to (1,1) 该路径有 w(1,1)=2 条;
    • (0,1)\to (2,1) 该路径有 w(1,1)=2 条;
    • (0,1)\to (3,1) 该路径有 w(1,1)=2 条;
  2. 路径长度为 3 ,一共有三类路径:
    • (0,1)\to (1,1)\to (2,1)\to (3,1) 该路径有 w(1,1)\times w(1,1)\times w(1,1)=8 条;
    • (0,1)\to (1,1)\to (2,2)\to (3,1) 该路径有 w(1,1)\times w(1,2)\times w(2,1)=2 条;
    • (0,1)\to (1,2)\to (2,1)\to (3,1) 该路径有 w(1,2)\times w(2,1)\times w(1,1)=2 条;

答案就为 2+2+2+8+2+2=18

样例输入 2

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

样例输出 2

506551216
528858062
469849094
818871911

数据范围与提示

对于全部数据, 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

对于每组测试点,特殊限制如下:

  • 测试点 1,2 L\le 10^5
  • 测试点 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