Submission #28021143

---

Source Code Expand

//g++ 1.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;

#define fi first
#define se second
#define pb push_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

const int MAX=1510000;
const long long MOD=998244353;

long long fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<MAX;i++){
    fac[i]=fac[i-1]*i%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

long long COM(int n,int k){
  if(n<k) return 0;
  if(n<0||k<0) return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

using mint = modint998244353;

mint dp_h[1000000+10][2]={};
mint dp_w[1000000+10][2]={};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  COMinit();

  int h,w,k;
  cin>>h>>w>>k;

  h%=MOD;
  w%=MOD;

  //i回移動j=0 -> 同じとこ j=1 -> 違うとこ

  dp_h[0][0]=1;dp_h[0][1]=0;dp_h[1][0]=0;dp_h[1][1]=1;
  dp_w[0][0]=1;dp_w[0][1]=0;dp_w[1][0]=0;dp_w[1][1]=1;

  rep(i,2,k+10){
    /*
    dp_h[i][0] 1から1
    dp_h[i][1] 1から2 
    */
    dp_h[i][0]=dp_h[i-1][1]*(h-1);
    dp_h[i][1]=dp_h[i-1][0]+dp_h[i-1][1]*(h-2);

    dp_w[i][0]=dp_w[i-1][1]*(w-1);
    dp_w[i][1]=dp_w[i-1][0]+dp_w[i-1][1]*(w-2);
  }

  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;

  mint ans=0;

  rep(i,0,k+1){
    mint nw=1;
    if(x1==x2){
      nw*=dp_h[i][0];
    }
    else{
      nw*=dp_h[i][1];
    }
    if(y1==y2){
      nw*=dp_w[k-i][0];
    }
    else{
      nw*=dp_w[k-i][1];
    }

    nw*=COM(k,i);

    ans+=nw;
  }

  cout<<ans.val()<<endl;
}

Submission Info

Judge Result