結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
|
提出日時 | 2022-04-29 22:02:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,884 ms / 3,000 ms |
コード長 | 2,230 bytes |
コンパイル時間 | 331 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 184,156 KB |
最終ジャッジ日時 | 2024-12-26 23:20:37 |
合計ジャッジ時間 | 16,084 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
H,W = map(int,input().split())S = [input() for _ in range(H)]P = 10 ** 9 + 7import sysif S[0][0] != S[-1][-1]:print(0)exit()base = 10mask = (1 << base) - 1def pack(a,b,c,d):return (a << 30) + (b << 20) + (c << 10) + ddef unpack(x):d = x & maskx >>= basec = x & maskx >>= baseb = x & maska = x >> basereturn (a,b,c,d)from collections import defaultdictd = defaultdict(int)d[pack(0,0,H - 1,W - 1)] = 1ans = 0u = H + W - 2if 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)] %= Pd = nxfor u in d:h,w,hh,ww = unpack(u)if h == hh and w == ww:ans += d[u]ans %= Pprint(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)] %= Pelse: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 %= Pd = nxprint(ans)