結果

問題 No.1516 simple 門松列 problem Re:MASTER
ユーザー ansainansain
提出日時 2021-05-04 03:59:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,646 ms / 6,000 ms
コード長 3,001 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 88,064 KB
最終ジャッジ日時 2024-04-17 10:42:51
合計ジャッジ時間 17,603 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
62,336 KB
testcase_01 AC 307 ms
78,076 KB
testcase_02 AC 1,606 ms
82,432 KB
testcase_03 AC 59 ms
68,480 KB
testcase_04 AC 58 ms
67,840 KB
testcase_05 AC 73 ms
76,652 KB
testcase_06 AC 123 ms
77,056 KB
testcase_07 AC 289 ms
77,952 KB
testcase_08 AC 408 ms
78,592 KB
testcase_09 AC 50 ms
62,848 KB
testcase_10 AC 132 ms
77,192 KB
testcase_11 AC 82 ms
77,060 KB
testcase_12 AC 62 ms
71,936 KB
testcase_13 AC 52 ms
64,000 KB
testcase_14 AC 3,170 ms
86,400 KB
testcase_15 AC 1,361 ms
82,432 KB
testcase_16 AC 662 ms
80,000 KB
testcase_17 AC 278 ms
78,164 KB
testcase_18 AC 124 ms
76,928 KB
testcase_19 AC 85 ms
76,416 KB
testcase_20 AC 3,646 ms
88,064 KB
testcase_21 AC 3,592 ms
87,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, Counter, deque
from itertools import permutations, combinations, product, combinations_with_replacement, groupby, accumulate
import operator
from math import sqrt, gcd, factorial
# from math import isqrt, prod,comb  # python3.8用(notpypy)
#from bisect import bisect_left,bisect_right
#from functools import lru_cache,reduce
#from heapq import heappush,heappop,heapify,heappushpop,heapreplace
#import numpy as np
#import networkx as nx
#from networkx.utils import UnionFind
#from numba import njit, b1, i1, i4, i8, f8
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, NegativeCycleError
# numba例 @njit(i1(i4[:], i8[:, :]),cache=True) 引数i4配列、i8 2次元配列,戻り値i1
def input(): return sys.stdin.readline().rstrip()
def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す
def yn(hantei, yes='Yes', no='No'): print(yes if hantei else no)


def check(a):
    return a[0] != a[1] and a[1] != a[2] and a[2] != a[0] and a[1] in [max(a), min(a)]


def dot(a, b, MOD=10**9+7):
    n=len(a)
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ret[i][j] = sum(a[i][k] * b[k][j] for k in range(n)) % MOD
    return ret

def dot2(a, b, MOD=10**9+7):
    n=len(a)
    ret = [0] * n
    for j in range(n):
        ret[j] = sum(a[k] * b[k][j] for k in range(n)) % MOD
    return ret


def matrix_multiplication(a, n, k, mod=10**9+7):  # n次正方行列a^k
    ans = [[int(i==j) for i in range(n)] for j in range(n)]
    while k:
        k, i = divmod(k, 2)
        if i:
            ans = dot(ans, a ,mod)
        a = dot(a, a, mod)
    return ans


def main():
    mod = 10**9+7
    mod2 = 998244353
    n, k = map(int, input().split())
    mat = [[0]*2*k*k for i in range(2*k*k)]
    ans = [0]*2*k*k
    for a in range(k):
        for b in range(k):
            for c in range(k):
                if check([a, b, c]):
                    mat[a*k+b][b*k+c] += 1
                    mat[a*k+b+k**2][b*k+c+k**2] += 1
                    mat[a*k+b][b*k+c+k**2] += a
            if a != b:
                ans[a*k+b] += 1
                ans[a*k+b+k**2] += a+b
    newmat=[]
    newans=[]
    for x in range(2):
        for a in range(k):
            for b in range(k):
                if a!=b:
                    tmp=[]
                    for y in range(2):
                        for c in range(k):
                            for d in range(k):
                                if c!=d:
                                    tmp.append(mat[a*k+b+x*k**2][c*k+d+y*k**2])
                    newmat.append(tmp)
                    newans.append(ans[a*k+b+x*k**2])    
    mat2=matrix_multiplication(newmat, 2*k*(k-1), n-2, mod2)
    ans2=dot2(newans,mat2,mod2)
    #print(ans2[:k*k])
    #print(ans2[k*k:])
    print(sum(ans2[:k*(k-1)])%mod2,sum(ans2[k*(k-1):])%mod2)


if __name__ == '__main__':
    main()
0