Codeforces #836 : Div2 E. Tick, Tock

6問回の5問目で割と苦戦。
https://codeforces.com/contest/1758/problem/E

問題

N*Mのグリッドが与えられる。
また正整数Hが与えられる。
グリッドの各マスには0～(H-1)の数値が入っているか、または空欄である。

行または列を選択して、各セルをインクリメントする(Hに到達したマスは0にする)ことを考える。
空きマスに0～(H-1)の値を入れたとき、上記手順で全マスの値を同じにできるのは何通りか。

解法

同じ列に2行、または同じ行に2列値が埋まっている箇所があれば、列同士または行同士の差が確定される。
そんな感じでUnion Findの要領で差が確定する行・列を定めていこう。
途中矛盾が生じたら解は0。
そうでない場合、H^(連結成分数-1)通りだけ自由度がある。

int T;
int H,W;
ll V;
vector<int> X[202020];
vector<pair<int,int>> RE[202020];
vector<pair<int,int>> CE[202020];
const ll mo=1000000007;
set<int> Rs,Cs;
ll RT[202020],RB[202020];
ll CT[202020],CB[202020];;
ll ret;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<404040> uf;

void dfsR(int y,ll T,int b) {
	T=(T+V)%V;
	if(RT[y]!=-1) {
		if(RT[y]!=T) ret=0;
		return;
	}
	RB[y]=b;
	RT[y]=T;
	FORR2(e,c,RE[y]) dfsR(e,T+c,b);

}
void dfsC(int y,ll T,int b) {
	T=(T+V)%V;
	if(CT[y]!=-1) {
		if(CT[y]!=T) ret=0;
		return;
	}
	CB[y]=b;
	CT[y]=T;
	FORR2(e,c,CE[y]) dfsC(e,T+c,b);

}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>V;
		FOR(y,H) RE[y].clear(), RT[y]=-1;
		FOR(x,W) CE[x].clear(), CT[x]=-1;
		uf.reinit(H+W);
		int vis=0;
		FOR(y,H) {
			X[y].resize(W);
			int pre=-1;
			FOR(x,W) {
				cin>>X[y][x];
				if(X[y][x]!=-1) {
					vis=1;
					uf(y,H+x);
					if(pre>=0) {
						CE[pre].push_back({x,X[y][x]-X[y][pre]});
						CE[x].push_back({pre,X[y][pre]-X[y][x]});
						uf(H+pre,H+x);
					}
					pre=x;
				}
			}
		}
		FOR(x,W) {
			int pre=-1;
			FOR(y,H) if(X[y][x]!=-1) {
				if(pre>=0) {
					RE[pre].push_back({y,X[y][x]-X[pre][x]});
					RE[y].push_back({pre,X[pre][x]-X[y][x]});
					uf(pre,y);
				}
				pre=y;
			}
		}
		
		ret=1;
		if(vis==0) {
			FOR(i,H+W-1) ret=ret*V%mo;
		}
		else {
			
			FOR(y,H) FOR(x,W) if(X[y][x]!=-1) {
				if(RT[y]==-1) dfsR(y,0,y);
				if(CT[x]==-1) dfsC(x,0,x);
				ll d=(X[y][x]+V-RT[y]+V-CT[x])%V;
				if(X[RB[y]][CB[x]]==-1) X[RB[y]][CB[x]]=d;
				if(X[RB[y]][CB[x]]!=d) {
					//cout<<y<<x<<" "<<RB[y]<<" "<<CB[x]<<" "<<X[y][x]<<" "<<d<<" "<<X[RB[y]][CB[x]]<<" "<<RT[y]<<CT[x]<<endl;
					ret=0;
				}
			}
			int num=0;
			FOR(i,H+W) if(uf[i]==i) num++;
			FOR(i,num-1) ret=ret*V%mo;
			
		}
		cout<<ret<<endl;
	}
}

まとめ

考察は余り複雑でない気がするが、手間取ってしまった。