fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(x) (int)(x).size()
  8. #define FILL(a,v) memset(a,v,sizeof(a))
  9. using namespace std;
  10. typedef long long ll; typedef pair<int,int> ii;
  11. const int N = 1000003;
  12. const int MOD = 998244353;
  13.  
  14. int addmod(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
  15. int mulmod(ll a,ll b){ return (int)((a*b)%MOD); }
  16.  
  17. int main(){
  18.     ios::sync_with_stdio(false);
  19.     cin.tie(nullptr); cout.tie(nullptr);
  20.     freopen("sumpath.inp","r",stdin);
  21.     freopen("sumpath.out","w",stdout);
  22.     int m, n;
  23.     cin >> m >> n;
  24.     vector<string> g(m);
  25.     for(int i=0;i<m;++i) cin>>g[i];
  26.     vector<vector<int>> d(m, vector<int>(n,0));
  27.     d[0][0]=1;
  28.     for(int i=0;i<m;++i){
  29.         for(int j=0;j<n;++j){
  30.             if(i||j){
  31.                 int v=0;
  32.                 if(i) v=addmod(v,d[i-1][j]);
  33.                 if(j) v=addmod(v,d[i][j-1]);
  34.                 if(i&&j) v=addmod(v,d[i-1][j-1]);
  35.                 d[i][j]=v;
  36.             }
  37.         }
  38.     }
  39.     int ans=0;
  40.     for(int i=0;i<m;++i){
  41.         for(int j=0;j<n;++j){
  42.             int dig = g[i][j]-'0';
  43.             int ways = mulmod(d[i][j], d[m-1-i][n-1-j]);
  44.             ans = addmod(ans, mulmod(dig, ways));
  45.         }
  46.     }
  47.     cout<<ans;
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0.34s 112656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KTLnLh
language:
C++14 (clang 8.0)
created:
11 hours 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!