专题班前缀和练习题 - G - 牛牛的Link Power I

这个题，zngg在讲课的时候案例举得非常明确和详细了，记录一下
把题意转化一下：考虑前面的1，对于后面位置的 x 产生的影响
如：1abcdefg
1对于a的影响，是1
1对于b的影响，是2
1对于c的影响，是3
依次类推
这些影响，什么时候要累加到答案里呢？当abcdefg里某些位置的数是1的时候
所以，这是考虑到单个1的贡献，在abcdefg，会对应于123456789

1 0 0 1 0 0 0 0 1
0 1 0 0 1 0 0 0 0（1）
0 1 1 1 2 2 2 2 2
0 1 2 3 5 7 9 11 13

在把数位上是1的贡献对应好加起来就好了
最难的还是思维转换，从一个数学定义，如何联想转化到前缀与差分

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const long long MOD = 1e9 + 7;
const int maxn = 1e5 + 10;

int T, n, m;
long long a[maxn], ans;
char s[maxn];

void pre_sum(long long a[]){
    for(int i = 1; i <= n; i++)
        a[i] = (a[i] + a[i - 1]) % MOD;
}

int main(){
    scanf("%d", &n);
    scanf("%s", s + 1);
    memset(a, 0, sizeof(a));
    for(int i = 1; i <= n; i++)
        if (s[i] == '1') a[i+1]++;
    pre_sum(a);
    pre_sum(a);
    ans = 0;
    for(int i = 1; i <= n; i++)
        if (s[i] == '1')
            ans = (ans + a[i]) % MOD;
    printf("%lld\n", ans);
    return 0;
}