AtCoder Regular Contest 048 C - 足の多い高橋君

問題

　高橋君には足が $N(\le 10^5)$ 本あり、 $i$ 番目の足は $L_i(\le10^9)$ 本の骨が一列に繋がった構造をしている。全ての骨に $0$ または $1$ を書き込むことにし、任意の足2本について片方の足先から胴体を通ってもう一方の足先まで辿って読むと回文になるようにしたとき、文字の書き込み方としてあり得る数を求めよ。

解法

　まず $L_i$ はソートされているものとして考える。次の3つのことが言える。

全ての文字列について先頭 $L_1$ 文字は等しく、これは任意に $0, 1$ を選べる。
各文字列に対して先頭 $L_1$ 文字を取り除いた文字列は回文
2つの異なる文字列に対し「1つ目の文字列の先頭 $L_i$ 文字を取り除いたもの + 2つ目の文字列の先頭 $L_i$ 文字を取り除いたものの反転」が回文

　ここで3つ目の条件は、組み合わせる2つの文字列は2つ目の条件から回文であることがわかっているので、結局「回文と回文を繋げると回文ができる」ということを示している。ここで「長さ $X$ の回文Aと長さ $Y$ の回文Bを繋げて回文ができるとき、AもBも周期 $\mathrm{gcd}(X, Y)$ を持ち、さらにその1周期は回文」である(証明は解説スライドを参照のこと)

　この条件が満たされるように $L_i - L_1$ たちのgcdを取っていけばこれが最小の周期となる。これが回文となるように選べる部分は2で割った切り上げ。先頭 $L_1$ 文字分自由に選べるのと合わせて、2をこれらの数の和で累乗したものが答えとなる。

反省

　48分13秒(2WA)でAC。いろいろ考察していたら(足の長さでソートしてuniqueを取ったとして)一番長い足について、一番短い足の分は任意に取れて、あとは残りの部分が $L_N - L_1$ 文字の回文かつ $L_N - L_2$ 文字の回文かつ $\dots$ かつ $L_N - L_{N - 1}$ の回文になればいいというところまではわかった。つまりだいたい $ans = 2^{L_0 + x}$ という形になっていて $x$ が特定できればいいと考えた。

　サンプルの3つ目をこの形で解くと $x = 5 \times 10^5$ になることがわかって、これはいかにも $10^6 / 2$ っぽい。そして $10^6$ というのは $L_i$ の差分の最小公倍数っぽいなーというのをエスパーして、あとはサンプル1,2も合うように奇数の場合は+1してから2で割るということをして(まぁ回文だしそれっぽい操作だと思った)適当に投げたらAC。完全に考察ではなくエスパーで解いてしまった。多分これはコンテスト後かなんかで一度解説を読んだことがある気がする。

　同じ文字列長のものがあったときの処理が不安でuniqueを取ってしまったが別にこれは必要なかったか。gcd(0, x) = xになるから問題ないんだな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> L(N);
    for (ll i = 0; i < N; i++) {
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    L.erase(unique(L.begin(), L.end()), L.end());

    ll diff_gcd = L[1] - L[0];
    for (ll i = 2; i < L.size(); i++) {
        diff_gcd = gcd(diff_gcd, L[i] - L[i - 1]);
    }

    cout << MODpow(2, L[0]) * MODpow(2, (diff_gcd + 1) / 2) % MOD << endl;
}