結果

問題 No.2134 $\sigma$-algebra over Finite Set
ユーザー 👑 KazunKazun
提出日時 2022-11-25 22:56:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,896 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 271,596 KB
最終ジャッジ日時 2024-04-10 04:02:29
合計ジャッジ時間 6,910 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
60,940 KB
testcase_01 AC 203 ms
77,864 KB
testcase_02 AC 193 ms
77,872 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 710 ms
130,864 KB
testcase_07 AC 857 ms
152,828 KB
testcase_08 AC 41 ms
58,888 KB
testcase_09 AC 40 ms
59,648 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Modulo_Vector_Error(Exception):
    pass

class Modulo_Vector:
    def __init__(self,v):
        self.vec=[x%Mod for x in v]
        self.size=len(v)

        #出力
    def __str__(self):
        return str(self.vec)

    def __repr__(self):
        return str(self)

    def __bool__(self):
        return any(self.vec)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return self.__scale__(-1)

    #加法
    def __add__(self,other):
        if self.size!=other.size:
            raise Modulo_Vector_Error("2つのベクトルのサイズが異なります. ({}, {})".format(self.size,other.size))

        v=self.vec
        w=other.vec
        return Modulo_Vector([v[i]+w[i] for i in range(self.size)])

    #減法
    def __sub__(self, other):
        return self+(-other)

    def __rsub__(self, other):
        return (-self)+other

    #乗法
    def __mul__(self,other):
        pass

    def __rmul__(self,other):
        return self.__scale__(other)

    #スカラー倍
    def __scale__(self,r):
        v=self.vec
        v=[r*x for x in v]
        return Modulo_Vector(v)

    #内積
    def inner(self,other):
        if self.size!=other.size:
            raise Modulo_Vector_Error("2つのベクトルのサイズが異なります.({},{})".format(self.size,other.size))

        X=0
        v=self.vec
        w=other.vec

        for i in range(self.size):
            X+=v[i]*w[i]%Mod
        return X

    #累乗
    def __pow__(self,n):
        pass

    #等号
    def __eq__(self,other):
        return (self.vec==other.vec)

    def __len__(self):
        return self.size

    #不等号
    def __neq__(self,other):
        return not(self==other)

    def __getitem__(self,index):
        assert isinstance(index,int)
        return self.vec[index]

    def __setitem__(self,index,val):
        assert isinstance(index,int)
        self.vec[index]=val

class Modulo_Vector_Space:
    def __init__(self, dim):
        """ 次元が dim のベクトル空間の部分空間を生成する.

        """

        self.dim=dim
        self.basis=[]
        self.__ind=[]

    def __contains__(self, v):
        for i,u in zip(self.__ind, self.basis):
            v-=v[i]*u
        return not bool(v)

    def add_vectors(self, *S):
        for v in S:
            assert len(v)==self.dim
            for i,u in zip(self.__ind, self.basis):
                v-=v[i]*u

            if bool(v):
                for j in range(self.dim):
                    if v[j]:
                        self.__ind.append(j)
                        break
                v=pow(v[j], Mod-2, Mod)*v
                self.basis.append(v)

                for k in range(len(self.basis)-1):
                    self.basis[k]-=self.basis[k][j]*v

    def dimension(self):
        return len(self.basis)

    def __le__(self, other):
        for u in self.basis:
            if u not in other:
                return False
        return True

    def __ge__(self, other):
        return other<=self

    def __eq__(self, other):
        return (self<=other) and (other<=self)

    def refresh(self):
        I=sorted(range(len(self.__ind)), key=lambda i:self.__ind[i])
        self.basis=[self.basis[i] for i in I]
        self.__ind=[self.__ind[i] for i in I]

    def projection(self, v):
        for i,u in zip(self.__ind, self.basis):
            v-=v[i]*u
        return v
#==================================================
def solve():
    N,M=map(int,input().split())

    global Mod; Mod=2

    V=Modulo_Vector_Space(N)
    V.add_vectors(Modulo_Vector([1]*N))
    for i in range(M):
        l,*a=list(map(int,input().split()))
        y=Modulo_Vector([0]*N)
        for j in a:
            y[j-1]=1
        V.add_vectors(y)
    return pow(2,V.dimension(),998244353)

#==================================================
print(solve())
0