【題解】Codeforces 1383E. Strange Operation

#include <iostream>
#include <string>
using namespace std;
 
int n, l, r, a[1000005], nxt[1000005], cnt;
long long ans, mul, dp[1000005], mod = 1e9+7;
string s;
 
int main() {
    cin >> s;
    n = s.length();
    cnt = 1;
    while (s.size() && s.back() == '0'){
        cnt++;
        s.pop_back();
    }
    mul = cnt;
    int ptr = 0;
    if (!s.size()){
        cout << mul-1 << "\n";
        return 0;
    }
    while (ptr < s.length() && s[ptr] == '0'){
        ptr++;
    }
    mul *= (ptr+1);
    mul %= mod;
    s = s.substr(ptr);
    for (int i = 1; i < s.length(); i++){
        if (s[i] == '0') a[i] = a[i-1]+1;
        else a[i] = 0;
    }
    dp[s.length()-1] = 1;
    nxt[0] = s.length()-1;
    for (int i = (int)s.length()-2; i >= 0; i--){
        dp[i] = dp[nxt[a[i]+1]] + dp[nxt[0]] + (s[i] == '1');
        dp[i] %= mod;
        nxt[a[i]] = i;
    }
    ans = dp[0] * mul % mod;
    cout << ans << "\n";
}