結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-04-29 22:37:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 349 ms / 3,000 ms |
コード長 | 6,295 bytes |
コンパイル時間 | 2,417 ms |
コンパイル使用メモリ | 212,540 KB |
最終ジャッジ日時 | 2025-01-28 23:25:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<ll, ll>;using tp = tuple<ll, ll, ll>;template <class T>using vec = vector<T>;template <class T>using vvec = vector<vec<T>>;#define all(hoge) (hoge).begin(), (hoge).end()#define en '\n'#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)#define REP(i, n) rep(i, 0, n)#define REP2(i, n) rep2(i, 0, n)constexpr long long INF = 1LL << 60;constexpr int INF_INT = 1 << 25;constexpr long long MOD = (ll)1e9 + 7;// constexpr long long MOD = 998244353LL;static const ld pi = 3.141592653589793L;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")template <class T>inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}template <class T>inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}//グラフ関連struct Edge {int to, rev;ll cap;Edge(int _to, int _rev, ll _cap) : to(_to), rev(_rev), cap(_cap) {}};typedef vector<Edge> Edges;typedef vector<Edges> Graph;void add_edge(Graph &G, int from, int to, ll cap, bool revFlag, ll revCap) {G[from].push_back(Edge(to, (int)G[to].size(), cap));if(revFlag)G[to].push_back(Edge(from, (int)G[from].size() - 1, revCap));}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod)x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod)x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1)ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt<mod>(t);return (is);}static int get_mod() { return mod; }};using mint = ModInt<MOD>;void solve() {ll h, w;cin >> h >> w;vec<string> s(h);REP(i, h) {cin >> s[i];}if(s[0][0] != s[h - 1][w - 1]) {cout << 0 << en;return;}if(h + w <= 3) {cout << (s[0][0] == s[h - 1][w - 1]) << en;return;}vector dp(h + w, vector(h + w, vector(h + w, mint(0))));dp[0][h][w] = 1; // s[0][0]とs[h-1][w-1]にいる状態int d = (h + w - 1 + 1) / 2 - 1;ll dx[2] = {1, 0};ll dy[2] = {0, 1};mint ans = 0;REP(i, d) {// cout << "d:" << i << en;REP(j, h + w) {REP(k, h + w) {if(dp[i][j][k].x == 0)continue;int x1 = (i + j - h) / 2;int y1 = (i - j + h) / 2;int x2 = (h + w - 1 - i + k - h) / 2;int y2 = (h + w - 1 - i - k + h) / 2;// cout << x1 << " " << y1 << " " << x2 << " " << y2 << en;REP(v1, 2) {ll nx1 = x1 + dx[v1];ll ny1 = y1 + dy[v1];if(nx1 < 0 or nx1 >= w or ny1 < 0 or ny1 >= h)continue;REP(v2, 2) {ll nx2 = x2 - dx[v2];ll ny2 = y2 - dy[v2];if(nx2 < 0 or nx2 >= w or ny2 < 0 or ny2 >= h)continue;if(s[ny1][nx1] != s[ny2][nx2])continue;ll nj = nx1 - ny1 + h;ll nk = nx2 - ny2 + h;// cout << nx1 << " " << ny1 << " " << nx2 << " " << ny2 << en;if(i + 1 == d) {if((h + w - 1) % 2) {if(nx1 == nx2 and ny1 == ny2)ans += dp[i][j][k];} else {if(abs(nx2 - nx1) + abs(ny2 - ny1) <= 1)ans += dp[i][j][k];}continue;}dp[i + 1][nj][nk] += dp[i][j][k];}}}}// REP(j, h + w) {// REP(k, h + w) {// cout << dp[i][j][k] << " ";// }// cout << en;// }}// REP(i, d) {// cout << "d:" << i << en;// REP(j, h + w) {// REP(k, h + w) {// cout << dp[i][j][k] << " ";// }// cout << en;// }// cout << en;// }cout << ans << en;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// cout << fixed << setprecision(10);// ll t;// cin >> t;// REP(i, t - 1) {// solve();// }solve();return 0;}