洛谷P5159 WD与矩阵

题目背景

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

题目描述

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

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

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#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;

}

巴特西

洛谷P5159 WD与矩阵

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章