Readme

3700.Number-of-ZigZag-Arrays-II

此题是3699的进阶版，时间复杂度是o(NM)的动态规划是不可行的。考虑到n如此巨大，必然是用到了类似于快速幂的算法。

此题的思路还是基于之前的DP思想：

up[i][x] = sum(down[i-1][y]) for y=x+1,...,m
down[i][x] = sum(up[i-1][y]) for y=1,2,...,x-1

突破点在于第i轮的状态只依赖于第i-1轮，即{up[i]和down[i]}是{up[i-1],down[i-1]}的线性组合。因此我们令向量vec[i]={up[1],up[2],...,up[m],down[1],down[2],...,down[m]}，它与vec[i-1]之间必然存在转移矩阵T使得vec[i]=T*vec[i-1]. 这样的矩阵是一个2m*2m的方阵。

我们不难构造出T的样子：

............... 0
                1 0
                1 1 0
                ...
                1 1 1 .. 1 1 0
1 1 1 .. 1 1 0  ...........
...
1 1 0
1 0
0

右上部分体现了up[i]与down[i-1]的关系，左下部分体现了down[i]与up[i-1]的关系。

我们易知初始状态v[1] = {1,..0,0..,1}，就可以得到 v[n] = T*T*T...*T*v[1]，其中T要连乘n-1次幂，然后再与向量v[1]想乘，即得最后一轮的v。其向量的所有元素之和就是答案。