「Luogu P5159」WD与矩阵

发表于 |
字数统计: 546 | 阅读时长 ≈ 2

求有多少个$n\times m$的矩阵，使得每行每列异或值都是$0$。

Data Range：$T\leq 10^5,1\leq n,m\leq 10^9$

Solution

先声明一下，$(n,m)$表示$n\times m$矩阵的答案，这里假定$n\leq m$，因为$(n,m)=(m,n)$。

不知道有没有人在看到这题的时候想到了NOIP 2018的填数游戏，按照这个思路，可以写一个爆搜跑一下小数据，这里记录一下我得到的小数据的答案：

$(2,2)=2,(2,3)=4,(2,4)=8,(2,5)=16,(2,6)=32\cdots$

$(3,3)=16,(3,4)=64,(3,5)=256,(3,6)=1024\cdots$

$(4,4)=512,(4,5)=4096,(4,6)=32768\cdots$

$(5,5)=65536\cdots$

首先考虑$(n,m)\div (n,m-1)$，把这个值记为$\operatorname{grow}(n)$，于是有：

$\operatorname{grow}(2)=2,\operatorname{grow}(3)=4,\operatorname{grow}(4)=8,\operatorname{grow}(5)=16\cdots$

所以$\operatorname{grow}(n)=2^{n-1}$。

接下来算$(n,n)$，有：

$(2,2)=2,(3,3)=16,(4,4)=512,(5,5)=65536$。

乍一看，没什么规律，所以将这些式子变个形：

$(2,2)=2^1,(3,3)=2^4,(4,4)=2^9,(5,5)=2^{16}\cdots$

啊哈！这样就有规律啦qwq！

于是就有$(n,n)=2^{(n-1)^2}$

综上，可以得出$(n,m)\equiv 2^{(n-1)^2}\times(2^{n-1})^{m-n}$。

于是就可以用快速幂做啦qwq。

但是这样子$\texttt{Subtask 3}$会TLE，所以考虑优化。

不是有欧拉定理吗？

所以说可以把$(n-1)^2$模个$\varphi(998244353)=998244352$，就可以完结撒花啦qwq！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MOD=998244353;
ll test,length,width,base,grow;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent,ll mod)
{
    if(!exponent)
    {
        return 1;
    }
    ll temp=qpow(base,exponent>>1,mod),res=temp*temp%mod;
    if(exponent&1)
    {
        res=res*base%mod;	
    }	
    return res;
}
int main()
{
    test=read();
    for(register int i=0;i<test;i++)
    {
        length=read(),width=read();
        if(length>width)
        {
            swap(length,width);
        }
        base=qpow(2,(length-1)*(length-1)%(MOD-1),MOD);
        grow=qpow(2,length-1,MOD);
        printf("%lld\n",base*qpow(grow,width-length,MOD)%MOD);
    }
}