题目背景

WD整日沉浸在矩阵中,无法自拔……

题目描述

WD特别喜欢矩阵,尤其是\(01\)矩阵。

一天,CX给了WD一个巨大的\(n\)\(m\)列的\(01\)矩阵,WD发现这个矩阵每行、每列的异或值都是\(0\).

CX随后就问道:“WD,你知道有多少\(01\)矩阵每行每列异或值都是\(0\)吗!?”WD当然不会这个问题,于是他来请教你。

由于答案可能很大,输出结果模\(998244353\)的值即可。

输入输出格式

输入格式:

第一行一个数\(T\),表示数据组数。

接下来\(T\)行每行两个数\(n,m\),分别表示询问的行数和列数。

输出格式:

\(T\)行,每行一个数,表示答案\(mod\) \(998244353\)的结果。

输入输出样例

输入样例#1:

2
2 2
2 2018

输出样例#1:

2
851481696

说明

\(subtask1(11pts):~1\le T\le 10,~1\le n,m\le 4\)

\(subtask1(43pts):~1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000\)

\(subtask1(46pts):~1\le T\le 100,000,~1\le n,m\le 10^9\)

思路:

题意是让你求满足n行m列且每行每列异或值都是0的矩阵个数,因为是异或,所以只可能有两个值,\(0\)\(1\),那么每行可能的取值就是\(2^n\),然后最后值是0的情况是就是\(2^{n-1}\),然后扩展到列上,那么就是\((2^{n-1})^{m-1}\),然后自己再打打表就发现,显然这个式子是正确的,然后用快速幂求解,计算的过程中记得取模。

自己整理的题解

下面是我简洁的代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define mod 998244353
using namespace std;
ll n,m;
int t;
inline ll fpow(ll a, ll b) {
  if(!b) return 1;
  ll ans=1;
  for(;b;b>>=1,a=(a*a)%mod)
    if(b&1) ans=(ans*a)%mod;
  return ans;
}
int main() {
  scanf("%d",&t);
  while(t--) {
    scanf("%lld%lld",&n,&m);
    printf("%lld\n",fpow(fpow(2,n-1),m-1));
  }
  return 0;
}