3642: 斐波(第四轮03)
题目描述
假设 fib(n) 为斐波那契数列的第 n 项，其中fib(0) = 0, fib(1) = 1，且fib(n) = fib(n − 1) + fib(n − 2), (n > 1)。
假设S是一个可重集合{S1, S2, . . . , S∣S∣}， f(S) 定义为f(S) = ∑T⊆S[fib(∑S∈TS )]2
有一个数组a1, a2, . . . , an，牛妹会对数组进行q次操作，每次操作可能是以下两种 操作中的一种：
1. 把ap 变为v；
2. 计算 ∑i(r)=l ∑j(r)=i f({ai, ai+1, . . , aj })。
对于每个操作 2，输出答案模 998244353。
输入
第一行两个整数n, q 。
第二行n个整数a1, a2, . . . , an
接下来q行，每行代表一个操作： 如果是操作1，格式为1pv ；
如果是操作2，格式为2lr。
输出
输出答案，模 998244353。
样例输入 复制
5 3
1 2 3 4 5
2 1 2
1 2 3
2 1 2样例输出 复制
8
19提示
【样例 1 输入】
5 3
1 2 3 4 5
2 1 2
1 2 3
2 1 2
【样例 1 输出】
8
19
【样例 1 说明】
第一个询问:
f({1}) = fib2 (0) + fib2 (1) = 1
f(1,2) = fib2 (0) + fib2 (1) + fib2 (2) + fib2 (3) = 6 f({2}) = fib2 (0) + fib2 (2) = 1
f({1}) + f({1,2}) + f({2}) = 8
第二个操作把数列改变为 1 3 3 4 5
第三个询问:f({1}) + f({1,3}) + f({3}) = 1 + 14 + 4 = 19。
【数据范围】
对于 10%的数据，满足 1 ≤ n, q ≤ 20 对于 50%的数据，满足 1 ≤ n, q ≤ 100 对于 70%的数据，满足 1≤n,q≤1000
对于 100%的数据，满足 1 ≤ n, q ≤ 100000, 1 ≤ ai ≤ 105, ∀1 ≤ i ≤ n,
1 ≤ l ≤ r ≤ n, 1 ≤ p ≤ n, 1 ≤ v ≤ 10^5 。