#1700. 朝圣道

    ID: 1700 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1049来源:qoj.ac数据:公开样例动态规划数学

朝圣道

朝圣道

题目描述

标题: 朝圣道 - Problem - QOJ.ac

#5099. 朝圣道

Statistics

The problem was used in the following contests:

题目背景

这里本来应该有一个绝妙的题目背景,可惜位置太小写不下了。

题目描述

给定一个数轴,你初始时位于原点。

每一单位时间内,你将分别以 14,12,14 的概率向左移动一个单位长度、不动、向右移动一个单位长度。

有 T 次询问,每次询问给定 n,求 n 个单位时间后后位移大小(即所在位置坐标的绝对值)的期望对 p 取模的结果。

实现细节

请在提交源代码前添加 #include "pilgrimage.h"。

你需要实现以下函数:

void init (int o, int p);
  • o:表示该测试点所属的子任务编号,特别地,对于样例有 o=0。
  • p:表示该测试点的模数。

该函数在每个测试点内只会被调用一次,早于任何一次 ask 调用。

int ask (long long n);
  • n:表示一次询问的时间长度。
  • 该函数需要返回一个 [0,p) 范围内的整数表示答案。

评测程序示例

评测程序示例按照以下格式读入输入数据:

  • 第 1 行:o T p,其中 o 表示该测试点所属的子任务编号。
  • 第 2+i(0≤i<T)行:n[i]。

评测程序示例首先调用 init,然后按照 i=0,1,…,T−1 的顺序调用 ask:n=n[i]。

评测程序示例按照以下格式输出:

第 1+i(0≤i<T)行:一个 [0,p) 范围内的整数,表示第 i 次调用 ask 返回的结果。

样例

样例输入

0 9 999983
1
2
3
4
5
12
2999
999999
1000000000000000000

样例输出

499992
749988
937485
593741
292965
279604
703253
798000
771553

样例解释

以 n=2 为例,有以下 9 种情况:

  • 第一个单位时间内向左,第二个单位时间内向左,最终位于 −2,概率为 116。
  • 第一个单位时间内向左,第二个单位时间内不动,最终位于 −1,概率为 18。
  • 第一个单位时间内向左,第二个单位时间内向右,最终位于 0,概率为 116。
  • 第一个单位时间内不动,第二个单位时间内向左,最终位于 −1,概率为 18。
  • 第一个单位时间内不动,第二个单位时间内不动,最终位于 0,概率为 14。
  • 第一个单位时间内不动,第二个单位时间内向右,最终位于 1,概率为 18。
  • 第一个单位时间内向右,第二个单位时间内向左,最终位于 0,概率为 116。
  • 第一个单位时间内向右,第二个单位时间内不动,最终位于 1,概率为 18。
  • 第一个单位时间内向右,第二个单位时间内向右,最终位于 2,概率为 116。

故期望为 |−2|×116+|−1|×18+⋯+|2|×116=34,在模 999983 意义下即为 749988。

数据范围

对于所有测试数据,满足 3≤p≤106,1≤T≤106,1≤n≤1018,保证 p 为奇数。

每个子任务的具体限制如下表所示:

子任务编号 分值 p≤ T≤ n≤ 特殊性质 A 特殊性质 B 1 4 106 106 12 否 否 2 8 3000 3 12 1 ⌊p−12⌋ 是 是 4 18 106 5 14 1018 6 12 否 7 8 1 否 8 16 104 104 9 8 106 106

  • 特殊性质 A:p 是素数。
  • 特殊性质 B:p=p1×p2×⋯×pk,其中 p1,p2,…,pk 是两两不同的素数。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

0 9 999983
1
2
3
4
5
12
2999
999999
1000000000000000000
499992
749988
937485
593741
292965
279604
703253
798000
771553