#P5293. [HNOI2019] 白兔之舞

    ID: 4927 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学2019各省省选湖南容斥快速傅里叶变换 FFT

[HNOI2019] 白兔之舞

题目背景

HNOI2019 day2t2

题目描述

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

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

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

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

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

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

输出的结果对 pp 取模。

输入格式

输入文件名为 dance.in。

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

接下来 nn 行,每行有 nn 个用空格隔开的整数,第 ii 行的第 jj 个数表示 w[i][j]w[i][j]

输出格式

输出文件名为 dance.out。

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

2 2 3 1 1 998244353
2 1
1 0
16
18
3 4 100 1 3 998244353
1 1 1
1 1 1
1 1 1
506551216
528858062
469849094
818871911

提示

样例解释 1

t=0t=0

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

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

t=1t=1

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

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

数据范围

对于全部数据,pp 为一个质数,108<p<23010^8<p<2^{30}1n31\le n\le 31xn1\le x\le n1yn1\le y\le n0w(i,j)<p0\le w(i,j)<p1k655361\le k\le 65536kkp1p-1 的约数,1L1081\le L\le 10^8

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

  • 测试点 1,21,2L105L\le 10^5
  • 测试点 33n=1,w(1,1)=1n=1,w(1,1)=1kk 的最大质因子为 22
  • 测试点 44n=1n=1kk 的最大质因子为 22
  • 测试点 55n=1,w(1,1)=1n=1,w(1,1)=1
  • 测试点 66n=1n=1
  • 测试点 7,87,8kk 的最大质因子为 22