解题思路
发现每一行,每一列前n-1,m-1确定则最后一列 => 判断成立条件
long long 范围 小于10^19
高范围=>__int128搏一搏 or 直接转为python => 费马小定理/欧拉函数
费马小定理
具体内容
实际应用
两次快速幂
快速幂模板
int qmi(int a,int k,int p)
{
int res=1;
while(k)
{
if(k&1) res=(LL)res*a%p;
k>>=1;
a=(LL)a*a%p;
}
return res;
}
AC代码
费马小定理
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
LL qmi(LL a, LL k, LL p) // 求a^k mod p
{
int res = 1 ;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
LL n,m,k;
cin>>n>>m>>k;
if(k==-1&&m%2!=n%2)
{
cout<<"0";
}
else
{
LL res=(n-1)%(mod-1)*((m-1)%(mod-1))%(mod-1);
cout<<qmi(2,res,mod);
}
return 0;
}
两次快速幂
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
LL qmi(LL a, LL k, LL p) // 求a^k mod p
{
int res = 1 ;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
LL n,m,k;
cin>>n>>m>>k;
if(k==-1&&m%2!=n%2)
{
cout<<"0";
}
else
{
cout<<qmi(qmi(2,n-1,mod),m-1,mod);
}
return 0;
}