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

题目：

要求构造一个由数字1,2,3组成的长度为n的序列，

其中某些位置已经指定(1,2,3中的一个),同时有一组规则，

即某些数字不能相邻，例如23. 求序列的可能个数。

题解：

区间DP + 线段树 + 矩阵乘法

维护一个线段树，每个节点有一个矩阵a[3][3],

a[i][j]表示这个区间的第一个数是i,最后一个数是j的序列数目有多少。

初始化的时候，对于叶子，便是a[i][j]=(i==j?1:0)，即对角矩阵，表示每一位有1,2,3三种可能。

然后向上更新，则需要枚举父亲的两端，然后枚举子节点的另外两端，判断两个内侧相邻是否符合规则，使用矩阵乘法。

对于每一次查询，则去更新叶子结点。