题解|#牛牛的Link Power I#
题目链接:https://ac.nowcoder.com/acm/contest/19483/G
模型总结:
模型1:等差数列
原数组: 0 1 0 0 0 0
前缀和: 0 1 1 1 1 1
再前缀和:0 1 2 3 4 5
模型2:平方数列
原本数组: 1 1 0 0 0 0 0
1次前缀和:1 2 2 2 2 2 2
2次前缀和:1 3 5 7 9 11 13
3次前缀和:1 4 9 16 25 36
静态数组求前对后的影响时,考虑前缀和
本题采用模型一。给原数组做一次前缀和,就能算出该位置之前有多少个1;再求一次前缀和,就能得到前面的1对该位置的影响。
需要注意下标的问题:(以100100001为例)
为了计算字符串a每个位置i之前出现1的个数,需要先把a右移一位形成原数组,再进行前缀和
最终找原串中1出现的位置,将二次前缀和在该点处的值相加即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define mst(v,s) memset(v,s,sizeof(v)) const ll mod=1e9+7; int n; string a; ll s[100010];//a的前缀和 ll ss[100010];//a的前缀和的前缀和 int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>> n; cin >> a; _for(i,0,n-1){ s[i+1]=s[i]+(a[i]-'0'); } ll ans=0; _for(i,1,n){ ss[i]=(ss[i-1]+s[i])%mod; } _for(i,1,n-1){ if(a[i]=='1') ans=(ans+ss[i])%mod; } cout << ans << "\n"; return 0; } /* 9 100100001 */