Atcoder Ex - 01? Queries

problem

给定字符串 s,si{0,1,?}s,s_i \in \{0,1,?\} , ?可以视为01任意一种,若干次单点修改,每次修改回答本质不同字串个数(长相不同的字串个数)

Solution

fif_i 为前ii位以11结尾的不同字串个数,gig_i表示前ii位以00结尾的不同字串个数

有方程

fi={fi1 , si=0fi1+gi1+1 , si=1 or si= ? f_i= \left\{ \begin{aligned} &f_{i-1}~,~s_i=0\\ &f_{i-1}+g_{i-1}+1~,~s_i=1 ~or~ s_i=~?\\ \end{aligned} \right.

gi={fi1+gi1+1 , si=0 or si=?gi1 , si=1 g_i= \left\{ \begin{aligned} &f_{i-1}+g_{i-1}+1~,~s_i=0~or~ s_i=?\\ &g_{i-1}~,~s_i=1\\ \end{aligned} \right.

发现可以写成矩阵

状态矩阵为

ansi=[figi1]ans_i= \begin{bmatrix} {f_i}&{g_i}&1\\ \end{bmatrix}

转移矩阵:

si=0:[110010011]s_i=0:\\ \begin{bmatrix} 1&1&0\\ 0&1&0\\ 0&1&1\\ \end{bmatrix}

si=1:[100110101]s_i=1:\\ \begin{bmatrix} 1&0&0\\ 1&1&0\\ 1&0&1\\ \end{bmatrix}

si= ?:[110110111]s_i=~?:\\ \begin{bmatrix} 1&1&0\\ 1&1&0\\ 1&1&1\\ \end{bmatrix}

用线段树维护矩阵,支持区间矩阵乘法,单点修改,区间查询即可

时间复杂度O(qlogn)O(q\log{n})

Code

Atcoder

Author: cjh-hhz
Link: https://cjh-hhz.github.io/92954ab337af.html/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.