結果
問題 |
No.1142 XOR と XOR
|
ユーザー |
|
提出日時 | 2025-03-21 15:53:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 1,675 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,724 KB |
実行使用メモリ | 149,468 KB |
最終ジャッジ日時 | 2025-03-21 15:53:58 |
合計ジャッジ時間 | 8,306 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import os,sys,random,threading from random import randint,choice,shuffle from copy import deepcopy from io import BytesIO,IOBase from types import GeneratorType from functools import lru_cache,reduce from bisect import bisect_left,bisect_right from collections import Counter,defaultdict,deque from itertools import accumulate,combinations,permutations from heapq import heapify,heappop,heappush from typing import Generic,Iterable,Iterator,TypeVar,Union,List from string import ascii_lowercase,ascii_uppercase,digits from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf from decimal import Decimal,getcontext from sys import stdin, stdout, setrecursionlimit input = lambda: sys.stdin.readline().rstrip("\r\n") MI = lambda :map(int,input().split()) li = lambda :list(MI()) ii = lambda :int(input()) mod = int(1e9 + 7) #998244353 inf = 1<<60 py = lambda :print("YES") pn = lambda :print("NO") inv=pow(2,mod-2,mod) def fwt(f,op): n = len(f) l_, k = 2, 1 while l_ <= n: for i in range(0, n, l_): for j in range(k): f[i+j],f[i+j+k]=(f[i+j]+f[i+j+k])*op%mod,(f[i+j]-f[i+j+k])*op%mod l_, k = l_ << 1, k << 1 return f def xorconvolution(a,b): #xor卷积 fa=fwt(a[:],1);fb=fwt(b[:],1) for i in range(len(a)): fa[i]=fa[i]*fb[i]%mod return fwt(fa,inv) _,_,k=li() n=12 a=li() b=li() def cal(a): pa=[0] for i in a: pa.append(pa[-1]^i) ca=[0]*(1<<n) for i in pa: ca[i]+=1 xa=xorconvolution(ca,ca) xa[0]-=len(pa) for i in range(len(xa)): xa[i]=xa[i]*inv%mod return xa res=xorconvolution(cal(a),cal(b)) print(res[k]%mod)