#PQJ1961x10303. QOJ 1961_10303

    ID: 2763 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2023动态规划二分答案

QOJ 1961_10303

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

#10303. 伪随机

Statistics

题目背景

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

题目描述

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

有 次询问,分为两种:

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

,,,其中 为 的系数。

输入格式

从标准输入读入数据。

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

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

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

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

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

输出格式

输出到标准输出。

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

对于无解的询问,输出 -1。

样例

输入

1 0
1 1
2
1 100
2 100

输出

100
100

解释

。

样例二

见下载目录下的 ex_2.in 与 ex_2.ans。

子任务

下面的 表示第一类询问中的 的最大值。

子任务 ( 分):,。

子任务 ( 分):。

子任务 ( 分):。

子任务 ( 分):。

子任务 ( 分):。

子任务 ( 分):无额外限制。