Educational Codeforces Round 91 F(矩陣與線段樹優(yōu)化dp)
題意：
? ? 對(duì)于兩個(gè)非負(fù)整數(shù)，現(xiàn)在重新定義加法運(yùn)算：
將?a,b?一上一下寫在兩行，并按照低位對(duì)齊。
將它們的每一位加起來(lái)，并將每一位的結(jié)果從高位到低位連接在一起，得到的就是?a⊕b。
（你可以認(rèn)為，兩個(gè)數(shù)都有無(wú)窮多的前導(dǎo) 0）
例如，3248⊕908=311416
你現(xiàn)在有一個(gè)僅包含?n?個(gè)?0～9?的數(shù)碼的字符串?c，并且還有?m?次操作。一次操作為：
x d?- 將?c?的第?x?個(gè)數(shù)碼替換成數(shù)碼?d?。
（注意，c?在任何時(shí)刻都可能存在前導(dǎo) 0）
每次操作過(guò)后，你需要輸出，有多少個(gè)有序?qū)?/strong>?(a,b)，滿足?a,b?都是非負(fù)整數(shù)，且?a⊕b=c。
答案對(duì)?998244353?取模。
思路：
????動(dòng)態(tài)dp，先考慮沒有修改的情況，表示 1 ~?
?的答案，那么考慮這一位單獨(dú)稱為一個(gè)數(shù)字的貢獻(xiàn)以及與前一個(gè)數(shù)字組合的貢獻(xiàn)（此時(shí)前一位必須是1），那么轉(zhuǎn)移方程為
，
因?yàn)轭}目中要求有修改的操作，每次都去跑一邊dp一定會(huì)超時(shí)，所以考慮將這個(gè)遞推式轉(zhuǎn)換為矩陣，則可以表示為
初始化：把和
置成1
用線段樹維護(hù)每個(gè)區(qū)間即可
注意：
線段樹在push_up的時(shí)候，一定是右兒子乘左兒子（上面矩陣的遞推式也可以看出來(lái)，（等號(hào)左邊那一坨）左邊是
，右邊是?
?~?
?）
當(dāng)修改
時(shí)，要修改
和
，因?yàn)?img type="latex" class="latex" src="https://api.bilibili.com/x/web-frontend/mathjax/tex?formula=pos%2B1%0A" alt="pos%2B1%0A">在更新dp的時(shí)候會(huì)用到pos
