以下所有值均在 (mathbb F_{998244353}) 上运算。
给定多项式 (P(x)=x) 和 (n) 次首 (1) 多项式 (Q(x)=sum_{k=0}^n a_kx^k)，你可以进行两种操作：
1 c：表示令 (P(x):=P(x)+c)。2 k：表示令 (P(x):=P(x)^k)。
构造长度最小的操作序列，使 (P(x)=Q(x))。需判断无解。
(nle 10^6)。
显然最终的操作序列会使 (P(x)=(cdots(x^{k_0}+c_1)^{k_1}+cdots+c_m)^{c_m})，其中 (k_0) 可以 (=1)，其他的 (k_i>1)，所有 (c_i e 0)。
考虑将操作改为对 (Q(x)) 做，则 1 c 表示 (Q(x):=Q(x-c))，2 k 表示令 (Q(x):=Q(x^{1/k}))。
先看 (k_0=1) 的情况，归纳一下可以得到 (c_1=[x^{n-1}]Q(x)/n)，于是直接平移一下即可。然后将 (Q(x)) 的非 (0) 项的次数除以它们的 (gcd)。
若 (k_0 e 1)，初始时判一下 (gcd) 即可。若有某一步缩不起来就无解。
每次除以 (gcd) 次数至少减半，于是得到时间复杂度 (T(n)=T(n/2)+O(nlog n)=O(nlog n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1<<21, mod = 998244353;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0; bool f = false;
for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} int ksm(int a, int b){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
} void qmo(int &x){x += x >> 31 & mod;}
int n, m, lim, rev[N], w[N], a[N], b[N], fac[N], finv[N], inv[N], ans[50];
int gcd(int x, int y){return y ? gcd(y, x % y) : x;}
int calc(){ int g = 0;
for(int i = 1;i <= n && g != 1;++ i)
if(a[i]) g = gcd(g, i);
return g;
} void work(int g){
assert(!(n % g)); n /= g; ans[m++] = -g;
for(int i = 0;i <= n;++ i){b[i] = a[i * g]; a[i * g] = 0;}
memcpy(a, b, n+1<<2); memset(b, 0, n+1<<2);
} void init(int n){
fac[0] = 1;
for(int i = 1;i <= n;++ i) fac[i] = (LL)fac[i-1] * i % mod;
finv[n] = ksm(fac[n], mod-2);
for(int i = n;i;-- i){
finv[i-1] = (LL)finv[i] * i % mod;
inv[i] = (LL)finv[i] * fac[i-1] % mod;
} for(int mid = 1;mid < N;mid <<= 1){
int Wn = ksm(3, (mod-1) / (mid<<1)); w[mid] = 1;
for(int i = 1;i < mid;++ i) w[mid+i] = (LL)w[mid+i-1] * Wn % mod;
}
} void calrev(int len){
int L = -1; lim = 1;
while(lim <= len){lim <<= 1; ++ L;}
for(int i = 0;i < lim;++ i)
rev[i] = (rev[i>>1]>>1) | ((i&1)<<L);
} void NTT(int *A, bool op){
for(int i = 0;i < lim;++ i)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1;mid < lim;mid <<= 1)
for(int i = 0;i < lim;i += mid<<1)
for(int j = 0;j < mid;++ j){
int y = (LL)((op && j) ? (mod - w[(mid<<1)-j]) : w[mid+j]) * A[mid+i+j] % mod;
qmo(A[mid+i+j] = A[i+j] - y); qmo(A[i+j] += y - mod);
}
if(op){ int inv = ksm(lim, mod-2);
for(int i = 0;i < lim;++ i) A[i] = (LL)A[i] * inv % mod;
}
}
int main(){
read(n); init(n);
for(int i = 0;i <= n;++ i) read(a[i]);
int g = calc(); if(g != 1) work(g);
while(n > 1){
if(!a[n-1]) return puts("-1"), 0;
int c = (LL)a[n-1] * inv[n] % mod; ans[m++] = c; c = mod - c;
for(int i = 0;i <= n;++ i) a[i] = (LL)a[i] * fac[i] % mod;
for(int i = 0, pw = 1;i <= n;++ i, pw = (LL)pw * c % mod) b[n-i] = (LL)pw * finv[i] % mod;
calrev(n<<1); NTT(a, 0); NTT(b, 0);
for(int i = 0;i < lim;++ i) a[i] = (LL)a[i] * b[i] % mod;
NTT(a, 1); for(int i = 0;i <= n;++ i) a[i] = (LL)a[i+n] * finv[i] % mod;
memset(a+n+1, 0, lim-n-1<<2); memset(b, 0, lim<<2);
int g = calc(); if(g == 1) return puts("-1"), 0; work(g);
} if(a[0]) ans[m++] = a[0];
printf("%d
", m);
for(int i = 0;i < m;++ i) printf("%d %d
", 1 + (ans[i] < 0), abs(ans[i]));
}