#438. 【NFLSPC #2】Polynomial

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:Special Judge

题目背景

“要不要来做一做我新出的多项式题啊” djq 对可怜的 wzy 说。

uOA5Fg.jpg

题目描述

你有一个多项式 $P(x)=x$,再给定一个次数为 $n$ 的多项式 $Q(x)$,你有两种操作:

  1. 选定一个常数 $c$,把 $P(x)$ 的常数项加上 $c$。即 $P(x) \leftarrow P(x)+c$。
  2. 选定一个常数 $k$,把 $P(x)$ 求 $k$ 次幂。即 $P(x) \leftarrow P^k(x)$,其中 $\leftarrow$ 为赋值。

请你给出一种总操作次数最小的构造方案,使用这两种操作把 $P(x)$ 变为 $Q(x)$,并输出方案。如果无解,请输出 $-1$。

为了方便,所有计算在 $\bmod~998244353$ 的意义下进行。

输入格式

第一行一个正整数 $n$,表示 $Q(x)$ 的次数。

第二行总共 $n+1$ 个非负整数,分别表示 $Q(x)$ 的 $0 \sim n$ 次项系数。

输出格式

若无解,输出一行一个 $-1$。

否则,第一行一个数 $m$ 表示总操作次数。接下来 $m$ 行每行两个非负整数 $a,b$,其中 $a$ 表示操作编号,$b$ 表示操作参数。

若有多种方案,输出任意一种即可。

样例输入 1

2
1 2 1

样例输出 1

2
1 1
2 2

样例解释 1

$(x+1)^2=x^2+2x+1=Q(x)$

可以证明,操作次数最小为 $2$。

样例输入 2

3
3 2 1 1

样例输出 2

-1

样例解释 2

可以证明,不存在合法操作。

数据范围

  • $subtask1(10pts)$:保证 $n \le 20$ 且存在一种操作次数最小的方案使得所有操作参数(即 $c,k$) $\le 10$。

  • $subtask2(15pts)$:$n \le 10^3$,且保证 $n$ 是 $2$ 的幂次。

  • $subtask3(15pts)$:$n \le 10^3$。

  • $subtask4(15pts)$:$n \le 10^5$,且保证 $n$ 是 $2$ 的幂次。

  • $subtask5(20pts)$:$n \le 10^5$。

  • $subtask6(25pts)$:无特殊限制。

对于 $100\%$ 的数据,$1 \le n \le 10^6$,保证输入系数非负且 $< 998244353$,保证最高次项系数为 $1$。


$by\ \text{djq_cpp}$