結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
👑 ![]() |
提出日時 | 2022-04-29 21:36:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,999 ms / 3,000 ms |
コード長 | 1,201 bytes |
コンパイル時間 | 1,119 ms |
コンパイル使用メモリ | 90,400 KB |
最終ジャッジ日時 | 2025-01-28 22:34:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <atcoder/modint>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)using m32 = atcoder::static_modint<1000000007>;int H,W;map<pair<pair<int,int>, pair<int,int>>, m32> dp;vector<string> S;m32 recursion(int y1, int x1, int y2, int x2){if(y1 > y2 || x1 > x2){ return m32::raw(0); }if(S[y1][x1] != S[y2][x2]) return m32::raw(0);if(y1 + x1 + 1 >= x2 + y2) return m32::raw(1);if(dp.count({{y1,x1},{y2,x2}})) return dp[{{y1,x1},{y2,x2}}];m32 ans = 0;ans += recursion(y1+1, x1, y2-1, x2);ans += recursion(y1+1, x1, y2, x2-1);ans += recursion(y1, x1+1, y2-1, x2);ans += recursion(y1, x1+1, y2, x2-1);return dp[{{y1,x1},{y2,x2}}] = ans;}int main(){cin >> H >> W;S.resize(H);rep(y,H) cin >> S[y];m32 ans = recursion(0,0,H-1,W-1);cout << ans.val() << '\n';return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;