6547: Walk
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
There is currently a grid of n×m. You have to walk start at (1,k1)(∀1≤k1≤m),end at (n,k2)(∀1≤k2≤m).For every possible path, there will be a value V.The initial value of V is f[k1] when you start at (1,k1).When you reach (x,y), the value will become V × f [y].When you are located at (x,y) , you can walk to (x+1,P)(P≤y+S (S (S (y) ) ) )
Where S(x)=⌊log2(max(1,x)))⌋
Calculate the sum of the value of all the ways module 998244353.
Two ways A,B think different if ∃(x,y), A passes (x,y) but B not.
Where S(x)=⌊log2(max(1,x)))⌋
Calculate the sum of the value of all the ways module 998244353.
Two ways A,B think different if ∃(x,y), A passes (x,y) but B not.
输入
The first line contains two integers n,m
The second line contains m integers f1,f2,...,fm
1≤n,m≤105,0≤ fi ≤109
The second line contains m integers f1,f2,...,fm
1≤n,m≤105,0≤ fi ≤109
输出
print one integer — the answer to the problem.
样例输入 复制
5 4
1 2 3 4样例输出 复制
7770