当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6716:反向传播

题目描述
一共有 $2^m-1$ 个函数 $f_i(x_1...x_{2^{m-1}})~~~~~(1\leq i\leq 2^m-1)$,其中对于 $2^{m-1}\leq i\leq 2^m-1$,有$f_i(x)=x_{i-2^{m-1}+1}$

对于 $1\leq i\leq 2^{m-1}-1$,有 $f_i(x)=f_{2i}(x)~op_i~f_{2i+1}(x)$,其中 $op_i\in \{+,\times\}$

一开始有 $x_i=i$,接下来一共有 $Q$ 次操作,每次操作是其中以下两个中的一种:

- $1~i~y$:表示令 $x_i=y$
- $2~i$: 表示你需要求出:$\lim_{d\rightarrow 0}\frac{f_1(add(x,i,d))-f_1(x)}{d}$,其中 $add(x,i,d)$ 表示:将 $x_1...x_{2^{m-1}}$ 中的 $x_i$ 变成 $x_i+d$,其他的保持不变,可以发现该操作其实就是需要你求出 $\frac{\partial f_1(x)}{\partial x_i}$

由于答案可能很大,你只需要输出答案对 $998244353$ 取模后的值
输入解释
第一行两个正整数 $m(2\leq m\leq 20)$,$Q(1\leq Q\leq 10^5)$

第二行一个长度为 $2^{m-1}-1$ 的 01 字符串 ,第 $i$ 个字符为 $0$ 表示 $op_i=+$,否则 $op_i=\times$

接下来 $Q$ 行,每行两个数或者三个数表示一次操作,保证 $0\leq y< 998244353$
输出解释
对于每次操作 2,输出答案
输入样例
2 6
1
2 1
2 2
1 1 6
1 2 7
2 1
2 2
输出样例
2
1
7
6
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6716

最后修改于 2020-10-25T23:33:45+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)