设字符串为s,长度为len
记preq[i]为s的前缀'?'数量,lastq[i]为s的后缀'?'数量,prea[i]为s的前缀'a'数量,lastc[i]为s的后缀'c'数量(均不含s[i])
则 ans=∑i=1len(s[i]==′b′∨s[i[==′?′)∗∑j=0preq[i]∑k=0lastq[i](prea[i]+j)∗(lastc[i]+k)∗Cpreq[i]j∗Clastq[i]k∗2preq[i]+lastq[i]−j−k
这个式子实现显然最好是O(n3)的,不知道能不能优化到能通过本题的形式??(式子正确性应该没问题,暴力打了样例都过了)