#1700. 朝圣道
朝圣道
朝圣道
题目描述
标题: 朝圣道 - Problem - QOJ.ac
#5099. 朝圣道
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