String Coloring [AtCoder Grand Contest 026 C]

https://beta.atcoder.jp/contests/agc026/tasks/agc026_c

前提知識

• 半分全列挙

考察過程

1. いかにも半分全列挙感がある
2. 前半部分を赤と青に分けた時に、青の文字列を逆にして赤につなげると、全体で作られる赤の文字列ができあがる
3. つまり、後半部分で赤とされるべき文字列と青とされるべき文字列が決定するということ
4. なので、後半部分で赤とされるべき文字列と青とされるべき文字列がそうなるような組合せ数を事前計算しておけば間に合う

解法

https://beta.atcoder.jp/contests/agc026/submissions/2851074

半分全列挙のような感じに解いていこう。
まずは後半部分から計算する。
「cnt[{r,b}] := 後半N文字列を赤の文字列rと青の文字列bに分割する色分けの組み合わせ数」
を計算しよう。これはO(2^N*N)で行える。
　
次に前半部分を全列挙する。
前半部分の赤の文字列がa, 青の文字列がbとする。
すると全体で条件を満たすようにするためには後半は、赤がbの反転、青がaの反転になっている必要がある。
そのため、a,bを作る場合も反転になるように作っていこう。
すると後半部分での組み合わせ数はcnt[{b,a}]となるので、これの総和を取ると答え。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
 
    map<pair<string, string>, int> cnt;
    rep(msk, 0, 1 << N) {
        string a = "";
        string b = "";
        rep(i, 0, N) {
            if (msk & (1 << i)) a += S[i + N];
            else b += S[i + N];
        }
        cnt[{a, b}]++;
    }
 
    ll ans = 0;
    rep(msk, 0, 1 << N) {
        string a = "";
        string b = "";
        rep(i, 0, N) {
            if (msk & (1 << i)) a = S[i] + a;
            else b = S[i] + b;
        }
        ans += cnt[{b, a}];
    }
    cout << ans << endl;
}