https://codeforces.com/contest/256/problem/E

題目：

要求構(gòu)造一個(gè)由數(shù)字1,2,3組成的長度為n的序列，

其中某些位置已經(jīng)指定(1,2,3中的一個(gè)),同時(shí)有一組規(guī)則，

即某些數(shù)字不能相鄰，例如23. 求序列的可能個(gè)數(shù)。

題解：

區(qū)間DP + 線段樹 + 矩陣乘法

維護(hù)一個(gè)線段樹，每個(gè)節(jié)點(diǎn)有一個(gè)矩陣a[3][3],

a[i][j]表示這個(gè)區(qū)間的第一個(gè)數(shù)是i,最后一個(gè)數(shù)是j的序列數(shù)目有多少。

初始化的時(shí)候，對于葉子，便是a[i][j]=(i==j?1:0)，即對角矩陣，表示每一位有1,2,3三種可能。

然后向上更新，則需要枚舉父親的兩端，然后枚舉子節(jié)點(diǎn)的另外兩端，判斷兩個(gè)內(nèi)側(cè)相鄰是否符合規(guī)則，使用矩陣乘法。

對于每一次查詢，則去更新葉子結(jié)點(diǎn)。

?