题解|#牛牛的Link Power I#

题目链接：https://ac.nowcoder.com/acm/contest/19483/G

模型总结：
模型1：等差数列
原数组： 0 1 0 0 0 0
前缀和： 0 1 1 1 1 1
再前缀和：0 1 2 3 4 5

模型2：平方数列
原本数组： 1 1 0 0 0 0 0
1次前缀和：1 2 2 2 2 2 2
2次前缀和：1 3 5 7 9 11 13
3次前缀和：1 4 9 16 25 36
静态数组求前对后的影响时，考虑前缀和

本题采用模型一。给原数组做一次前缀和，就能算出该位置之前有多少个1；再求一次前缀和，就能得到前面的1对该位置的影响。
需要注意下标的问题：（以100100001为例）
为了计算字符串a每个位置i之前出现1的个数，需要先把a右移一位形成原数组，再进行前缀和
最终找原串中1出现的位置，将二次前缀和在该点处的值相加即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
const ll mod=1e9+7;
int n;
string a;
ll s[100010];//a的前缀和 
ll ss[100010];//a的前缀和的前缀和 

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>> n;
    cin >> a;
    _for(i,0,n-1){
        s[i+1]=s[i]+(a[i]-'0');
    } 
    ll ans=0;
    _for(i,1,n){
        ss[i]=(ss[i-1]+s[i])%mod;
    }
    _for(i,1,n-1){
        if(a[i]=='1')    ans=(ans+ss[i])%mod;
    }
    cout << ans << "\n";
    return 0;
}
/*
9
100100001
*/