P5293 [HNOI2019]白兔之舞

    • 96通过
    • 341提交
  • 题目提供者 「QQ红包」 发红包了
  • 评测方式 云端评测
  • 标签 容斥 快速傅里叶变换,DFT,FFT 数论,数学 各省省选 2019 湖南
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。