AcWing 第127场周赛 构造矩阵

构造题目，考虑去除掉最后一行最后一列先进行考虑，假设除了最后一行和最后一列都已经排好了（你可以随便排），那么分析知最后一个数字由限制以外其他都已经确定了，无解的情况是k为-1

并且n，m的奇偶性不同其余均有解 并且方案数就是2**（n-1)*(m-1）%p 发现数很大，欧拉降幂

原式等价于2**(n-1)%(p-1)*(m-1)%(p-1) %p

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 2e5+10,p = 1e9+7;
ll n,m,k;ll qmi(ll a,ll b,ll p){ll ans = 1;while(b){if(b&1)ans = ans*a%p;b>>=1;a = a*a%p;}return ans;
}
void solve()
{cin>>n>>m>>k;if(k==-1&&(n%2!=m%2))cout<<-1;else{ll t = ((n-1)%(p-1))*((m-1)%(p-1));cout<<qmi(2,t,p);}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;_ = 1;while(_--)solve();return 0;
}

贴一个y总的分析图片

当然你写两次快速幂也是一样的，这里也是知道你底数可以随便模这个性质

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 2e5+10,p = 1e9+7;
ll n,m,k;ll qmi(ll a,ll b,ll p){ll ans = 1;while(b){if(b&1)ans = ans*a%p;b>>=1;a = a*a%p;}return ans;
}
void solve()
{cin>>n>>m>>k;if(k==-1&&(n%2!=m%2))cout<<0;else{// ll t = ((n-1)%(p-1))*((m-1)%(p-1));// cout<<qmi(2,t,p);ll t = qmi(2,m-1,p);cout<<qmi(t,n-1,p);}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;_ = 1;while(_--)solve();return 0;
}