Codeforces Round #447 (Div. 2) B. Ralph And His Magic Field 数学

题目链接

题意：给你三个数n,m,k;让你构造出一个nm的矩阵，矩阵元素只有两个值（1，-1),且满足每行每列的乘积为k，问你多少个矩阵。

解法：首先，如果n，m奇偶不同，且k=-1时，必然无解：

设n为奇数，m为偶数，且首先要满足每行乘积为-1，那么每行必然有奇数个-1，那么必然会存在有偶数个-1.。满足每列乘积为-1，那么每列必然有奇数个-1，那么必然存在奇数个-1.互相矛盾。

剩下的就是有解的情况了。

我们可以在n-1m-1的矩阵中随意放置-1，1.在最后一列和最后一行控制合法性即可。

#include#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_backusing namespace std;LL gcd(LL a,LL b){ return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){ return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){ LL ans=1;while(b){ if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
LL mod=1e9+7;
int main(){ ios::sync_with_stdio(false);LL n ,m ,k;cin>>n>>m>>k;if(k==-1&&(n+m)%2==1)return cout<<0,0;cout<<powmod(powmod(2,n-1,mod),m-1,mod);return 0;
}