結果

問題 No.206 数の積集合を求めるクエリ
コンテスト
ユーザー mkawa2
提出日時 2020-01-28 11:11:26
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,467 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 96,052 KB
最終ジャッジ日時 2024-09-15 08:17:46
合計ジャッジ時間 21,367 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

import numpy as np

def main():
    # aa=[3,4,6]とbb=[1,2,5,7]とする
    # aaに要素iが存在すればa[i]に1を立てる
    # a=[0,0,0,1,1,0,1] b=[0,1,1,0,0,1,0,1]
    # これにFFTをかけると「和(i+j)がある数になる組合せの個数」が分かる
    # しかし今回欲しいのは「差(i-j)がある数になる組合せの個数」
    # そのためにbを反転してb[j]をb[n-j]にする
    # すると「i-j+nがある数になる組合せの個数」が分かる
    # bbの要素jにvを足したときaaの要素iと等しくなるのはi=j+vのとき
    # すなわちi-j=vのとき
    # よってi-j+n=v+nなので、i-j+nがv+nになるときの個数を答えればよい
    def bitarr(aa):
        res = np.zeros(n+1,'i8')
        for a in aa: res[a] = 1
        return res

    l, m, n = MI()
    aa = LI()
    bb = LI()
    q = II()
    a = bitarr(aa)
    b = bitarr(bb)
    b = b[::-1]
    s=(n+1)*2
    cc = (np.fft.irfft(np.fft.rfft(a, s) * np.fft.rfft(b, s)) + 0.5).astype(np.int)
    for i in range(n,n+q):
        print(cc[i])

main()
0