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

問題

arc048.contest.atcoder.jp

解法

解説スライドを見るとわかりやすいです。

AtCoder Regular Contest 048 from AtCoder Inc.

www.slideshare.net

まず, 配列 L の中で, 一番値の小さいものについては, そこに書く数字は何でも大丈夫です(一番値の小さいのが l であるとして, l より長い数字を書き込まなければならないものは, 最初の l 個の数字を l に合わせれば良いので)。

で, 残りの数字をどうするかが問題になります。
ここで, 長さ A, B(A, B > l) の骨について, 特徴を考えてみます。すると,

• A から最初の l 文字をなくしたものは回文(A と l を組み合わせることを考えれば明らか)
• 「A から最初の l 文字をなくしたもの」と「B から最初の l 文字をなくしたものをひっくり返したもの」を組み合わせたのは回文

残りの文字に関しては, l 文字をなくして考えると, 以下のようになります(A > B としています)。

この操作は, どちらかの回文の長さが 0 になるまで続きます。この操作はユークリッドの互除法そのものなので, 最後に出来る回文の長さは A と B の最大公約数と等しいです。
以上により, A と B に対する回文の自由度は gcd(A, B) であることがわかりました。
これがすべての長さに対して成り立つので, 結局 ((全体の gcd) + 1)/2 + l だけの自由度があることになります。

const ll MOD = 1e9+7;

ll pow_mod(ll x, ll p) {
    if (x==0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p%2) return x*pow_mod(x, p-1)%MOD;
    ll tmp = pow_mod(x, p/2);
    return tmp*tmp%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> L(N);
    for (int i = 0; i < N; i++) cin >> L[i];
    sort(L.begin(), L.end());
    ll p = L[0];
    for (int i = 0; i < N; i++) L[i] -= p;
    int gcd = 0;
    for (int i = 0; i < N; i++) {
        gcd = __gcd(gcd, L[i]);
    }
    p += (gcd+1)/2;
    cout << pow_mod(2, p) << endl;
    return 0;
}