fork download
copy 
  1. // Author: Rushin Shah
  2.  
  3. #include <bits/stdc++.h>
  4. #define int long long
  5. #define inf (LLONG_MAX / 5)
  6.  
  7. using namespace std;
  8.  
  9. // constexpr int MOD = 1e9 + 7;
  10. const int MOD = 998244353;
  11.  
  12. int inv(int a, int b = MOD - 2);
  13.  
  14. struct Mint
  15. {
  16.     int val;
  17.     Mint(int v) : val(v) {}
  18.     Mint() : val(0) {}
  19.  
  20.     Mint operator+(const Mint &b) const
  21.     {
  22.         Mint n = val + b.val;
  23.         n.val %= MOD;
  24.         return n;
  25.     }
  26.  
  27.     Mint operator-(const Mint &b) const
  28.     {
  29.         Mint n = val - b.val;
  30.         if (n.val < 0)
  31.             n += MOD;
  32.         return n;
  33.     }
  34.  
  35.     Mint operator*(const Mint &b) const
  36.     {
  37.         Mint n = val * b.val;
  38.         n.val %= MOD;
  39.         return n;
  40.     }
  41.  
  42.     Mint operator/(const Mint &b) const
  43.     {
  44.         Mint n = val * inv(b.val);
  45.         n.val %= MOD;
  46.         return n;
  47.     }
  48.     Mint &operator+=(const Mint &b)
  49.     {
  50.         this->val += b.val;
  51.         this->val %= MOD;
  52.         return *this;
  53.     }
  54.  
  55.     Mint &operator-=(const Mint &b)
  56.     {
  57.         this->val -= b.val;
  58.         if (this->val < 0)
  59.             this->val += MOD;
  60.         return *this;
  61.     }
  62.  
  63.     Mint &operator*=(const Mint &b)
  64.     {
  65.         this->val *= b.val;
  66.         this->val %= MOD;
  67.         return *this;
  68.     }
  69.  
  70.     Mint operator/=(const Mint &b)
  71.     {
  72.         this->val *= inv(b.val);
  73.         this->val %= MOD;
  74.         return *this;
  75.     }
  76.     Mint operator++(int32_t)
  77.     {
  78.         Mint tmp = *this;
  79.         this->val += 1;
  80.         return tmp;
  81.     }
  82.     Mint &operator++()
  83.     {
  84.         this->val += 1;
  85.         return *this;
  86.     }
  87.     bool operator<(const Mint &b) const
  88.     {
  89.         return val < b.val;
  90.     }
  91.     bool operator<=(const Mint &b) const
  92.     {
  93.         return val <= b.val;
  94.     }
  95.     bool operator>(const Mint &b) const
  96.     {
  97.         return val > b.val;
  98.     }
  99.  
  100.     bool operator>=(const Mint &b) const
  101.     {
  102.         return val >= b.val;
  103.     }
  104.  
  105.     operator int() const
  106.     {
  107.         return val;
  108.     }
  109.     friend std::ostream &operator<<(std::ostream &os, const Mint &b)
  110.     {
  111.  
  112.         return os << b.val;
  113.     }
  114.     friend std::istream &operator>>(std::istream &is, Mint &b)
  115.     {
  116.         is >> b.val;
  117.         return is;
  118.     }
  119. };
  120.  
  121. Mint bin_pow(int a, int b)
  122. {
  123.     if (!b)
  124.         return 1;
  125.     Mint g = bin_pow(a, (b >> 1));
  126.     g *= g;
  127.     if (b & 1)
  128.         g *= a;
  129.     return g;
  130. }
  131.  
  132. int inv(int a, int b)
  133. {
  134.     return bin_pow(a, b);
  135. }
  136. // -----------------------PRIME TIME--------------------------------------------
  137.  
  138. // constexpr int primeN = 1000000 + 5;
  139. // bitset<primeN> is_prime;
  140. // int low[primeN];
  141. // vector<int> primes;
  142.  
  143. // void prime_it()
  144. // {
  145. //     is_prime.set();
  146. //     for (int i = 2; i < primeN; i++)
  147. //     {
  148. //         if (!is_prime[i])
  149. //             continue;
  150. //         primes.push_back(i);
  151. //         low[i] = i;
  152. //         for (int j = i * i; j < primeN; j += i)
  153. //         {
  154. //             is_prime.reset(j);
  155. //             low[j] = i;
  156. //         }
  157. //     }
  158. // }
  159.  
  160. // ---------------------------------DAILY USE--------------------------------------------------------------
  161.  
  162. constexpr int maxN = 2050;
  163. int n, m, d;
  164. int a[maxN][maxN];
  165. Mint dp[maxN][maxN][2];
  166. Mint pre_dp[maxN][maxN][2];
  167.  
  168. // REMEMBER TO - USE BS - Find an Invariant - DP[find subproblems]
  169. // REMEBER TO  - Focus on any imp constraints or find one
  170.  
  171. void solve()
  172. {
  173.     cin >> n >> m >> d;
  174.  
  175.     for (int i = 1; i <= n; i++)
  176.     {
  177.         for (int j = 1; j <= m; j++)
  178.         {
  179.             char x;
  180.             cin >> x;
  181.             if (x == 'X')
  182.                 a[i][j] = 1;
  183.             else
  184.                 a[i][j] = 0;
  185.         }
  186.     }
  187.     for (int j = 1; j <= m; j++)
  188.     {
  189.         if (a[n][j])
  190.         {
  191.             dp[n][j][0] = 1;
  192.         }
  193.     }
  194.     for (int j = 1; j <= m; j++)
  195.     {
  196.         if (a[n][j])
  197.         {
  198.             int l = max(0ll, j - d - 1), r = max(n, j + d);
  199.             dp[n][j][1] += pre_dp[n][r][0] - pre_dp[n][l][0] - dp[n][j][0];
  200.         }
  201.     }
  202.  
  203.     for (int j = 1; j <= m; j++)
  204.     {
  205.         pre_dp[n][j][0] += pre_dp[n][j - 1][0] + dp[n][j][0];
  206.         pre_dp[n][j][1] += pre_dp[n][j - 1][1] + dp[n][j][1];
  207.     }
  208.     for (int i = n - 1; i > 0; i--)
  209.     {
  210.         for (int j = 0; j <= m; j++)
  211.         {
  212.             for (int k = 0; k < 2; k++)
  213.             {
  214.                 dp[i][j][k] = 0;
  215.                 pre_dp[i][j][k] = 0;
  216.             }
  217.         }
  218.         for (int j = 1; j <= m; j++)
  219.         {
  220.             if (!a[i][j])
  221.                 continue;
  222.             for (int k = 0; k < 2; k++)
  223.             {
  224.                 if (k == 0)
  225.                 {
  226.                     int l = max(0ll, j - d - 1), r = max(n, j + d);
  227.                     dp[i][j][k] += pre_dp[i + 1][r][0] - pre_dp[i + 1][l][0];
  228.                     dp[i][j][k] += pre_dp[i + 1][r][1] - pre_dp[i + 1][l][1];
  229.                 }
  230.                 else
  231.                 {
  232.                     int l = max(0ll, j - d - 1), r = max(n, j + d);
  233.                     dp[i][j][k] += pre_dp[i][r][0] - pre_dp[i][l][0] - dp[i][j][0];
  234.                 }
  235.             }
  236.         }
  237.         for (int j = 1; j <= m; j++)
  238.         {
  239.             pre_dp[i][j][0] += pre_dp[i][j - 1][0] + dp[i][j][0];
  240.             pre_dp[i][j][1] += pre_dp[i][j - 1][1] + dp[i][j][1];
  241.         }
  242.     }
  243.  
  244.     cout << pre_dp[1][m][0] + pre_dp[1][m][1] << "\n";
  245. }
  246.  
  247. int32_t main()
  248. {
  249.     ios_base::sync_with_stdio(false);
  250.     cin.tie(nullptr);
  251.  
  252.     // prime_it();
  253.  
  254.     int t = 1;
  255.     cin >> t;
  256.     // cout << fixed << setprecision(7);
  257.     for (int i = 1; i <= t; i++)
  258.     {
  259.         solve();
  260.     }
  261.     return 0;
  262. }
Success #stdin #stdout 0.03s 136900KB
comments (?)
stdin
copy 
3
3 4 1
XX#X
#XX#
#X#X
3 4 2
XX#X
#XX#
#X#X
3 1 3
X
X
#
stdout
copy 
0
0
0
https://ideone.com/SIngVU
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!