#1905. 伪随机

    ID: 1905 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest1961来源:qoj.ac数据:公开样例递推二分

伪随机

伪随机

题目描述

标题: 伪随机 - Problem - QOJ.ac

#10303. 伪随机

Statistics

题目背景

众所周知,可以用一些简单的算法来生成伪随机序列。然而,某些这样的算法并不靠谱,因为生成的数据可以被快速预测。如下我们将给出一种伪随机算法,使得我们能快速预测序列中的值。

题目描述

给定一个整系数多项式 。递归定义数列 如下:。

有 次询问,分为两种:

  • 给定 ,求 。
  • 给定 ,求最小的 使得 ,或者判断无解。

,,,其中 为 的系数。

输入格式

从标准输入读入数据。

输入第一行包含两个整数 (),(),分别表示多项式 的次数和 的值。

第二行输入 个小于 的非负整数 表示 的 次项系数。

第三行输入一个正整数 (),表示询问的个数。

接下来 行,每一行两个整数 (),()表示一组询问。

  • 对于 :这个询问要求 的值。
  • 对于 :这个询问要求满足 的最小的 。

输出格式

输出到标准输出。

对于每一组询问,输出一行一个整数,表示这组询问的答案。

对于无解的询问,输出 -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