Maximum Palindromes [HourRank 25 B]

https://www.hackerrank.com/contests/hourrank-25/challenges/maximum-palindromes

アルファベット小文字からなる文字列Sがある。
これについて以下のクエリに答えよ。

S[L..R]の文字を上手く取って入れ替えることで回文を作る。
この回文のうち長さが最長のものは何通り作れるか（mod10^9+7）。

前提知識

• 累積和
• 同じものを含む順列
• mod

解法

まずは、区間に文字がそれぞれ何個あるか高速に求められるように累積和を作っておこう。
各文字の個数をそれぞれ求めるのに「sm[c][i] := 文字cが区間[0,i]に何個あるか」という累積和を作る典型がある。
これをやろう。

クエリ部分を考えよう。
回文であるためには「全ての文字の個数が偶数個、または、1つだけ奇数個」の必要がある。
　
奇数個の文字が回文の中心となるので、奇数個の文字がある場合は、別途中心の組合せを求める必要がある。
奇数個の文字のうち1つは回文の中心となるか、使われないかであるため、中心の組合せを求めてしまった後は、
取り除いて考えることができる。

全ての文字が偶数個となったので、それ以外を決めていこう。
中心の左側を決めることで右側も一意に定まるので、左側の組み合わせ数を数えよう。
片方だけを決めるので全ての文字について半分の個数の並び替えだけを考えればいい。
これは丁度同じものを含む順列になっている
その為、総和の階乗/(各文字の個数の階乗の総積)が組み合わせ数となる。

string S; int Q, N;
int sm[26][101010];
Comb<mint, 101010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> Q;
    N = S.length();

    rep(i, 0, N) sm[S[i] - 'a'][i] = 1;
    rep(c, 0, 26) rep(i, 1, N) sm[c][i] += sm[c][i - 1];

    rep(q, 0, Q) {
        int L, R; cin >> L >> R;
        L--; R--;

        vector<int> cnt(26, 0);
        rep(c, 0, 26) {
            cnt[c] = sm[c][R];
            if (L) cnt[c] -= sm[c][L - 1];
        }

        vector<int> odd;
        rep(c, 0, 26) if (cnt[c] % 2 == 1) odd.push_back(c);

        mint ans = 1;

        if(0 < odd.size()) {
            ans = mint((int)odd.size());
            fore(c, odd) cnt[c]--;
        } 

        int sum = 0;
        rep(c, 0, 26) sum += cnt[c] / 2;
        ans *= com.fac[sum];
        rep(c, 0, 26) ans *= com.ifac[cnt[c] / 2];

        printf("%d\n", ans.get());
    }
}