算法

(数学、字符串) $O(n)$

先统计一下每一段上的1的个数，记为cnt，而对于每一段1上可构成cnt * (cnt + 1) / 2个仅含1的串，然后把这些结果累加即可。

注：

$\frac{{cnt(cnt + 1)}}{2} = cnt + (cnt - 1) + \cdots + 1$

C++ 代码

using LL = long long;
constexpr LL mod = 1'000'000'007;
class Solution {
public:
    int numSub(string s) {
        LL res = 0, sum = 0;
        s.push_back('0');
        for(char c : s){
            if(c == '0'){
                res += sum * (sum + 1) / 2;
                sum = 0;
            }
            else sum += 1;
        }
        return res % mod;
    }
};

Python 代码

class Solution:
    def numSub(self, s: str) -> int:
        mod = 10 ** 9 + 7
        res = cnt = 0
        for c in s:
            if c == '0':
                res += (cnt + 1) * cnt // 2
                cnt = 0
            else:
                cnt += 1
        return (res + (cnt + 1) * cnt // 2) % mod