小藍(lán)有一個(gè)長(zhǎng)度均為 n 且僅由數(shù)字字符 0 ~ 9 組成的字符串,下標(biāo)從 0 到 n ? 1,你可以將其視作是一個(gè)具有 n 位的十進(jìn)制數(shù)字 num,小藍(lán)可以從 num 中選出一段連續(xù)的子串并將子串進(jìn)行反轉(zhuǎn),最多反轉(zhuǎn)一次。小藍(lán)想要將選出的子串進(jìn)行反轉(zhuǎn)后再放入原位置處得到的新的數(shù)字 numnew 滿足條件 numnew < num,請(qǐng)你幫他計(jì)算下一共有多少種不同的子串選擇方案,只要兩個(gè)子串在 num 中的位置不完全相同我們就視作是不同的方案。
注意,我們?cè)试S前導(dǎo)零的存在,即數(shù)字的最高位可以是 0 ,這是合法的。
輸入一行包含一個(gè)長(zhǎng)度為 n 的字符串表示 num(僅包含數(shù)字字符 0 ~ 9),
從左至右下標(biāo)依次為 0 ~ n ? 1。
輸出一行包含一個(gè)整數(shù)表示答案。
210102
8
一共有 8 種不同的方案:
1)所選擇的子串下標(biāo)為 0 ~ 1 ,反轉(zhuǎn)后的 numnew = 120102 < 210102 ;
2)所選擇的子串下標(biāo)為 0 ~ 2 ,反轉(zhuǎn)后的 numnew = 012102 < 210102 ;
3)所選擇的子串下標(biāo)為 0 ~ 3 ,反轉(zhuǎn)后的 numnew = 101202 < 210102 ;
4)所選擇的子串下標(biāo)為 0 ~ 4 ,反轉(zhuǎn)后的 numnew = 010122 < 210102 ;
5)所選擇的子串下標(biāo)為 0 ~ 5 ,反轉(zhuǎn)后的 numnew = 201012 < 210102 ;
6)所選擇的子串下標(biāo)為 1 ~ 2 ,反轉(zhuǎn)后的 numnew = 201102 < 210102 ;
7)所選擇的子串下標(biāo)為 1 ~ 4 ,反轉(zhuǎn)后的 numnew = 201012 < 210102 ;
8)所選擇的子串下標(biāo)為 3 ~ 4 ,反轉(zhuǎn)后的 numnew = 210012 < 210102 ;
對(duì)于 20% 的評(píng)測(cè)用例,1 ≤ n ≤ 100 ;
對(duì)于 40% 的評(píng)測(cè)用例,1 ≤ n ≤ 1000 ;
對(duì)于所有評(píng)測(cè)用例,1 ≤ n ≤ 5000 。