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-1
m-1的矩阵中随意放置-1,1.在最后一列和最后一行控制合法性即可。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back using 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;
}
上一篇:.net core获取本地Ip地址的方法


下一篇:javascript 获取滚动条高度+常用js页面宽度与高度