#643676 (PyPy3) No.184 たのしい排他的論理和(HARD)

提出ソース

結果

問題	No.184 たのしい排他的論理和(HARD)
ユーザー	None
提出日時	2021-04-02 23:45:44
言語	PyPy3 (7.3.15)
結果	AC
実行時間	3,255 ms / 5,000 ms
コード長	11,014 bytes
コンパイル時間	274 ms
コンパイル使用メモリ	82,432 KB
実行使用メモリ	211,784 KB
最終ジャッジ日時	2024-06-06 08:49:47
合計ジャッジ時間	55,585 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 54,528 KB
testcase_01	AC	35 ms 54,912 KB
testcase_02	AC	49 ms 65,536 KB
testcase_03	AC	43 ms 61,824 KB
testcase_04	AC	45 ms 64,128 KB
testcase_05	AC	47 ms 64,016 KB
testcase_06	AC	37 ms 54,528 KB
testcase_07	AC	48 ms 64,256 KB
testcase_08	AC	2,229 ms 168,036 KB
testcase_09	AC	537 ms 94,720 KB
testcase_10	AC	1,819 ms 146,016 KB
testcase_11	AC	1,292 ms 126,108 KB
testcase_12	AC	2,726 ms 183,768 KB
testcase_13	AC	2,937 ms 191,996 KB
testcase_14	AC	1,730 ms 142,248 KB
testcase_15	AC	3,255 ms 207,860 KB
testcase_16	AC	2,536 ms 180,484 KB
testcase_17	AC	2,784 ms 189,316 KB
testcase_18	AC	52 ms 65,920 KB
testcase_19	AC	36 ms 54,400 KB
testcase_20	AC	479 ms 206,008 KB
testcase_21	AC	2,971 ms 211,784 KB
testcase_22	AC	3,006 ms 211,744 KB
testcase_23	AC	54 ms 65,664 KB
testcase_24	AC	55 ms 65,152 KB
testcase_25	AC	54 ms 64,640 KB
testcase_26	AC	48 ms 61,952 KB
testcase_27	AC	54 ms 65,024 KB
testcase_28	AC	1,949 ms 154,072 KB
testcase_29	AC	2,857 ms 187,084 KB
testcase_30	AC	2,356 ms 173,956 KB
testcase_31	AC	2,038 ms 161,204 KB
testcase_32	AC	2,507 ms 181,808 KB
testcase_33	AC	3,150 ms 208,732 KB
testcase_34	AC	3,143 ms 207,240 KB
testcase_35	AC	3,245 ms 210,872 KB
testcase_36	AC	3,212 ms 210,368 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#########################################################
"""

##　和＆積（MOD無し）　#######################################

def mul2(a,b): return a*b

def add2(a,b): return a+b

def mul_inv2(a): return 1/a

def add_inv2(a): return -a

def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)])

###########################################################

##　和＆積（MOD有り）　#######################################
MOD=10**9+7

def mul2(a,b): return a*b%MOD

def add2(a,b): return (a+b)%MOD

def mul_inv2(a): return pow(a,MOD-2,MOD)

def add_inv2(a): return -a%MOD

def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)])

###########################################################

##　論理和＆論理積　#######################################

def mul2(a,b): return a&b

def add2(a,b): return a^b

def mul_inv2(a): return None

def add_inv2(a): return a

mask=(1<<32-1)
def identity(n): return Matrix([[int(i==j)*mask for i in range(n)] for j in range(n)])

###########################################################


"""


#########################################################

class Matrix():
    def __init__(self,A):
        self.H=len(A)
        self.W=len(A[0])
        self._matrix=A
        # for i in range(self.row):
        #     for j in range(self.column):

    def __getitem__(self,item):
        if type(item)==tuple:
            i,j=item
            return self._matrix[i][j]
        else:
            return self._matrix[item]

    def __setitem__(self,item,val):
        i,j=item
        self._matrix[i][j]=val

    def __add__(self,B):
        # assert (self.row,self.column)==(other.row,other.column), "sizes of matrices are different"
        H,W,A=self.H,self.W,self._matrix
        AB=[[0]*W for _ in range(H)]
        for h in range(H):
            for w in range(W):
                AB[h][w]=add2(A[h][w],B._matrix[h][w])
        return Matrix(AB)

    def __mul__(self,other):
        H,W,A=self.H,self.W,self._matrix
        if type(other)==int:
            n=other
            AB=[[(mul2(n,A[i][j])) for j in range(W)] for i in range(H)]
            return Matrix(AB)
        elif type(other)==Vector:
            vec=other
            res=[0]*W
            for i in range(H):
                for j in range(W):
                    res[i]=add2(res[i],mul2(A[i][j],vec[j]))
            return Vector(res)
        else:
            # assert self.column!=other.row, "sizes of matrices are different"
            AB=[[0]*other.W for _ in range(H)]
            for i in range(H):
                for j in range(other.W):
                    temp=0
                    for k in range(W):
                        temp=add2(temp,mul2(A[i][k],other._matrix[k][j]))
                    AB[i][j]=temp
            return Matrix(AB)

    def __truediv__(self,c):
        H,W,A=self.H,self.W,self._matrix
        res=A.copy()
        for h in range(H):
            for w in range(W):
                res[h][w]=mul2(res[h][w],mul_inv2(c))
        return Matrix(res)

    def __floordiv__(self,c):
        H,W,A=self.H,self.W,self._matrix
        res=A.copy()
        for h in range(H):
            for w in range(W):
                res[h][w]=res[h][w]//c
        return Matrix(res)

    def __mod__(self,c):
        H,W,A=self.H,self.W,self._matrix
        res=A.copy()
        for h in range(H):
            for w in range(W):
                res[h][w]=res[h][w]%c
        return Matrix(res)

    def map(self,func):  # act func to all elements
        H,W,A=self.H,self.W,self._matrix
        res=A.copy()
        for h in range(H):
            for w in range(W):
                res[h][w]=func(res[h][w])
        return Matrix(res)

    def __pow__(self,m):
        # assert self.column==self.row, "the size of row must be the same as that of column"
        H,W,A=self.H,self.W,self._matrix
        res=identity(H)
        while m:
            if m%2==1:
                res=res*self
            self=self*self
            m>>=1
        return res

    def det(self):
        H,W,A=self.H,self.W,self._matrix
        n=H
        res=1
        for i in range(n):
            if A[i][i]==0:
                res=add_inv2(res)
                for k in range(i+1,n):
                    if A[k][i]!=0:
                        A[i],A[k]=A[k],A[i]
                        break
                else:
                    return 0
            c=mul_inv2(A[i][i])
            for j in range(i+1,n):
                l=mul2(c,A[j][i])
                for k in range(i+1,n):
                    A[j][k]=add2(A[j][k],add_inv2(l*A[i][k]))
        for i in range(n):
            res=mul2(res,A[i][i])
        return res

    def __eq__(self,other):
        if type(other)==Matrix:
            return self._matrix==other._matrix
        return False

    def __ne__(self,other):
        if type(other)==Matrix:
            return self._matrix!=other._matrix
        return True

    def __len__(self):
        return self.H

    def __str__(self):
        res=[]
        for i in range(self.H):
            for j in range(self.W):
                res.append(str(self._matrix[i][j]))
                res.append(" ")
            res.append("\n")
        return "".join(res)

    def __hash__(self):
        res=[]
        for h in range(self.H):
            for w in range(self.W):
                res.append(self._matrix[h][w])
        return tuple(res)

    def count(self,x):
        cnt=0
        for h in range(self.H):
            for w in range(self.W):
                cnt+=(self._matrix[h][w]==x)
        return cnt

    def rank(self):
        """ = dimension"""
        H,W,A=self.H,self.W,self._matrix
        A=[self._matrix[i][:] for i in range(H)]
        rank=0
        p,q=[],[]
        for w in range(W):
            for h in range(rank,H):
                if A[h][w]!=0:
                    break
            else:
                q.append(w)
                continue
            if w==W: return -1,[],[]
            p.append(w)
            A[rank],A[h]=A[h],A[rank]
            inv=mul_inv2(A[rank][w])
            for ww in range(W):
                A[rank][ww]=mul2(A[rank][ww],inv)
            for h in range(H):
                if h==rank: continue
                c=add_inv2(A[h][w])
                for ww in range(W):
                    A[h][ww]=add2(A[h][ww],mul2(c,A[rank][ww]))
            rank+=1
        return rank



class Vector():
    def __init__(self,vec):
        self.n=len(vec)
        self._vector=vec

    def __getitem__(self,item):
        return self._vector[item]

    def __setitem__(self,item,val):
        self._vector[item]=val

    def __neg__(self):
        n,vec=self.n,self._vector
        res=[]
        for x in vec:
            res.append(add_inv2(x))
        return Vector(res)

    def __add__(self,vec2):
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=add2(res[i],vec2[i])
        return Vector(res)

    def __sub__(self,vec2):
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=add2(res[i],add_inv2(vec2[i]))
        return Vector(res)

    def __mul__(self,vec2):
        n,vec=self.n,self._vector
        if type(vec2)!=int:
            res=vec.copy()
            for i in range(n):
                res[i]=mul2(res[i],vec2[i])
            return Vector(res)
        else:
            res=[mul2(vec2,vec[i]) for i in range(n)]
            return Vector(res)

    def __truediv__(self,c):
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=mul2(res[i],mul_inv2(c))
        return Vector(res)

    def __floordiv__(self,c):
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=res[i]//c
        return Vector(res)

    def __mod__(self,c):
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=res[i]%c
        return Vector(res)

    def map(self,func):  # act func to all elements
        n,vec=self.n,self._vector
        res=vec.copy()
        for i in range(n):
            res[i]=func(res[i])
        return Vector(res)

    def __eq__(self,other):
        if type(other)==Vector:
            return self._vector==other._vector
        return False

    def __ne__(self,other):
        if type(other)==Vector:
            return self._vector!=other._vector
        return True

    def __len__(self):
        return self.n

    def __str__(self):
        res=[]
        for i in range(self.n):
            res.append(str(self._vector[i]))
            res.append(" ")
        return "".join(res)

    def __hash__(self):
        return tuple(self._vector)

    def count(self,x):
        cnt=0
        for a in self._vector:
            cnt+=(a==x)
        return cnt


def linear_equations(mat,vec):
    """
    return
        (dim, [x,y,z], [[a0,b0,c0],[a1,b1,c1],...])

    which means,

        solution = (x,y,z)+t0*(a0,b0,c0)+t1*(a1,b1,c1)+...

    Cation: float
    """
    H,W=len(mat),len(mat[0])
    # assert H == len(vec)
    aug=[mat[i]+[vec[i]] for i in range(H)]
    rank=0
    p,q=[],[]
    for w in range(W+1):
        for h in range(rank,H):
            if aug[h][w]!=0:
                break
        else:
            q.append(w)
            continue
        if w==W: return -1,[],[]
        p.append(w)
        aug[rank],aug[h]=aug[h],aug[rank]
        inv=mul_inv2(aug[rank][w])
        for ww in range(W+1):
            aug[rank][ww]=mul2(aug[rank][ww],inv)
        for h in range(H):
            if h==rank: continue
            c=add_inv2(aug[h][w])
            for ww in range(W+1):
                aug[h][ww]=add2(aug[h][ww],mul2(c,aug[rank][ww]))
        rank+=1
    dim=W-rank
    sol=[0]*W
    for h in range(rank):
        sol[p[h]]=aug[h][-1]
    vecs=[[0]*W for _ in range(dim)]
    for h in range(dim):
        vecs[h][q[h]]=1
    for h in range(dim):
        for w in range(rank):
            vecs[h][p[w]]=add_inv2(aug[w][q[h]])
    return dim,sol,vecs


###########################################################
def example():
    global input
    example=iter(
        """
3 3
1 0 0
1 0 1
0 0 1
        """
            .strip().split("\n"))
    input=lambda:next(example)


##　和＆積（MOD有り）　#######################################
MOD=2


def mul2(a,b): return a*b%MOD


def add2(a,b): return (a+b)%MOD


def mul_inv2(a): return pow(a,MOD-2,MOD)


def add_inv2(a): return -a%MOD


def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)])

def bit_rep(bit,N):
    return format(bit, "0" + str(N) + "b")


###########################################################

import sys
input=sys.stdin.readline

# example()

N=int(input())
A=list(map(int, input().split()))
mat=[]
for a in A:
    vec=[]
    for b in bit_rep(a,62):
        vec.append(int(b))
    mat.append(vec)

mat=Matrix(mat)
rank=mat.rank()
print(pow(2,rank))

yukicoder

結果

テストケース

ソースコード