Reverse and Compare

---

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

You have a string A=A1A2…An consisting of lowercase English letters.

You can choose any two indices i and j such that 1≤i≤j≤n and reverse substring AiAi+1…Aj.

You can perform this operation at most once.

How many different strings can you obtain?

Constraints

• 1≤|A|≤200,000
• A consists of lowercase English letters.

---

Input

Input is given from Standard Input in the following format:

A

Output

Print the number of different strings you can obtain by reversing any substring in A at most once.

---

Sample Input 1

Copy

aatt

Sample Output 1

Copy

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

---

Sample Input 2

Copy

xxxxxxxxxx

Sample Output 2

Copy

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

---

Sample Input 3

Copy

abracadabra

Sample Output 3

Copy

44 //很简单的一道DP，但是难想到，想到极其简单 dp[i]为前 i 个数的不同串数的话,dp[i] = dp[i-1] + sum[ str[j]!=str[i] ] (1<=j

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5 #define LL long long 6 #define MX 200500 7  8 LL dp[MX]; 9 LL num[26];10 char s[MX];11 12 int main()13 {14     scanf("%s",s+1);15     int len = strlen(s+1);16     dp[0]=1;17     for (int i=1;i<=len;i++)18     {19         dp[i]=dp[i-1];20         for (int j=0;j<26;j++)21         {22             if (s[i]=='a'+j) continue;23             dp[i] += num[j];24         }25         num[ s[i]-'a' ]++;26     }27     printf("%lld\n",dp[len]);28     return 0;29 }