#1905. 伪随机
伪随机
伪随机
题目描述
标题: 伪随机 - Problem - QOJ.ac
#10303. 伪随机
题目背景
众所周知,可以用一些简单的算法来生成伪随机序列。然而,某些这样的算法并不靠谱,因为生成的数据可以被快速预测。如下我们将给出一种伪随机算法,使得我们能快速预测序列中的值。
题目描述
给定一个整系数多项式 。递归定义数列 如下:。
有 次询问,分为两种:
- 给定 ,求 。
- 给定 ,求最小的 使得 ,或者判断无解。
,,,其中 为 的系数。
输入格式
从标准输入读入数据。
输入第一行包含两个整数 (),(),分别表示多项式 的次数和 的值。
第二行输入 个小于 的非负整数 表示 的 次项系数。
第三行输入一个正整数 (),表示询问的个数。
接下来 行,每一行两个整数 (),()表示一组询问。
- 对于 :这个询问要求 的值。
- 对于 :这个询问要求满足 的最小的 。
输出格式
输出到标准输出。
对于每一组询问,输出一行一个整数,表示这组询问的答案。
对于无解的询问,输出 -1。
样例
输入
1 0
1 1
2
1 100
2 100
输出
100
100
解释
。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
子任务
下面的 表示第一类询问中的 的最大值。
子任务 ( 分):,。
子任务 ( 分):。
子任务 ( 分):。
子任务 ( 分):。
子任务 ( 分):。
子任务 ( 分):无额外限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 0
1 1
2
1 100
2 100
100
100
样例 2
3 0
1 0 1 1
6
1 123456
1 314124414211
1 32647614864861231
2 123456
2 23141421231
2 141241311323
11291754590384060799
6505308383668450853
1981985835118963565
-1
4954317998318152
7448487559802353958