HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6050 Funny Function 矩阵快速幂 矩阵变化

http://acm.hdu.edu.cn/showproblem.php?pid=6050

Funny Function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.
Input
There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.
Output
For each given N and M,print the answer in a single line.

Sample Input

2
2 2
3 3

Sample Output

2
33

Source

题意

给定上图公式和$n,m$,求$F_{m,1}$

思路

可以发现,$F_{i,j} = F_{i,j-1}+2*F_{i,j-2}$,对于每行,维护出$F_j, F_{j-1},Sum_j,F_1$,用矩阵快速幂计算即可。转移到下一行,
$$F_j = Sum_{n+1} - F_1$$
$$F_{j-1} = Sum_{n+1} - F_n$$
$$Sum_j = 2* Sum_{n+1} -  F_1 - F_n$$
$$F_1 = Sum_{n+1} - F_n$$
上述变化是线性的,前面乘以一个矩阵即可表示。最后将所得的矩阵快速幂$m-1$次后,乘上维护的信息,就是最后的答案。