小数が出てくるとややこしいが、$b_i=\frac{a_i}{2}$ として、$X=b_i \times (2p+1)$ としてしまえばいい。
これで、以下の2つを満たせばよいことがわかりやすくなる。
なので、とりあえず全ての $b_i$ の最小公倍数を求めて、それが $b_i$ で割ると全て奇数となるか確認する。
1つでも偶数となるものがあれば、達成不可能。
全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。
2数 $n,m$ の最小公倍数は、最大公約数を $g$ として $\frac{nm}{g}$ で求められる。3数以上なら、これを繰り返し適用しつづければよい。
ただし $b_i$ が互いに素だと、最小公倍数は繰り返している内にとてつもなく大きくなってしまう。途中で $M$ 以上になった時点で $M$ 以下の半公倍数は不可能なので、0を出力して即終了する。
from fractions import gcd
def solve(n, m, aaa):
lcm = 1
for a in aaa:
a //= 2
lcm *= a // gcd(lcm, a)
if lcm > m:
return 0
for a in aaa:
if int(lcm / a) == lcm / a:
return 0
return (m // lcm + 1) // 2
n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, m, aaa))
最初から異なっている要素数が $k$ 個の時、異なっている箇所にある $C_i$ のうち、
という操作を経て、$S$ と $T$ が一致する。 なので、$C_i$ の小さい方から処理するのが最適である。
とりあえず $C_i$ を昇順にソートし、indexを0から振り直す。
i 0 1 2 3 4 C 25 52 67 72 79
（注: 解説pdfとは逆順で考えを進めている）
1つずつ $f(S,T)$ を求めるという視点から、各 $C_i$ が何回足されるかという視点に転換する。
$C_i$ について考える時、$C_i$ より小さい要素、$C_i$、$C_i$ より大きい要素に分けてそれぞれのパターン数を考える。
まず、$C_i$ より小さい要素は $i$ 個あるが、$S_i,T_i$ が0,1のそれぞれどちらを取るかで1つあたり4通り、計 $4^i$ 通りある。 この部分は、最初に異なっていようと、$i$ 番目を変更する頃には先に操作されて同じになっているので、初期状態を気にしなくてよい。
$C_i$ が足される場合、要素 $i$ は異なっていることは確定。(0,1)(1,0)の2通りある。
$C_i$ より大きい要素は全部で $N-i-1$ 個あるが、コストに関わってくるので初期状態で異なっている箇所の数 $k$ を気にする必要がある。
$k$ を固定すると、パターン数は $N-i-1$ 個から $k$ 個を選ぶので、${}_{N-i-1}C_k$、 各要素に付き、同じ要素は(0,0)(1,1)、違う要素は(0,1)(1,0)でそれぞれ2パターンずつあるので $2^{N-i-1}$。
コストは1パターンあたり $C_i(k+1)$。（$k$ のカウントに $i$ 番目は入っていないため、1足す）
これを $k=0～N-i-1$ までの総和を取るので、コスト総計は $\displaystyle 4^i \times 2 \times 2^{N-i-1} \times \sum_{k=0}^{N-i-1}{{}_{N-i-1}C_k \times C_i \times (k+1)}$ となる。
しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。
ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r(r+1)}=2^{n-1}(n+2)$ となることを利用できる。
よって上の式は、$\displaystyle 4^i \times 2 \times 2^{N-i-1} \times 2^{N-i-2} \times (N-i+1) \times C_i$ となり、 2の冪をまとめると上手い具合に合成されて $4^{N-1} \times (N-i+1) \times C_i$ となる。
よって、これを $i=0～N-1$ まで合計すれば、答えとなる。
n = int(input())
ccc = list(map(int, input().split()))
ccc.sort()
MOD = 10 ** 9 + 7
ans = 0
others = pow(4, n - 1, MOD)
for i, c in enumerate(ccc):
ans = (ans + others * c * (n - i + 1)) % MOD
print(ans)
A 0 2 1 B 1 2 3 (k, X) = (1, 3) のとき、 A 2 1 0 左に1個回転 A' 1 2 3 X=3をXOR でBに一致させることができる
共通の数 $X$ をXORしても、隣り合う要素とのXORは変わらないことがとっかかりとなる。
つまり、$C=\{a_0 \oplus a_1,a_1 \oplus a_2,...,a_{N-1} \oplus a_0\}$ とすると、$A$ にどんな数をXORしても $C$ は不変となる。
よって、$A→C$ と同様に $B→D$ も作ると、「$C$ をいくつずらすと $D$ に一致させることができるか？」と$X$ を除外して $k$ のみに限定して考えることができる。
これは、$D$ を繰り返して2倍の長さにしたものを $D'$ として、$D'$ から $C$ を探す処理に言い換えられる。
数列の各要素を文字と見なして、文字列検索アルゴリズムのローリングハッシュやKMP法を用いることができる。
一致するindex $k$ が見つかれば、$A_k$ と $B_0$ を一致させればよいので、$A_k \oplus X = B_0 → X = A_k \oplus B_0$ より、その $k$ に対しての $X$ を求められる。
def solve(n, aaa, bbb):
ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]
ans = []
# ローリングハッシュ
m = 2147483647
g = 1000000007
s = 0
for c in ccc:
s = (s * g + c) % m
t = 0
for d in ddd:
t = (t * g + d) % m
u = pow(g, n, m) - 1
for i in range(n):
if s == t:
ans.append((i, aaa[i] ^ bbb[0]))
s = (s * g - ccc[i] * u) % m
ans.sort()
return ans
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in ans))