problem
给定字符串 s,si∈{0,1,?} , ?
可以视为0
或1
任意一种,若干次单点修改,每次修改回答本质不同字串个数(长相不同的字串个数)
Solution
设 fi 为前i位以1结尾的不同字串个数,gi表示前i位以0结尾的不同字串个数
有方程
fi={fi−1 , si=0fi−1+gi−1+1 , si=1 or si= ?
gi={fi−1+gi−1+1 , si=0 or si=?gi−1 , si=1
发现可以写成矩阵
状态矩阵为
ansi=[figi1]
转移矩阵:
si=0:⎣⎡100111001⎦⎤
si=1:⎣⎡111010001⎦⎤
si= ?:⎣⎡111111001⎦⎤
用线段树维护矩阵,支持区间矩阵乘法,单点修改,区间查询即可
时间复杂度O(qlogn)
Code
Atcoder