結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー | ああいい |
提出日時 | 2022-04-29 22:02:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,097 ms / 3,000 ms |
コード長 | 2,230 bytes |
コンパイル時間 | 342 ms |
コンパイル使用メモリ | 87,220 KB |
実行使用メモリ | 185,032 KB |
最終ジャッジ日時 | 2023-09-11 13:13:54 |
合計ジャッジ時間 | 19,236 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 96 ms
71,724 KB |
testcase_01 | AC | 74 ms
71,364 KB |
testcase_02 | AC | 151 ms
77,860 KB |
testcase_03 | AC | 94 ms
71,388 KB |
testcase_04 | AC | 97 ms
71,680 KB |
testcase_05 | AC | 97 ms
71,740 KB |
testcase_06 | AC | 100 ms
72,344 KB |
testcase_07 | AC | 100 ms
72,388 KB |
testcase_08 | AC | 100 ms
72,152 KB |
testcase_09 | AC | 96 ms
71,604 KB |
testcase_10 | AC | 95 ms
71,900 KB |
testcase_11 | AC | 101 ms
72,156 KB |
testcase_12 | AC | 94 ms
71,612 KB |
testcase_13 | AC | 123 ms
77,528 KB |
testcase_14 | AC | 127 ms
78,356 KB |
testcase_15 | AC | 249 ms
79,080 KB |
testcase_16 | AC | 223 ms
78,556 KB |
testcase_17 | AC | 355 ms
81,352 KB |
testcase_18 | AC | 887 ms
108,524 KB |
testcase_19 | AC | 884 ms
106,120 KB |
testcase_20 | AC | 873 ms
106,472 KB |
testcase_21 | AC | 870 ms
107,100 KB |
testcase_22 | AC | 893 ms
106,460 KB |
testcase_23 | AC | 76 ms
71,576 KB |
testcase_24 | AC | 74 ms
71,376 KB |
testcase_25 | AC | 76 ms
71,548 KB |
testcase_26 | AC | 74 ms
71,420 KB |
testcase_27 | AC | 75 ms
71,264 KB |
testcase_28 | AC | 2,097 ms
183,868 KB |
testcase_29 | AC | 2,087 ms
184,596 KB |
testcase_30 | AC | 2,057 ms
184,576 KB |
testcase_31 | AC | 2,079 ms
183,440 KB |
testcase_32 | AC | 2,072 ms
185,032 KB |
ソースコード
H,W = map(int,input().split()) S = [input() for _ in range(H)] P = 10 ** 9 + 7 import sys if S[0][0] != S[-1][-1]: print(0) exit() base = 10 mask = (1 << base) - 1 def pack(a,b,c,d): return (a << 30) + (b << 20) + (c << 10) + d def unpack(x): d = x & mask x >>= base c = x & mask x >>= base b = x & mask a = x >> base return (a,b,c,d) from collections import defaultdict d = defaultdict(int) d[pack(0,0,H - 1,W - 1)] = 1 ans = 0 u = H + W - 2 if u % 2 == 0: for _ in range(u // 2): nx = defaultdict(int) for x in d: h,w,hh,ww = unpack(x) for i,j in [(1,0),(0,1)]: for k,l in [(-1,0),(0,-1)]: if h + i < H and w + j < W and hh + k >= 0 and ww + l >= 0: if S[h + i][w + j] == S[hh + k][ww + l]: nx[pack(h + i,w + j,hh + k,ww + l)] += d[pack(h,w,hh,ww)] nx[pack(h + i,w + j,hh + k,ww + l)] %= P d = nx for u in d: h,w,hh,ww = unpack(u) if h == hh and w == ww: ans += d[u] ans %= P print(ans) else: for _ in range(u // 2 + 1): nx = defaultdict(int) if _ < u // 2: for x in d: h,w,hh,ww = unpack(x) for i,j in [(1,0),(0,1)]: for k,l in [(-1,0),(0,-1)]: if h + i < H and w + j < W and hh + k >= 0 and ww + l >= 0: if S[h + i][w + j] == S[hh + k][ww + l]: nx[pack(h + i,w + j,hh + k,ww + l)] += d[x] nx[pack(h + i,w + j,hh + k,ww + l)] %= P else: for x in d: h,w,hh,ww = unpack(x) for i,j in [(1,0),(0,1)]: for k,l in [(-1,0),(0,-1)]: if h + i < H and w + j < W and hh + k >= 0 and ww + l >= 0: if S[h + i][w + j] == S[hh + k][ww + l]: if h + i == hh and w + j == ww and hh + k == h and ww + l == w: ans += d[x] ans %= P d = nx print(ans)