結果

問題 No.2810 Have Another Go (Hard)
ユーザー navel_tos
提出日時 2024-07-16 19:10:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 8,683 bytes
コンパイル時間 1,466 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 137,580 KB
最終ジャッジ日時 2024-07-16 19:11:53
合計ジャッジ時間 28,069 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 29 RE * 9 TLE * 23
権限があれば一括ダウンロードができます

ソースコード

diff #

#yukicoder 2810 Have Another Go(Hard)

'''
1. ライブラリの登録
'''
#kitamasa法 隣接k項間漸化式の特定項を算出する
#F(x): [P0,P1, ... , Pk-1]   Px: Ax=sum(Pi*Ai) [0<=i<x] としたときの定数項
#D[x]: F(k)の隣接項、 A[k]=D[0]A[k-K]+D[1]A[k-K+1]+ ・・・ +D[K-1]A[k-1] を満たす定数項
class kitamasa:
    def __init__(self,k,D,A0,MOD='Large'):  #Ak = sum(Di * Ak-K+i) [0<=i<k]
        self._k=k; self._D=D; self._MOD=MOD if isinstance(MOD,int) else 9*10**18
        self._A=[A0]+[0]*(k-1)  #初項からA[k-1]までを自動計算  困る場合は編集を
        for i in range(k-1,0,-1):
            for x in range(k): self._A[k-i]+=D[x]*self._A[x-i]; self._A[k-i]%=self._MOD
    def add(self,F):  #F(N)→F(N+1)に遷移
        S=[0]+[F[i] for i in range(self._k-1)]; P=F[self._k-1]
        for i in range(self._k): F[i]=(P*self._D[i]+S[i])%self._MOD
        return F
    def mul(self,F):  #F(N)→F(2*N)に遷移
        S,T=F[:],[0]*self._k
        for i in range(self._k):
            for x in range(self._k): T[x]+=F[i]*S[x]; T[x]%=self._MOD
            S=self.add(S)
        return T
    def get(self,F):  #F(N)の一般項を取得
        return sum(self._A[i]*F[i]%self._MOD for i in range(self._k))%self._MOD


#行列累乗  1行N列の行列は[[1, 2, ...]] と2重括弧に自動変換するので注意
class matrix_pow:
    def __init__(self,MOD=998244353): self._MOD=MOD
    def eye(self,N):  #単位行列の作成
        return [[1 if i==j else 0 for j in range(N)] for i in range(N)]
    def add(self,A,B):  #行列の加算
        if isinstance(A[0],int): A=[A]
        if isinstance(B[0],int): B=[B]
        assert len(A)   ==len(B),    'not same size'
        assert len(A[0])==len(B[0]), 'not same size'
        nG=[[0]*max(len(A[i]) for i in range(len(A))) for _ in range(len(A))]
        for h in range(len(nG)):
            for w in range(len(nG[h])):
                if len(A[h])<w: nG[h][w]+=A[h][w]
                if len(B[h])<w: nG[h][w]+=B[h][w]
                nG[h][w]%=self._MOD
        return nG
    def mul(self,A,B):  #行列積  L行M列 * M行N列 = L行N列
        if isinstance(A[0],int): A=[A]
        if isinstance(B[0],int): B=[B]
        assert len(A[0])==len(B),    'cannot calcurate'
        nG=[[0]*max(len(B[i]) for i in range(len(B))) for _ in range(len(A))]
        for h in range(len(nG)):
            for w in range(len(nG[0])):
                for x in range(len(A[0])):
                    nG[h][w]+=A[h][x]*B[x][w]%self._MOD; nG[h][w]%=self._MOD
        return nG

'''
2. 愚直解の定義
'''
#愚直解
def brute(N, M, Ci):
    MOD = 998244353
    dp = [1] + [0] * N * M
    d2 = [1] + [0] * N * M
    for i in range(N * M):
        if i % N == Ci:
            dp[i] = 0
        for k in range(1, 7):
            dp[min(N * M, i + k)] += dp[i]
            dp[min(N * M, i + k)] %= MOD
            d2[min(N * M, i + k)] += d2[i]
            d2[min(N * M, i + k)] %= MOD
    return (d2[-1] - dp[-1]) % MOD

#A[i][j]: (1 + 0)N - 5 ~ (1 + 0)N - 0のうちはじめて踏んだマスである(1 + 0)N - iから始め、
#         (1 + M)N - 5 ~ (1 + M)N - 0のうちはじめて踏んだマスである(1 + M)N - jで終わる
#         移動経路のうち、Ci mod Nを踏まない場合の数
def brute_matrix(N, M, Ci):
    MOD = 998244353
    A = [[0] * 6 for _ in range(6)]
    for i in range(6):
        for j in range(6):
            dp = [0] * ((1 + M) * N + 1)
            dp[N - i] = 1
            for k in range(N - i, (1 + M) * N):
                if k in range((1 + M) * N - 5, (1 + M) * N - j):
                    dp[k] = 0
                if k % N == Ci:
                    dp[k] = 0
                for L in range(1, 7):
                    if k + L > (1 + M) * N: continue
                    dp[k + L] += dp[k]
                    dp[k + L] %= MOD
            A[i][j] = dp[(1 + M) * N - j]
    return A



'''
3. 入力受取と各種初期設定  kitamasa法まわりを設定
'''
N, M, K = map(int, input().split())
C = list(map(int, input().split()))
MOD = 998244353
kit = kitamasa(6, [1] * 6, 1, MOD)
MP = matrix_pow(MOD)
def calc_move(x):  #マス0から開始して、ちょうどマスxに到達するときの寄与
    F = [1, 0, 0, 0, 0, 0]
    for i in bin(x)[2:]:
        F = kit.mul(F)
        if i == '1': F = kit.add(F)
    return F

def calc_dict(x_list):  #計算したい「ちょうどxマス」の一覧を渡す。全部計算する
    #1. ソートしてから重複を削除
    x_list = sorted(x_list)
    x2 = []
    while x_list:
        x = x_list.pop()
        if len(x2) == 0 or x2[-1] != x:
            x2.append(x)

    #2. 計算
    sub = dict()
    back = 0
    F = [1, 0, 0, 0, 0, 0]
    while x2:
        now = x2.pop()
        assert back <= now
        diff = now - back
        if diff < 40:  #毎回再生成はコストが重いので、addで歩ける範囲は歩く
            for _ in range(diff): F = kit.add(F)
        else:
            F = calc_move(now)
        sub[now] = kit.get(F)
        back = now
    return sub


#sub[i]: ちょうどiマス目に止まる場合の数 を前計算しておく。行列Aを返す。
#A[i][j]: (1 + 0)N - 5 ~ (1 + 0)N - 0のうちはじめて踏んだマスである(1 + 0)N - iから始め、
#         (1 + M)N - 5 ~ (1 + M)N - 0のうちはじめて踏んだマスである(1 + M)N - jで終わる
#         移動経路のうち、Ci mod Nを踏まない場合の数
def calc_matrix(Ci, sub):
    #Nが小さいときは愚直な計算でよい  O(N * 6^3)
    if N < 12:
        return brute_matrix(N, 1, Ci)

    #Nが大きい場合のみを考える
    assert N >= 12
    A = [[0] * 6 for _ in range(6)]
    for i in range(6):
        #dp[x]: N - iマス目から始めて、ちょうど2 * N - xマス目に止まる場合の数。
        #       ただし Ci mod Nマス目には止まらない
        #       特に x <= 5: 2 * N - (0 ~ 5)ではじめて止まったマスが2 * N - x
        dp = [0] * 11

        #i == 5, Ci == N - 5の場合は例外処理(常に0になる)
        if i == 5 and Ci == N - 5: continue

        #(N - 5 <=) N - i <= t <= 2 * N - (10 ~ 5) (<= 2 * N - 5),
        #t % N == Ci となるtは高々1個である。この性質を活かしてdp[5 ~ 10]を埋める
        t = Ci if N - 5 < Ci else N + Ci
        for x in range(5, 11):
            if N - i <= t <= 2 * N - x:
                d1 = t - (N - i)
                d2 = (2 * N - x) - t
                dp[x] = sub[d1 + d2] - sub[d1] * sub[d2]
                dp[x] %= MOD
            else:
                dp[x] = sub[(2 * N - x) - (N - i)]

        #もらうdpでdp[0:5]を埋める
        for x in range(5):
            if (-x) % N == Ci: continue
            for k in range(1, 7):
                y = x + k  #元々のマス
                if y <= 5: continue
                dp[x] += dp[y]
                dp[x] %= MOD

        #A[i][j]に反映
        for j in range(6):
            A[i][j] = dp[j] % MOD
    return A
                
            
#calc_matrixで必要な値を列挙する
def listup(C):
    x_list = []
    for Ci in C:
        for i in range(6):
            t = Ci if N - 5 < Ci else N + Ci
            for x in range(5, 11):
                if N - i <= t <= 2 * N - x:
                    d1 = t - (N - i)
                    d2 = (2 * N - x) - t
                    x_list.append(d1)
                    x_list.append(d2)
                    x_list.append(d1 + d2)
                else:
                    x_list.append((2 * N - x) - (N - i))
    return x_list


#計算を実行
def solve(N, M, C):
    #1. subを前計算  包除で使いたいのでN * M - (0 ~ 5)も計算する
    sub = calc_dict([N * M - i for i in range(6)] + listup(C))

    #2. 包除元を計算: N * Mマス以降に到達する場合の数
    dp = [sub[N * M - i] for i in range(6)]
    base = dp[0]
    for i in range(1, 6):
        base += dp[i] * (6 - i)  #N * Mマス目以降に到達する場合の数
        base %= MOD

    #3. 行列累乗を実行  Ciを踏まずにN * Mマス以降に到達する場合の数を計算
    for Ci in C:
        A = calc_matrix(Ci, sub)
        E = MP.eye(6)
        for i in bin(M)[2:]:
            E = MP.mul(E, E)
            if i == '1': E = MP.mul(E, A)
        dp = MP.mul([[1, 0, 0, 0, 0, 0]], E)[0]
        for i in range(5, 0, -1):
            if (-i) % N == Ci:
                dp[i] = 0
            for k in range(1, 7):
                dp[max(0, i - k)] += dp[i]
                dp[max(0, i - k)] %= MOD

        print((base - dp[0]) % MOD)
            
    
solve(N, M, C)
0