Python XORの高速化

Question

前提

N個の2進数が与えられ、すべての排他的論理和を求める問題で、TLEが出ています。
TLEが出ない方法はありませんか？

制約
1 <= N <= 100
1 <= 2進数の大きさ <= 2 ** 1000
追記
TLEの上限は5秒間です

実現したいこと

TLEが出ないコードにしたい

発生している問題・エラーメッセージ

Time Limit Error

該当のソースコード

from sys import stdin
n = int(input())
lis = sorted([int(stdin.readline()[:-1], 2) for _ in range(n)])
x = 0
for i in lis:
    x ^= i
print(x))

試したこと

各桁の1の出現回数が奇数かどうかでその桁を1にするか0にするかを判定するやり方も試しましたがだめでした

追記
上記の処理を実装したコードです

from collections import defaultdict
n = int(input())
dic = defaultdict(int)
for _ in range(n):
    arg = input()
    for i in range(len(arg)):
        if arg[i] == '1':
            dic[len(arg) - i] += 1
x = 0
for i in dic.keys():
    if dic[i] % 2 == 1:
        x += 2 ** (i - 1)
print(x)

補足情報（FW/ツールのバージョンなど）

Python3.7.4

###補足:今回の問題について
皆さん協力ありがとうございます!
関係ないと思って書いてませんでしたが、答えを2のx乗で求めて10**9+7で割った余りを出す処理に問題がありました
pow関数を呼び出して処理を実行すると無事時間内に出来ました!

Comments

[meg_]

> N個の2進数が与えられ、すべての排他的論理和を求める問題で、TLEが出ています。
何の問題でしょうか？出題元を提示できますか？

> TLEが出ないコードにしたい
TLEが出ないのは何秒以内でしょうか？今は何秒かかっていますか？

[ps_aux_grep]

弊環境で試しにN=100，i番目の文字列Aiの長さ|Ai|=1000にしてやってみたところ一瞬で実行完了しました．確かにTLEの上限が気になります．10^6回試行したところ平均10±3[μs]でした．

Pythonの整数の実装は2^30進数を表現する配列で実装されており，int()関数による基数変換も基数が2の累乗であれば入力された文字列の桁数Nに対してO(N)であることが明記されています．

対してBig Integerなどの実装が無い他の言語で基数変換を愚直実装するとO(N^2)が一般的で，基数が2の累乗であるか否かで基数変換を実装しているPythonの恩恵を十分に受けた解答ができていると思うんですけどどうでしょう．

[SiN]

出題元については規約に違反するおそれがあるので控えさせていただきます

TLEの上限は5秒です

恐らく問題の内容的にNが100ですべての文字列の長さが1000に近い状態で与えられるのですが、その状態でも5秒以内に収まりますか？

[meg_]

> 出題元については規約に違反するおそれがあるので控えさせていただきます
それは本質問をteratailに投稿すること自体が規約違反ということでしょうか？

[matukeso]

なんでlisはsortedで作ってるの？
というかそもそもlis自体が要らなくない？

[ps_aux_grep]

> Nが100ですべての文字列の長さが1000に近い状態で与えられるのですが、その状態でも5秒以内に収まりますか？

厳密に各行1000文字どころか最上位ビットを必ず1にして測定し直しても1つ目のコードで0.1ミリ秒，2つ目のコードで72ミリ秒で実行が終わります．先述の原理からも到底1秒以上かかるコードには見えません．

また2つ目のコードの最後にある基数変換が，桁数NとしたときO(N^2)になる基数変換ですね．
これを1つ目のコードのint()で実装されてたら確実にTLEしたでしょう

[SiN]

>それは本質問をteratailに投稿すること自体が規約違反ということでしょうか？
答えや模範解答を乗せる等の他のユーザーの回答の補助をする行為は禁止されています。
こういう問題があったらという体でお願いします。

>これを1つ目のコードのint()で実装されてたら確実にTLEしたでしょう
つまり、問題の制約通りであれば1つ目のコードでTLEが出ないはずということですね

ループを使わないで済む書き方があれば良さそうとも思いましたが、そんな書き方は思いつきませんね

TLEはなぜ起きるのか不思議ですね

[SiN]

>なんでlisはsortedで作ってるの？
小さい値から順に処理するほうが早いと思ってsortedしてます
>というかそもそもlis自体が要らなくない？
lisはどういった理由で要らないのですか？

Answer 1

後学のため余談

2進数文字列からの整数へ変換することに関して

ループを使わないで済む書き方があれば良さそう

ですが，ループは使う必要があります．実質2重ループになるから，O(N^2)と言いました．

Qiita - @square1001 - 超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】

N桁の整数同士の加算はO(N)です．コード中で言うx += 2 ** (i - 1)がO(N)です．

これを回避するために，2の累乗数に限ってはビットのシフト演算を併用することで，任意のビットを立てること(2の累乗数を加算すること)ができます．

a = ''.join([str(random.randint(0, 1)) for _ in range(1000)])
ret = 0
for i, x in enumerate(a[::-1]):
    ret |= (x == '1') << i # O(1)
print(ret)
print(int(a, 2))

Comments

[SiN]

わざわざありがとうございます！
質問なんですが、
(x == '1')の部分はxが文字列'1'の場合、整数1を入れてiビット左シフトした値を足す(論理和)するという解釈で合ってますか？

[ps_aux_grep]

合ってます

Answer 2

XOR演算は交換法則が成り立ち、どんな順序で演算しても結果は同じです。
したがって、ソートは不要です。

リストを作らなければ速いのではありませんか？

n = int(input())
x = 0
for _ in range(n):
    x ^= int(input(), 2)
print(x)

Comments

[SiN]

回答ありがとうございます!
色々と試してみたところ時間以内に収まりました！