Walk
Time Limit : 8000/4000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
There is currently a grid of $ n \times m $. You have to walk start at $(1,k_1)(\forall 1\le k_1 \le m)$,end at $(n,k_2)(\forall 1\le k_2\le m)$.For every possible path, there will be a value $V$.The initial value of $V$ is $f[k_1]$ when you start at $(1,k_1)$.When you reach $(x,y)$, the value will become $V \times f [y]$.When you are located at $ (x, y) $ , you can walk to $ (x+1, P) (P \le y+S ( S (S (y)))) $
Where $S(x)=\lfloor log2(max(1,x))) \rfloor$
Calculate the sum of the value of all the ways module $998244353$.
Two ways $ A,B$ think different if $ \exists (x,y)$, $A$ passes $(x,y)$ but $B$ not.
Where $S(x)=\lfloor log2(max(1,x))) \rfloor$
Calculate the sum of the value of all the ways module $998244353$.
Two ways $ A,B$ think different if $ \exists (x,y)$, $A$ passes $(x,y)$ but $B$ not.
Input
The first line contains two integers $n,m$
The second line contains $m$ integers $f_1,f_2,...,f_m$
$1\le n,m\le 10^5,0 \le f_i\le 10^9$
The second line contains $m$ integers $f_1,f_2,...,f_m$
$1\le n,m\le 10^5,0 \le f_i\le 10^9$
Output
print one integer — the answer to the problem.
Sample Input
5 4 1 2 3 4
Sample Output
7770
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）