题目大意

题意

分析

图论结论题

抽象成图论

分析

对要涂色的格子(x,y)(x,y) 连一条边 x↔yx \leftrightarrow y

那么对于能够把第四个格子染成黑色的情况来说

$ x_1 \leftrightarrow y_1\leftrightarrow x_2 \leftrightarrow y_2$ , 4个点联通，行列也联通

那么对于把全部各自染成黑色之后所有的行列都联通

可以发现可以把问题抽象为二分图一部有 nn 个结点，另一部有 mm 个结点

从 $ x_1 \leftrightarrow y_1\leftrightarrow x_2 \leftrightarrow y_2$ 也可以看出 x yx \ y 交替相连，并且无环

那么问题就是在问一个左边有 n 个点，右边有 m 个点的二分图中生成树的方案。

结论

​ res = nm−1∗mn−1res \ = \ n^{m-1} * m^{n-1}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int qmi(int a,int b){
    int res = 1;
    while(b){
        if(b&1) res = res *a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
void solve(){
    int n,m;cin>>n>>m;
    cout << (qmi(n,m-1)*qmi(m,n-1))%mod << endl;
}


signed main(){
    int t;cin>>t;
    while(t--) solve();
};