• 羊工八刀：

  • 直接写必然会超时，但是pta估计就能交上去，咳咳！

  • 先说思路：枚举每个位置直接算肯定会爆炸，所以我们发现到当前的1的总平方和仅仅受到其前面的1影响，很显然是一道DP

  • 每次枚举到一个新的1，当前的由这个1开始的总平方和就是（上一个1的总平方和）加上（上一个1的前面所有的1到上一个1的距离和2当前1到上一个1的距离）加上（当前1的前面的1的总个数乘以当前1到上一个1的距离）加上（当前1到上一个1距离的平方）可能有点不好理解我举个例子

  • 对于10111

  • 枚举到第二个1时平方和等于2显而易见

  • 枚举到第三个1时平方和等于10显而易见

  • 枚举到最后一个1时当前的这个1前面的1前面所有1到前面1的距离就是4

  • sum = 10 + 2 * 4 * 1 + 2 * 1 * 1 + 1 * 1 = 21

  • 为什么会这样，上面的公式时什么意思呢

  • 其实就是一个完全平方公式

  • 上一个sum就是上一个1的前面的1到上一个1的距离平方和，我们写成:

  • x1^2 + x2^2 + ... + xn^2

  • 统计的当前1的前一个1的前面的所有1到上一个1的距离和就是:

  • x1 + x2 + ... + xn

  • 当前1到上一个1的距离就是y

  • 所以上面描述的哪一大串公式就是x1^2 + x2^2 + ... + xn^2 + 2 * (x1 + x2 + ... + xn) * y + y + y + ... + y(前面1的个数个) + y

  • 含义就是(x1^2 + 2 * x1 * y + y * y) + (x2^2 + 2 * x2 * y + y * y) + ... + (xn^2 + 2 * xn * y + y * y) + y * y

  • 也就是当前的1前面所有1到当前1的距离平方和

#include<iostream>
using namespace std;
const int N=1e6+10,mod=1e9+7;
typedef long long ll;
char s[N];
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n,pos=-1;cin>>n;
        scanf("%s",s);
        ll num=0,len=0,cnt=0,sum=0;
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            if(pos==-1&&s[i]=='1')
            {
                pos=i;continue;
            }
            if(s[i]=='1')
            {
                num++;
                sum+=2*len*(i-pos)+(i-pos)*(i-pos)*num,sum%=mod;
                len+=num*(i-pos),len%=mod;
                ans+=sum,ans%=mod;
                pos=i;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}