G 牛牛的Link Power I

考虑每个点的贡献。
因为题目说 和 算一组，所以我们不妨令 。然后我们发现点 对后面节点的贡献为一个 首相为1 公差为1 的等差数列。于是我们便可以愉快地二阶差分了，最后遍历每个1答案加上其位置上的权值即可。

my code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10,mod = 1e9 + 7;
int n;
ll ans;
ll sum[maxn];
char a[maxn];
int main(){
    scanf("%d%s",&n,a + 1);
    for(int i = 1;i <= n;i++)
    if(a[i] == '1') sum[i + 1]++;
    for(int i = 1;i <= n;i++) sum[i] = (sum[i] + sum[i - 1]) % mod;
    for(int i = 1;i <= n;i++){
        sum[i] = (sum[i] + sum[i - 1]) % mod;
        if(a[i] == '1') ans += sum[i],ans %= mod;
    } 
    printf("%lld",ans);
    return 0;
}

std:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long long mod = 1e9 + 7;
char s[MAXN];
int n;
long long ans, sum[MAXN];
void pre_sum()
{
    for (int i = 1; s[i]; ++i)
    {
        sum[i] += sum[i - 1];
        if (sum[i] >= mod)sum[i] -= mod;
    }
}
int main()
{
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 0; s[i]; ++i)
    {
        if (s[i] == '1')
        {
            sum[i + 1]++;
        }
    }
    pre_sum();
    pre_sum();
    for (int i = 1; s[i]; ++i)
    {
        if (s[i] == '1')
        {
            ans += sum[i];
            if (ans >= mod)ans -= mod;
        }
    }
    printf("%lld\n", ans);
    return 0;
}