codeforces 519D dp

雨点打透心脏的1/2处 2022-07-24 05:08 180阅读 0赞

D. A and B and Interesting Substrings

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

*A and B are preparing themselves for programming contests.*

After several years of doing sports programming and solving many problems that require calculating all sorts of abstract objects, A and B also developed rather peculiar tastes.

A likes lowercase letters of the Latin alphabet. He has assigned to each letter a number that shows how much he likes that letter (he has assigned negative numbers to the letters he dislikes).

B likes substrings. He especially likes the ones that start and end with the same letter (their length must exceed one).

Also, A and B have a string *s*. Now they are trying to find out how many substrings *t* of a string *s* are interesting to B (that is, *t* starts and ends with the same letter and its length is larger than one), and also the sum of values of all letters (assigned by A), *except for the first and the last one* is equal to zero.

Naturally, A and B have quickly found the number of substrings *t* that are interesting to them. Can you do it?

Input

The first line contains 26 integers *x**a*, *x**b*, ..., *x**z* ( - 105 ≤ *x**i* ≤ 105) — the value assigned to letters *a*, *b*, *c*, ..., *z* respectively.

The second line contains string *s* of length between 1 and 105 characters, consisting of Lating lowercase letters— the string for which you need to calculate the answer.

Output

Print the answer to the problem.

Examples

input

1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
    xabcab

output

input

1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
    aaa

output

Note

In the first sample test strings satisfying the condition above are *abca* and *bcab*.

In the second sample test strings satisfying the condition above are two occurences of *aa*.

题意: 给定每个字母的价值, 求给定的字符串的子串中 首尾相同并且子串中不包含首尾的字符的价值和等于0的子串个数.

分析: 这种题一般就跟前缀和相关了, 一定要考虑前缀和啊, 有了前缀和的话, 当碰见一个字符的时候,假设现在前缀和是sum了(还没加上当前这个元素的价值), 考虑在他前面跟他相同的字符, 如果这个字符的前缀和也是sum(加上了这个字符的价值), 那么两者相减就是他们之间的元素的值的和, 也就是0. 那么, 只要记住相同元素的每个前缀和的个数, 在每次遍历的时候加上前面相同元素的这个前缀和的个数, 再考虑以下他的贡献, 就行了.

#include<bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=100010,MOD=1e9+7;
    map<ll,ll> dp[26];
    
    int val[26];
    string s;
    int main()
    {
        for(int i=0;i<26;i++)
        {
            cin>>val[i];
        }
        cin>>s;
        int n=s.size();
        ll sum=0,ans=0;
        for(int i=0;i<n;i++){
    
            ans += dp[s[i]-'a'][sum];
            sum += val[s[i]-'a'];
            dp[s[i]-'a'][sum]++;
        }
        cout<<ans;
        return 0;
    }