P5293 [HNOI2019] 白兔之舞

HNOI2019 day2t2

有一张顶点数为 $(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

无

无

### 样例解释 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$。 ### 数据范围 对于全部数据，$p$ 为一个质数，$10^8