AtCoder Beginner Contest 009

Submission #726812

Source codeソースコード

class BitMatrix:
    def __init__(self, n=0, m=0, l=8):
        self.n = n; self.m = m
        self.mat = [[0] * ((m+l-1)/l) for i in xrange((n+l-1)/l)]
        self.l = l
        self.mask = 2**(l**2)-1
        self.nr = range((n+l-1)/l)
        self.mr = range((m+l-1)/l)
 
        self.u = u = 2**l - 1
        self.v = ((u+1)**l - 1) / u
    def copy(self, other):
        self.n = other.n; self.m = other.m
        self.mat = [e[:] for e in other.mat]
        self.l = other.l
        self.mask = other.mask
        self.nr = other.nr
        self.mr = other.mr
        self.u = other.u; self.v = other.v
        return self
 
    def set(self, i, j, b):
        l = self.l
        bit = 1 << ((i%l)*l + (j%l))
        self.mat[i/l][j/l] &= self.mask ^ bit
        if b:
            self.mat[i/l][j/l] |= bit
        return self
    def setI(self):
        assert self.n == self.m
        l = self.l
        value = (2**((l+1)*l)-1) / (2**(l+1)-1)
        for i in self.nr:
            self.mat[i][i] = value
        return self
    def get(self, i, j):
        l = self.l
        return (self.mat[i/l][j/l] >> ((i%l)*l + (j%l))) & 1
    def __add__(self, other):
        assert self.n == other.n and self.m == other.m
        res = BitMatrix(self.n, self.m, self.l)
        me = self.mat; you = other.mat
        nr = self.nr; mr = self.mr
        for i in nr:
            for j in mr:
                res[i][j] = me[i][j] | you[i][j]
        return res
    def __mul__(self, other):
        assert self.l == other.l
        u = self.u; v = self.v; l = self.l
        def mul(a, b):
            c = 0
            while a and b:
                c ^= (((a & v) * u) & ((b & u) * v))
                a >>= 1; b >>= l
            return c
        res = BitMatrix(self.n, other.m, self.l)
        me = self.mat; you = other.mat
        nr = self.nr
        nro = other.nr; mro = other.mr
        for i in nr:
            for k in nro:
                for j in mro:
                    res.mat[i][j] ^= mul(me[i][k], you[k][j])
        return res
    def __pow__(self, k):
        assert self.n == self.m
        res = BitMatrix(self.n, self.n, self.l).setI()
        me = BitMatrix().copy(self)
        while k:
            if k&1:
                res = res * me
            me = me * me
            k >>= 1
        return res
 
k, m = map(int, raw_input().split())
a = map(int, raw_input().split())
c = map(int, raw_input().split())
if m <= k:
    print a[m-1]
else:
    ans = 0
    for b in xrange(32):
        mat = BitMatrix(k, k, 99)
        bit = 1 << b
        for i in xrange(k):
            if c[i] & bit:
                mat.set(0, i, 1)
        for i in xrange(k-1):
            mat.set(i+1, i, 1)
        res = mat ** (m - k)
        d = 0
        for i in xrange(k):
            if a[i] & bit:
                d ^= res.get(0, k-i-1)
        if d:
            ans |= bit
    print ans

Submission

Task問題 D - 漸化式
User nameユーザ名 tjake
Created time投稿日時
Language言語 Python (2.7.3)
Status状態 TLE
Score得点 0
Source lengthソースコード長 2995 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 100 random_01.txt,random_02.txt,random_03.txt,random_04.txt,random_05.txt,random_06.txt,random_07.txt,random_08.txt,random_09.txt,random_10.txt,random_11.txt,random_12.txt,random_13.txt,random_14.txt,random_15.txt,small_1.txt,small_2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
random_01.txt AC 245 ms 3828 KB
random_02.txt AC 256 ms 3828 KB
random_03.txt AC 59 ms 3580 KB
random_04.txt AC 59 ms 3580 KB
random_05.txt AC 59 ms 3572 KB
random_06.txt AC 81 ms 3832 KB
random_07.txt AC 450 ms 3792 KB
random_08.txt AC 706 ms 3824 KB
random_09.txt AC 1647 ms 3824 KB
random_10.txt TLE
random_11.txt TLE
random_12.txt TLE
random_13.txt TLE
random_14.txt TLE
random_15.txt TLE
sample_1.txt AC 81 ms 3832 KB
sample_2.txt AC 117 ms 3832 KB
sample_3.txt AC 323 ms 3840 KB
small_1.txt AC 238 ms 3836 KB
small_2.txt AC 236 ms 3828 KB