結果
問題 | No.3071 Double Speedrun |
ユーザー |
👑 ![]() |
提出日時 | 2025-03-21 22:12:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 6,000 ms |
コード長 | 4,105 bytes |
コンパイル時間 | 873 ms |
コンパイル使用メモリ | 84,024 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 22:12:35 |
合計ジャッジ時間 | 4,259 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include <utility> #include <cassert> namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ template<unsigned int MOD> struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const { return x; } my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; } bool operator==(const my_type& r) const { return x == r.x; } my_type pow(unsigned long long i) const { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const { return x; } int hval() const { return int(x > MOD/2 ? x - MOD : x); } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } // namespace nachia using Modint = nachia::StaticModint<998244353>; void testcase(){ i64 H, W; cin >> H >> W; vector<string> A(H+1); rep(i,H) cin >> A[i]; rep(i,H) A[i].push_back('#'); A[H] = string(W+1, '#'); vector<vector<Modint>> dp(1, vector<Modint>(1,1)); for(i64 i=1; i<H+W-2; i++){ i64 p = dp.size(); vector<vector<Modint>> nx(p+1, vector<Modint>(p+1,0)); rep(a,p) rep(b,p) if(a<=b){ nx[a][b] += dp[a][b]; nx[a+1][b] += dp[a][b]; nx[a][b+1] += dp[a][b]; nx[a+1][b+1] += dp[a][b]; } string ref; for(i64 x=0; x<W; x++) if(0 <= i-x && i-x < H) ref.push_back(A[i-x][x]); i64 q = ref.size(); //cout << ref << endl; i64 off = i < H ? 0 : 1; vector<vector<Modint>> nx2(q, vector<Modint>(q,0)); rep(a,q) rep(b,q) if(a<b && ref[a] == '.' && ref[b] == '.'){ nx2[a][b] = nx[a+off][b+off]; } swap(dp, nx2); //for(auto a : dp){ // for(auto b : a) cout << b.val() << " "; // cout << endl; //} } cout << dp[0][1].val() << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); rep(f,1) testcase(); return 0; }