結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-04-29 22:41:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,097 ms / 3,000 ms |
コード長 | 2,112 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 149,860 KB |
最終ジャッジ日時 | 2024-06-29 04:18:29 |
合計ジャッジ時間 | 12,101 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sysinput = sys.stdin.readlinemod=10**9+7H,W=map(int,input().split())MAP=[input().strip() for i in range(H)]#H,W=200,200#MAP=["a"*W for i in range(H)]if MAP[0][0]!=MAP[-1][-1]:print(0)exit()def cc(x,y,z,w):return x*8000000+y*40000+z*200+wdef re(r):w=r%200r//=200z=r%200r//=200y=r%200x=r//200return x,y,z,wDP=dict()DP[cc(0,0,H-1,W-1)]=1for i in range((H+W-2)//2):NDP=dict()for r in DP:x,y,z,w=re(r)if 0<=x<H and 0<=z<H and 0<=y+1<W and 0<=w-1<W and MAP[x][y+1]==MAP[z][w-1]:if cc(x,y+1,z,w-1) in NDP:NDP[cc(x,y+1,z,w-1)]+=DP[cc(x,y,z,w)]NDP[cc(x,y+1,z,w-1)]%=modelse:NDP[cc(x,y+1,z,w-1)]=DP[cc(x,y,z,w)]if 0<=x<H and 0<=z-1<H and 0<=y+1<W and 0<=w<W and MAP[x][y+1]==MAP[z-1][w]:if cc(x,y+1,z-1,w) in NDP:NDP[cc(x,y+1,z-1,w)]+=DP[cc(x,y,z,w)]NDP[cc(x,y+1,z-1,w)]%=modelse:NDP[cc(x,y+1,z-1,w)]=DP[cc(x,y,z,w)]if 0<=x+1<H and 0<=z<H and 0<=y<W and 0<=w-1<W and MAP[x+1][y]==MAP[z][w-1]:if cc(x+1,y,z,w-1) in NDP:NDP[cc(x+1,y,z,w-1)]+=DP[cc(x,y,z,w)]NDP[cc(x+1,y,z,w-1)]%=modelse:NDP[cc(x+1,y,z,w-1)]=DP[cc(x,y,z,w)]if 0<=x+1<H and 0<=z-1<H and 0<=y<W and 0<=w<W and MAP[x+1][y]==MAP[z-1][w]:if cc(x+1,y,z-1,w) in NDP:NDP[cc(x+1,y,z-1,w)]+=DP[cc(x,y,z,w)]NDP[cc(x+1,y,z-1,w)]%=modelse:NDP[cc(x+1,y,z-1,w)]=DP[cc(x,y,z,w)]DP=NDPif (H+W)%2==0:ANS=0for r in DP:x,y,z,w=re(r)if x==z and y==w:ANS+=DP[cc(x,y,z,w)]ANS%=modprint(ANS)else:ANS=0for r in DP:x,y,z,w=re(r)if x==z and y+1==w:ANS+=DP[cc(x,y,z,w)]ANS%=modif x+1==z and y==w:ANS+=DP[cc(x,y,z,w)]ANS%=modprint(ANS)