結果

問題 No.1269 I hate Fibonacci Number
ユーザー tpynerivertpyneriver
提出日時 2021-01-11 13:21:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,121 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 168,960 KB
最終ジャッジ日時 2024-11-21 09:02:00
合計ジャッジ時間 24,443 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
63,400 KB
testcase_01 AC 44 ms
56,160 KB
testcase_02 AC 1,367 ms
81,676 KB
testcase_03 AC 51 ms
61,312 KB
testcase_04 AC 53 ms
62,336 KB
testcase_05 AC 50 ms
61,440 KB
testcase_06 AC 52 ms
61,568 KB
testcase_07 AC 52 ms
62,848 KB
testcase_08 AC 49 ms
61,824 KB
testcase_09 AC 52 ms
62,208 KB
testcase_10 AC 51 ms
61,824 KB
testcase_11 AC 51 ms
61,952 KB
testcase_12 AC 53 ms
63,872 KB
testcase_13 AC 58 ms
65,536 KB
testcase_14 AC 1,020 ms
79,104 KB
testcase_15 AC 78 ms
67,968 KB
testcase_16 TLE -
testcase_17 AC 83 ms
67,840 KB
testcase_18 TLE -
testcase_19 AC 536 ms
77,696 KB
testcase_20 AC 228 ms
76,928 KB
testcase_21 AC 1,918 ms
81,128 KB
testcase_22 AC 1,033 ms
79,104 KB
testcase_23 AC 492 ms
77,440 KB
testcase_24 AC 2,333 ms
82,004 KB
testcase_25 AC 306 ms
76,800 KB
testcase_26 AC 73 ms
66,304 KB
testcase_27 AC 45 ms
54,784 KB
testcase_28 AC 79 ms
69,632 KB
testcase_29 AC 156 ms
76,628 KB
testcase_30 AC 58 ms
64,256 KB
testcase_31 AC 1,376 ms
79,872 KB
testcase_32 AC 1,823 ms
82,432 KB
testcase_33 AC 64 ms
67,456 KB
testcase_34 AC 45 ms
55,040 KB
testcase_35 AC 54 ms
62,976 KB
testcase_36 AC 60 ms
66,304 KB
testcase_37 AC 44 ms
54,656 KB
testcase_38 AC 1,200 ms
168,960 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.readline

from collections import deque
class AhoCorasick:
    def __init__(self, patterns):
        self.patterns = patterns
        self.children = [dict()]
        self.N = 1
        self.match = [False]
        self.order = [0]
        """
        例えばで、 self.match に patterns のうちどれかが部分文字列になっているかどうかを格納
        禁止文字列とかの場合 self.match が True だと使えない
        """
        for i in range(len(patterns)):
            self._add(i, patterns[i])
        
        self.failure = [0]*self.N
        self._createfailure()
    
    def _add(self, i, p):
        vn = 0
        for pi in p:
            if pi in self.children[vn]:
                vn = self.children[vn][pi]
            else:
                self.children[vn][pi] = self.N
                self.children.append(dict())
                self.match.append(False)
                vn = self.N
                self.N += 1
        self.match[vn] = True
    def _createfailure(self):
        Q = deque(self.children[0].values())
        while Q:
            vn = Q.pop()
            self.order.append(vn)
            fvn = self.failure[vn]
            self.match[vn] |= self.match[fvn]
            for fpi, vf in self.children[vn].items():
                self.failure[vf] = self.nxt(fvn, fpi)
                self.match[vf] |= self.match[vn]
                Q.appendleft(vf)
    
    def nxt(self, vn, s):
        #vnにsを付け足した時の遷移先
        while True:
            if s in self.children[vn]:
                return self.children[vn][s]
            if not vn:
                return vn
            vn = self.failure[vn]

    def idx(self, p):
        #文字列pのindexを返す
        vn = 0
        for pi in p:
            if pi in self.children[vn]:
                vn = self.children[vn][pi]
            else:
                return -1
        return vn
    
    def getnxttable(self, sigma):
        #[0, sigma) に対して各ノードからの遷移先を求める
        #res[s*self.N + vn] = nxt(vn, s)
        res = [0]*(self.N*sigma)
        for l in self.order:
            for s in range(sigma):
                if s in self.children[l]:
                    res[s*self.N + l] = self.children[l][s]
                else:
                    res[s*self.N + l] = res[s*self.N + self.failure[l]]
        return res
    
    def __repr__(self):
        SS = [None]*self.N
        SS[0] = ''
        Q = deque([0])
        while Q:
            vn = Q.pop()
            for c, vf in self.children[vn].items():
                SS[vf] = f'{SS[vn]} {c}'
                Q.appendleft(vf)
        return '\n'.join(f'{i}:{SS[i]} {self.match[i]}' for i in range(self.N))

N, L, R = map(int, readline().split())
MOD = 10**9+7
Fib = []

a, b = 1, 1
while b <= R:
    Fib.append(b)
    a, b = b, a+b
L -= 1
a, b = 1, 1
while b <= L:
    Fib.remove(b)
    a, b = b, a+b

Fib = [tuple(map(int, str(s))) for s in Fib]
ahc = AhoCorasick(Fib)
M = ahc.N
table = ahc.getnxttable(10)

J = [i for i in range(M) if not ahc.match[i]]
Lj = len(J)
AA = [[0]*Lj for _ in range(Lj)]
Ji = dict()
for jidx in range(Lj):
    Ji[J[jidx]] = jidx
for j in J:
    for s in range(10):
        vf = table[s*M + j]
        if not ahc.match[vf]:
            AA[Ji[vf]][Ji[j]] += 1
    

def mat_dot(A, B):
    assert len(A[0]) == len(B), 'invalid_size'
    
    L = len(A)
    M = len(A[0])
    N = len(B[0])
    
    res = [[0]*N for _ in range(L)]
    
    for i in range(L):
        for j in range(N):
            a = 0
            for k in range(M):
                a = (a+A[i][k]*B[k][j]) % MOD
            res[i][j] = a
            
    return res

def mat_pow(A, x):
    N = len(A)
    res = [[0]*N for _ in range(N)]
    for i in range(N):
        res[i][i] = 1
    for i in range(x.bit_length()):
        if 2**i & x:
            res = mat_dot(res, A)
        A = mat_dot(A, A)
    return res
    
dp = [[0] for _ in range(Lj)]
dp[0] = [1]

dp = mat_dot(mat_pow(AA, N), dp)

ans = MOD-1
for d in dp:
    ans = (ans + d[0])%MOD
print(ans)
0