题解 P5159 【WD与矩阵】

· · 题解

这么水的题目居然都没有人发题解QwQ？

emmm，比赛的时候只看了第一题然后惊讶地发现这居然是一道真·打卡题！于是开心o(￣▽￣)ブ地收下了这100分

怎么说呢，既然是01矩阵，那么每行每列（这里我们要把每行每列的最后一个值排除在外）的最终值就只有0和1两种可能（もちろん）本题要求每行每列的值均为0，那么很容易想到，最后一个数字的值是固定的，就好像下面这个矩阵(x代表还没有填入数字的位置)

0 0 1 x

1 0 1 x

0 1 1 x

x x x x

除了（4，4）暂时没办法确定之外，其他的数值都是确定的喵。所以矩阵变成了这样

0 0 1 1

1 0 1 0

0 1 1 0

1 1 1 1

此时x的值也变成了一个定值，就是0，并且我们可以很容易地证明，最后一行一定是一个满足要求的行（既然每一行的每一个值都和他上面的那一个已经满足条件的行的值不一样，那他本身的数值自然也是0）

不难发现，这道题就是让你求一个nm的矩阵中间那一个（n-1）（m-1）的01矩阵到底有多少种可能，也就是说，这道题只是一道简单的

快速幂

接下来又是愉快的上代码时间

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

请务必让我通过嘛OwO