結果

問題 No.1516 simple 門松列 problem Re:MASTER
コンテスト
ユーザー ansain
提出日時 2021-05-04 03:59:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,674 ms / 6,000 ms
コード長 3,001 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 88,480 KB
最終ジャッジ日時 2024-10-09 04:27:14
合計ジャッジ時間 17,939 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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