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; }