結果

問題 No.2807 Have Another Go (Easy)
ユーザー hirayuu_yc
提出日時 2024-07-06 09:04:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,052 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 278,092 KB
最終ジャッジ日時 2024-07-06 09:04:48
合計ジャッジ時間 6,785 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353
def matrix_mul(a,b):
    ret=[[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                ret[i][j]+=a[i][k]*b[k][j]
            if MOD:
                ret[i][j]%=MOD
    return ret

def matrix_pow(x,p):
    if p==0:
        return [[int(i==j) for i in range(len(x))] for j in range(len(x))]
    if p%2==1:
        return matrix_mul(matrix_pow(x,p-1),x)
    half=matrix_pow(x,p//2)
    return matrix_mul(half,half)

def bostan_mori(N,P,Q):
    if N<0:
        return 0
    while N>0:
        U=[0]*(len(P)+len(Q)-1)
        for i in range(len(P)):
            for j in range(len(Q)):
                if j%2==0:
                    U[i+j]+=P[i]*Q[j]
                else:
                    U[i+j]-=P[i]*Q[j]
                U[i+j]%=MOD
        P=U[N%2::2]
        V=[0]*(len(Q)*2-1)
        for i in range(len(Q)):
            for j in range(len(Q)):
                if j%2==0:
                    V[i+j]+=Q[i]*Q[j]
                else:
                    V[i+j]-=Q[i]*Q[j]
                V[i+j]%=MOD
        Q=V[0::2]
        N//=2
    return P[0]//Q[0]%MOD

N,M,k=map(int,input().split())
lst=0
for i in range(6):
    lst+=bostan_mori(N*M-1-i,[1],[1,-1,-1,-1,-1,-1,-1])*(6-i)
C=list(map(int,input().split()))
length=max(0,(M-6)//6)
last=M-length*6
for c in C:
    matrix=[[0]*6 for i in range(6)]
    for i in range(6):
        dp=[0]*(N*12+1)
        dp[i]=1
        for j in range(N*6):
            dp[j]%=MOD
            if j%N==c:
                dp[j]=0
            for k in range(1,7):
                dp[j+k]+=dp[j]
        for j in range(6):
            if j%N!=c:
                matrix[i][j]=dp[N*6+j]%MOD
    matrix=matrix_pow(matrix,length)
    dp=[0]*(last*N+1)
    for i in range(6):
        if matrix[0][i]!=0:
            dp[i]=matrix[0][i]
    for i in range(N*last):
        if i%N==c:
            dp[i]=0
        dp[i]%=MOD
        for j in range(1,7):
            dp[min(i+j,N*last)]+=dp[i]
    print((lst-dp[-1])%MOD)
0