NC231649. 羊工八刀
描述
输入描述
第一行输入一个，表示测试样例的个数。
对于每个测试样例：第一行输入一个接下来的一行输入一行
，表示公园里的这条路的长度。
字符串，
表示该点有一个嫌疑人。
输出描述
每个测试样例输出一个答案，任意两个嫌疑人之间距离的平方和。由于答案过大，需要对取模
示例1
输入:
3 3 101 4 1011 3 001
输出:
4 14 0
说明:
该样例中的第二个：pypy3 解法, 执行用时: 261ms, 内存消耗: 76516K, 提交时间: 2021-12-12 15:24:39
t=int(input())
for _ in range(t):
n=int(input())
s = input()
a=[0]*(n+1)
he = [0]*(n+1)
hf = [0]*(n+1)
j=0
for i in range(n):
if s[i]=="1":
a[j]=i+1
he[j]+=he[j-1]+a[j]
hf[j]+=hf[j-1]+a[j]*a[j]
j+=1
ans=0
for i in range(j):
ans+=a[i]*a[i]*i+hf[i-1]-2*he[i-1]*a[i]
print(ans%(1000000007))
C++ 解法, 执行用时: 19ms, 内存消耗: 1392K, 提交时间: 2021-12-13 21:36:29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,p=1e9+7;
char s[N];
int t,n,i,m;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>t;
while (t--)
{
cin>>n>>s;
ll r1=0,r2=0;m=0;
for (i=0;i<n;i++) if (s[i]=='1') r1+=i,r2+=(ll)i*i,++m;
r1%=p;r2%=p;
cout<<(r2*m+(p-r1)*r1)%p<<'\n';
}
}