abc232e Rook Path

开始看成走到相邻格子，后面发现是车的走法。。。

发现可以将整个图分成四个部分，
(x1,y1)
\((x,y1) (x \neq x1)\)
\((x1,y) (y\neq y1)\)
\((x,y) (x\neq x1 ,y\neq y1)\)
然后每一部分中的点的答案都是相同的，转移即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef long long ll;
const ll mo=998244353;
const int N=1e6+5;
ll n,m,k;
int a,b,c,d;
struct mat{
    ll a[4][4];
};
mat t,y;
void add(ll &x,ll y){
    x=(x+y)%mo;
}
mat mul(mat a,mat b){
    mat c;
    fo(i,0,3) fo(j,0,3) c.a[i][j]=0;
    fo(i,0,3) fo(j,0,3) fo(k,0,3) {
        add(c.a[i][j], a.a[i][k]*b.a[k][j]%mo);
    }
    return c;
}
void power(ll b){
    while (b) {
        if (b&1) t=mul(t,y);
        y=mul(y,y);
        b/=2;
    }
}
int main() {

    // #ifdef  LOCAL
    //     freopen("in.txt","r",stdin);
    //     freopen("out.txt","w",stdout);
    // #endif

    scanf("%lld %lld %lld",&n,&m,&k);
    scanf("%d %d %d %d",&a,&b,&c,&d);

    t.a[0][0]=t.a[1][1]=t.a[2][2]=t.a[3][3]=1;

    ll z[4][4]={
        0,m-1,n-1,0,
        1,m-2,0,n-1,
        1,0,n-2,m-1,
        0,1,1,n+m-4
    };
    fo(i,0,3) fo(j,0,3) y.a[i][j]=z[i][j];

    power(k);

    if (a==c && b==d) printf("%lld",t.a[0][0]);
    if (a==c && b!=d) printf("%lld",t.a[1][0]);
    if (a!=c && b==d) printf("%lld",t.a[2][0]);
    if (a!=c && b!=d) printf("%lld",t.a[3][0]);


}