F

考虑每一个1的贡献,显然的左边取x个的时候右边可以取0到n-x-1个数,我们用sum[i]表示0数量的前缀和。

那么贡献就是for(int i=2;i<=n;i++)ans+=(sum[i]-sum[i-j])(n-j+1);

我们把这个式子拆开,前面一坨的值是sum[i](n(n-1)/2。

后面一坨是一个前缀和的区间,每一个前缀和有一个系数1到n-1,显然如果我们每次减去这个前缀和的区间和,也就是每个浅醉和系数为1,再加上(n-1)sum[i-1],就能变成下一个位置需要减去的数。

怎么减去这个前缀和的区间呢,直接给前缀和再来个前缀和就好了

代码也是非常短

#define int long long
#define mod 1000000007
using namespace std;
int a[200005],sum[200005],sum2[200005];
signed main(){
    int n,ans=0,g=0;cin>>n;string s;cin>>s;s='0'+s;
    for(int i=1;i<=n;i++)if(s[i]=='1')a[i]=a[i+n]=1;
    for(int i=1;i<=n*2;i++)sum[i]=((a[i]==0)+sum[i-1])%mod;
    for(int i=1;i<=n*2;i++)sum2[i]=(sum[i]+sum2[i-1])%mod;
    for(int i=2;i<=n;i++)g=(g+sum[n+1-i]*(n-i+1)%mod)%mod;
    for(int i=n+1;i<=n*2;i++){
        if(a[i]==1)
            ans=(ans+sum[i]*(n*(n-1)/2%mod)%mod-g+mod)%mod;
        g=(g-(sum2[i-2]-sum2[i-n-1])+mod+sum[i-1]*(n-1)%mod)%mod;
    }
    cout<<ans;
    return 0;
}