XJB,又名constructive algorithm,是人类史上最伟大的算法,理论上可以解决一切问题。
HJC钻研XJB已经到了很深的境界,一心想修成XJB第九层心法,然而却走火入魔,整天叨念着一些不知名的话语。
万般无奈之下,我们请来了单总。
单总看着胡言乱语的HJC,眼睛却是越来越亮:“他这不是简单的走火入魔,这很有可能是一场大机缘!你们仔细听他的话。”
HJC:“JXXJXB!”
(N脸懵逼)
“仔细观察,他的话仅由'X','J','B'三个字母组成。我曾在一部古籍上看到,XJB修炼到最高境界,将不再拘泥于XJB的固定形式,彻底解放思维,以X生J,以J生B,以B生万物,万物生生不息!”
“难不成?”
“没错”,单总的眼光愈发得炽热,“他很可能已经触摸到了XJB王境的门槛,只要加以适当引导,我们将见证一位XJB之王的诞生!”
“我们需要怎么做?”
“据古籍所说,我们只要持续不断地计算出他每句话中XJB的个数,并以慑魂大法将之轰击至他的元神即可,其他的,就看他的造化了。”
单总仿佛看出了我们的不屑,继续补充道:“当然这个计数不是简单的计数,而是可以跨越若干个字符的组合。例如他刚刚那句话:JXXJXB,就包含了两个“XJB”,其中第一个XJB是第2位(X),第4位(J),第6位(B);第二个XJB是第3位(X),第4位(J),第6位(B)。正式点说,设a[i]为字符串中第i个字母,请你找出所有的(i,j,k)使得a[i]='X',a[j]='J',a[k]='B',i<j<k,明白了吗?”
“明白了!”
“好,你们开始吧,我为你们护法!”
第一行一个整数T,代表有T组数据。
每一组数据包含一行字符串,仅由'X','J','B'三个字母组成,长度不超过10^5。
对于每组数据,输出XJB的个数。由于结果可能比较大,只输出对1000000007取余数的结果。
推论:对于加法、乘法、乘方运算,算好后取余和边算边取余是等价的
以加法为例:
(a+b+c+...d)%m
将a,b,c..,d分解成z1*m+k1 , z2*m+k2 , z3*m+k3.....z4*m+k4
则 原式
=(z1*m+k1 , z2*m+k2 , z3*m+k3.....z4*m+k4)%m
=(k1+k2+k3+...k4)%m
=(a%m+b%m+c%m+....d%m)
乘法和乘方类似的。
(也就说你们不用纠结取模的问题,边算边取余就可以辣{{{(>_< )}}} )