AGC-019-B Reverse and Compare

■■■問題■■■

英小文字からなる文字列 A=A1A2 ・・・ An があります。

あなたは 1 <= i <= j <= n であるような任意の2つの添字 i,j を選び、
Aのうち部分文字列 AiAi+1 ・・・ Aj を反転することができます。

この操作は1回まで行うことができます。
これによって得られる文字列は何通りあるでしょうか？

■■■入力■■■

A

●1 <= |A| <= 20万
●Aは英小文字からなる

■■■出力■■■

Aのうち任意の部分文字列を1回まで反転することによって、
何通りの文字列が得られるか出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("aatt");
            //5
            //得られる文字列は
            //aatt（何もしない）、
            //atat（A[2..3] を反転）、
            //atta（A[2..4] を反転）、
            //ttaa（A[1..4] を反転）、
            //taat（A[1..3] を反転）です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("xxxxxxxxxx");
            //1
            //どの部分文字列を反転しても、結果はxxxxxxxxxxです
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("abracadabra");
            //44
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string A = InputList[0];

        long Answer = 1 + Derive_nC2(A.Length);
        foreach (var Each in A.ToCharArray().GroupBy(X => X)) {
            if (Each.Count() <= 1) continue;
            Answer -= Derive_nC2(Each.Count());
        }
        Console.WriteLine(Answer);
    }

    //nC2を返す
    static long Derive_nC2(long pN)
    {
        return pN * (pN - 1) / 2;
    }
}

解説

ABCという文字列で考えると、ABC,ACB,BAC,CAB の4通りだと分かります。
これは、1 + 3C2 です。

ABCDEFGHIJという文字列で考えると、
(1 + 10C2) 通りだと分かります。

AABBという文字列で考えると、
(1 + 4C2 - 2C2 - 2C2) 通りだと分かります。
元々の文字列の1通りと、
始点と終点 (始点 != 終点) を指定しての回文作成が 4C2 通りあり
同じ文字列同士で始点と終点となる場合が、Aで2C2通り、Bで2C2通りだからです。

引き算している理由ですが、
同じ文字列同士で始点と終点となる場合は、
内部に同じ文字列同士でない始点と終点を内包してたら、別途カウントしているので、
回文作成の場合の数から引く必要があるからです。

ABCBCAAABDという文字列で考えると、
(1 + 10C2 - 4C2 - 3C2 - 2C2) 通りだと分かります。
元々の文字列の1通りと、
始点と終点 (始点 != 終点) を指定しての回文作成が 10C2 通りあり
同じ文字列同士での始点と終点となる場合が、Aで4C2通り、Bで3C2通り、Cで2C2通りだからです。