#P7330. 「MCOI-07」Dream Fourier Transform

「MCOI-07」Dream Fourier Transform

题目背景

Dream 的红石计算机升级为 Dream 平台了。
一个“Dream 程序”为一个在 Dream 平台下执行的程序。
Dream 平台的内存由 5×2175\times2^{17} 个非负整数构成,这些内存位置依次标号为 0,1,,5×21710,1,\dots,5\times2^{17}-1。初始所有内存位置均为 00
Dream 平台有一个特性:第 xx 运算的结果在第 xx 内存位置存储,其中运算从 00 编号。
Dream 程序为若干运算的有序序列,运算类型为:

  1. >,表示输入一个非负整数,结果为输入值。
  2. < x,表示输出内存位置 x 所含的值,结果为这个值。
  3. S c,表示结果为常量非负整数 cc,其中 0c<9982443530\le c<998244353
  4. + x y,表示结果为内存位置 x 的值 加 内存位置 y 的值。
  5. - x y,表示结果为内存位置 x 的值 减 内存位置 y 的值。
  6. * x y,表示结果为内存位置 x 的值 乘 内存位置 y 的值。

其中所有运算在模 998244353998244353 意义下计算。

题目描述

Dream 有一个长度为 nn 的序列 a0,a1,,an1a_0,a_1,\dots,a_{n-1}

Dream 要支持两个操作:

  1. 1 i x,表示将 aia_ixx
  2. 2 k,表示定 x=63912897kx=63912897^k,并且求
i=0n1aixi(mod998244353)\sum_{i=0}^{n-1}a_ix^i\pmod{998244353}

由战争及时,Dream 无法提供序列 aa。他只能预测他会进行的操作。请构造一个“Dream 程序”,读入数组 aa 并且输出对应询问答案。

输入格式

第一行两个正整数,分别代表 nnqq
接下来 qq 行,每行描述一个操作,由 1 i x2 k 格式表示。

输出格式

第一行一个非负整数 LL,代表所构造的 Dream 程序长度。
接下来 LL 行,每行描述一个运算。
你需要保证 L5×217L\le5\times2^{17}

3 3
2 0
1 1 108616
2 114514
15
>
>
>
+ 0 1
+ 3 2
< 4
S 108616
S 716372446
* 1 6
* 8 7
* 7 7
* 2 10
+ 0 9
+ 12 11
< 13

提示

温情提示

$$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353} $$

样例解释

当 Dream 程序输入为序列 [1,2,3],输出为序列 [6,347675984],符合要求。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(11 pts):n,q28n,q\le2^8
  • Subtask 2(19 pts):所有询问操作在修改操作后面。
  • Subtask 3(23 pts):n,q210n,q\le2^{10}
  • Subtask 4(47 pts):没有特殊限制。

对于 100%100\% 的数据,1n,q2121\le n,q\le2^{12}0i<n0\le i<n0x,k<9982443530\le x,k<998244353