AtCoder Regular Contest 048 C - 足の多い高橋君
解法
解説スライドを見るとわかりやすいです。
まず, 配列 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; }