【JZOJ A组】荒诞

Description

Input

Output

Sample Input

输入1：
7
ABC

输入2：
5
AAAAAAAAAA

Sample Output

输出1：
14

输出2：
385

Data Constraint

Hint

思路

不妨设 s[i]表示 s 的前 i 个字母，也就是第 i 个前缀。C[i]表示 s 的第 i 个字母。

有 s[i]=s[i-1]+c[i]。因为前 i-1 位相同而最后一位有字符，所以 s[i]>s[i-1]。

证完了这个用头皮都想得出的性质后，原问题变为求解 1 到 n 的平方的和。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
int n;
long long ans;
char s[1000077];
int main()
{
    freopen("absurdity.in","r",stdin);
    freopen("absurdity.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",s);
    n=strlen(s);
    for(int i=1; i<=n; i++)
    {
        ans=(ans+1ll*i%mod*i%mod)%mod;
    }
    printf("%d",ans);
}