E - Rook Path
作者:
arthur15
,
2022-02-19 10:28:58
,
所有人可见
,
阅读 247
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
E - Rook Path
https://atcoder.jp/contests/abc232/tasks/abc232_e
dp[x][y] : sum
My idea:
1. current row and column must to be useful?
2. dfs ?
3. need memory?
4. four condition ?
SOLUTION:
1. we can transfer 2 dimension to 1 dimension, x and y can be seen separately, because it's only to only down and horizon
* */
public class Main{
static int N = 1000010;
static long p = 998244353;
static int n, m, k, x1, y1, x2, y2;
static long[][] x;
static long[][] y;
static long[] infact = new long[N], fact = new long[N];
public static void main(String[] args) {
FastScanner sc = new FastScanner();
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
x = new long[k + 1][2];
y = new long[k + 1][2];
x1 = sc.nextInt() - 1;
y1 = sc.nextInt() - 1;
x2 = sc.nextInt() - 1;
y2 = sc.nextInt() - 1;
solver();
}
static void solver() {
init();
// initial
if(x1 == x2) x[0][1] = 1; // get the destination when step == 0
else x[0][0] = 1;
if(y1 == y2) y[0][1] = 1; // get the destination when step == 0
else y[0][0] = 1;
for(int i = 1; i <= k; i++){
// cal x
x[i][1] = x[i - 1][0];
x[i][0] = ((n - 2) * x[i - 1][0]) % p + ((n - 1) * x[i - 1][1]) % p;
// cal y
y[i][1] = y[i - 1][0];
y[i][0] = ((m - 2) * y[i - 1][0]) % p + ((m - 1) * y[i - 1][1]) % p;
// System.out.println(x[i][1] + " " + x[i][0] + " " + y[i][1] + " " + y[i][0]);
}
long res = 0;
for(int i = 0; i <= k; i++){
res += (C(k, i) * x[i][1]) % p * y[k - i][1] % p;
}
System.out.println(res % p);
}
static void init(){
fact[0] = 1;
infact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = fact[i - 1] * i % p;
infact[i] = qmi(fact[i], p - 2, p) % p; // 快速幂求逆元x
}
}
static long C(int a, int b){
return fact[a] * infact[b] % p * infact[a - b] % p;
}
static long qmi(long a, long k, long p){
long res = 1;
while(k > 0){
if(k % 2 == 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
}
}