結果

問題 No.1516 simple 門松列 problem Re:MASTER
ユーザー googol_S0googol_S0
提出日時 2021-05-21 23:03:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 197 ms / 6,000 ms
コード長 3,533 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 78,672 KB
最終ジャッジ日時 2024-10-10 09:55:05
合計ジャッジ時間 3,342 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
52,864 KB
testcase_01 AC 77 ms
69,632 KB
testcase_02 AC 197 ms
78,292 KB
testcase_03 AC 40 ms
53,248 KB
testcase_04 AC 40 ms
53,504 KB
testcase_05 AC 54 ms
64,000 KB
testcase_06 AC 169 ms
78,428 KB
testcase_07 AC 95 ms
76,484 KB
testcase_08 AC 154 ms
77,388 KB
testcase_09 AC 41 ms
52,736 KB
testcase_10 AC 50 ms
61,952 KB
testcase_11 AC 41 ms
53,376 KB
testcase_12 AC 41 ms
53,760 KB
testcase_13 AC 42 ms
52,736 KB
testcase_14 AC 188 ms
78,672 KB
testcase_15 AC 159 ms
77,516 KB
testcase_16 AC 143 ms
77,328 KB
testcase_17 AC 134 ms
77,504 KB
testcase_18 AC 94 ms
76,032 KB
testcase_19 AC 62 ms
67,072 KB
testcase_20 AC 194 ms
78,220 KB
testcase_21 AC 194 ms
78,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K=map(int,input().split())
if K==3:
  if N==3:
    print(4,12)
  elif N==4:
    print(2,8)
  else:
    print(0,0)
  exit()
def m(a,b):
  r=[[0]*len(b[0]) for i in range(len(a))]
  for i in range(len(a)):
    for k in range(len(b)):
      for j in range(len(b[0])):
        r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod
  return r

def p(a,n):
  r=[[0]*len(a) for i in range(len(a))]
  b=[]
  for i in range(len(a)):
    r[i][i]=1
    b.append(a[i][:])
  l=n
  while l>0:
    if l&1:
      r=m(b,r)
    b=m(b,b)
    l>>=1
  return r
S='''1,998244352,1,0
1,998244351,4,0,4,0
2,998244348,12,998244346,24,998244350,18,0
2,998244346,22,998244341,88,4,152,16,96,0
3,998244341,44,998244303,254,998244269,734,998244310,1065,10,600,0
3,998244338,65,998244281,572,998244289,2620,452,6580,1284,8520,936,4320,0'''.split('\n')

T='''2,998244350,4,998244350,2,998244352,0
2,998244348,12,998244341,24,998244329,16,998244321,0,998244337,0
4,998244339,44,998244266,196,998244037,456,998243626,588,998243303,396,998243480,108,998244029,0
4,998244337,64,998244224,404,998243615,1240,998241293,1712,998235977,160,998230497,998242305,998231937,998242817,998239745,0
6,998244320,160,998243845,1864,998239525,12468,998212995,52796,998099443,146556,997763045,265176,997105553,296964,996375964,177710,996230188,30300,996966253,998232353,997884353,0
6,998244314,220,998243594,3526,998234408,32144,998148073,179736,997544001,598472,994441937,857496,982989745,996484017,953551505,986209729,904320145,969293153,860989553,960141953,866399105,971201153,923755457,990157313,979581953,0'''.split('\n')

mod=998244353
def solve1(N,K):
  DP1=[[[0]*K for i in range(K)] for j in range(N-1)]
  DP2=[[[0]*K for i in range(K)] for j in range(N-1)]
  for i in range(K):
    for j in range(K):
      if i!=j:
        DP1[0][i][j]=1
        DP2[0][i][j]=i+j
  for i in range(N-2):
    for j in range(K):
      for k in range(K):
        for l in range(K):
          if (min(j,k,l)==k or max(j,k,l)==k) and j!=l and k!=l:
            DP1[i+1][k][l]+=DP1[i][j][k]
            DP2[i+1][k][l]+=DP2[i][j][k]+DP1[i][j][k]*l
  ANS1,ANS2=0,0
  for i in range(K):
    for j in range(K):
      ANS1+=DP1[-1][i][j]
      ANS2+=DP2[-1][i][j]
  return ANS1

def solve2(N,K):
  DP1=[[[0]*K for i in range(K)] for j in range(N-1)]
  DP2=[[[0]*K for i in range(K)] for j in range(N-1)]
  for i in range(K):
    for j in range(K):
      if i!=j:
        DP1[0][i][j]=1
        DP2[0][i][j]=i+j
  for i in range(N-2):
    for j in range(K):
      for k in range(K):
        for l in range(K):
          if (min(j,k,l)==k or max(j,k,l)==k) and j!=l and k!=l:
            DP1[i+1][k][l]+=DP1[i][j][k]
            DP2[i+1][k][l]+=DP2[i][j][k]+DP1[i][j][k]*l
  ANS1,ANS2=0,0
  for i in range(K):
    for j in range(K):
      ANS1+=DP1[-1][i][j]
      ANS2+=DP2[-1][i][j]
  return ANS2

if N<=100:
  print(solve1(N,K)%mod,solve2(N,K)%mod)
  exit()
M=K-4
X=[list(map(int,S[i].split(','))) for i in range(6)]
Y=[list(map(int,T[i].split(','))) for i in range(6)]
A=[[0]*len(X[M]) for i in range(len(X[M]))]
for i in range(len(X[M])):
  A[i][-1]=solve1(len(X[M])-i+2,K)%mod
B=[[0]*len(X[M]) for i in range(len(X[M]))]
for i in range(len(X[M])-1):
  B[i+1][i]=1
for i in range(len(X[M])):
  B[0][i]=X[M][i]
ANS1=m(p(B,N-3),A)[-1][-1]
A=[[0]*len(Y[M]) for i in range(len(Y[M]))]
for i in range(len(Y[M])):
  A[i][-1]=solve2(len(Y[M])-i+2,K)%mod
B=[[0]*len(Y[M]) for i in range(len(Y[M]))]
for i in range(len(Y[M])-1):
  B[i+1][i]=1
for i in range(len(Y[M])):
  B[0][i]=Y[M][i]
print(ANS1,m(p(B,N-3),A)[-1][-1])
0