题目
n*m(1<=n,m<=2e5,n*m<=2e5)的网格图，
有一些格子内已经放入了闹钟，当前时刻在[0,h)(1<=h<=1e9)之间
还有一些位置没有放闹钟，输入时用-1表示，
在放入这些闹钟的时候，你可以指定它们的初始时刻，只要在[0,h)即可
不同的闹钟，被指定的初始时刻可以不同
放完这些闹钟之后，你可以执行以下操作若干次，
每次选择一行或者一列，并将这些闹钟都往后调一个小时，
即，当前闹钟时刻x，x<h-1时，会被调到x+1；x=h-1时，会被调到0
求指定初始时刻的方案数，使得所有的闹钟可以被调到同一时刻，答案对1e9+7取模
实际用例总数t不超过5e4，但保证sum n*m<2e5
思路来源
乱搞ac
题解
其实和刚刚的abc280f很像，只是这个题更直接一些，
都有在线和离线两种做法，感觉很典中典
在线：带权并查集(hdu3047)；离线：建树然后dfs判环(abc280f)
而abc280f这个题，主要是要找出非零环，
于是对图dfs得到一棵树后，检查非树边是否可以被树边线性表示
这个题也可以采用一样的做法，将同一行内的，值不为-1的两列，x列和y列，
连边y->x，权值(val[y]-val[x])%h；连边x->y，权值(val[x]-val[y])%h，就化成了abc280f这个题
于是只需检查，不同行对于列的限制，是否存在矛盾即可
对每一行做完之后，每一列就无需再做一遍了，
因为如果行的限制满足，势必存在一个delta，
使得第一行的x列的数，加delta后，等于第二行的x列的数；
第一行的y列的数，加delta后，等于第二行的y列的数；
检查完没有矛盾之后，
对于确定的数(不是-1的数)所在的位置(x,y)，就直接将x行和y列这两个点直接连到一起，
连到一起后，当前图相当于被分成了若干个连通块，
而每将-1填成一个具体的数，都有h种选择，
并且，将(x,y)处的-1填成具体数后，
相当于将x行所在的联通和y列所在的连通块合并到一起
最后，需要将n行m列这n+m个点合并成一个连通块
设通过-1合并了x次，则答案为h的x次方，
感觉有点类似矩阵的秩
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=4e5+10,mod=1e9+7;
int t,n,m,h,par[maxn];
ll pos[maxn];
void init(int x){
for(int i=0;i<x;++i){
par[i]=i;
pos[i]=0;
}
}
int find(int x){
if(par[x]==x)return x;
int fa=par[x];//直接基类
par[x]=find(par[x]);//路径压缩
(pos[x]+=pos[fa])%=h;//树上前缀和 两链变一链 直接连树根
return par[x];//返回树根
}
//y比x大v
bool unite(int x,int y,ll v){
int px=find(x),py=find(y);
if(px==py){
if((pos[x]+v-pos[y])%h)return 0;
return 1;
}
//把y所在树的树根挂在x所在树的树根上 只改树根py
par[py]=px;//rank[py]=rank[y现在]-rank[y之前]==(rank[x]+v)-rank[y]
pos[py]=((pos[x]+v-pos[y])%h+h)%h;//注意rank可能有负 与将负旋为0的根是等价的
return 1;
}
int solve(){
vector<vector<ll> >a(n+1,vector<ll>(m+1,0));
int all=0,cnt=0;
init(m);
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
scanf("%lld",&a[i][j]);
}
}
for(int i=0;i<n;++i){
int las=-1;
for(int j=0;j<m;++j){
if(a[i][j]==-1)continue;
if(~las && !unite(las,j,(a[i][j]-a[i][las]+h)%h)){
return 0;
}
las=j;
}
}
/*
init(n);
for(int j=0;j<m;++j){
int las=-1;
for(int i=0;i<n;++i){
if(a[i][j]==-1)continue;
if(~las && !unite(las,i,a[i][j]-a[las][j])){
return 0;
}
las=i;
}
}*/
init(n+m);
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(~a[i][j])par[find(n+j)]=find(i);
}
}
for(int i=0;i<n+m;++i){
if(find(i)==i)cnt++;
}
int res=1;
for(int i=1;i<cnt;++i){
res=1ll*h*res%mod;
}
//printf("res:%d h:%d\n",res,h);
//printf("res:%d\n",res);
return res;
}
int main(){
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d%d%d",&n,&m,&h);
printf("%d\n",solve());
}
return 0;
}
/*
hdu3047 带权并查集
1 2
-1 -1
1 -1
-1 2
1 0 -1
-1 -1 2
n+m-1个点 现在有3个点
-1 -1 -1
-1 -1 -1
n+m-1个点 现在有0个点
*/