Codeforces ECR #178 : G. Modulo 3

これも珍しい設定かも。
https://codeforces.com/contest/2104/problem/G

問題

Function Graphが与えられる。
このグラフに対し、以下の問題を考える。

• 正整数kが与えられる。初期状態で全点は色1で塗られている。
• 点vと色c (cは1以上k以下)を選択すると、vから到達可能な点が全部cで塗られる。
• 上記処理を何度でも行える時、彩色の仕方を3で割った余りを答えよ。

以下のクエリについて順次答えよ。

• 正整数x,y,kが与えられる。点xから出る辺の先を点yとしたとき、kに対する問題の解を答えよ。

なお、クエリ毎に辺の行き先の変更は積み重なるが、彩色は毎回リセットされる。

解法

強連結成分の数がcなら、解は(k^c)%3となる。
kが3の倍数の時はcに依存しないし、kが3の倍数でないとき、cの偶奇だけわかればよい。
よってクエリ毎にcの偶奇を求めればよい。

SegTreeの要領で、クエリの区間に対し辺を追加しよう。
そしてこの木構造をDFSしながら、連結関係を求めて行く。
閉路長が奇数の場合、閉路ができることによってcの偶奇は変化しない。
そこで、有向辺ではなく無向辺を考え、偶数長の閉路ができるか判定すればよい。
これは頂点を倍化したグラフを考えればよい。

int N;
vector<pair<int,int>> G[202020];
int Q;
int K[202020];
int ret[1<<20];

const int NV=1<<19;
vector<pair<int,int>> ev[1<<20];

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<array<int,6>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; hist.clear(); FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};
UF_pop<404040> uf;

void update(int x,int y, pair<int,int> v,int l=0,int r=NV,int k=1) {
	if(l>=r) return;
	if(x<=l && r<=y) {
		ev[k].push_back(v);
	}
	else if(l < y && x < r) {
		update(x,y,v,l,(l+r)/2,k*2);
		update(x,y,v,(l+r)/2,r,k*2+1);
	}
}


void dfs(int k,int L,int R,int num) {
	int cur=uf.hist.size();
	FORR2(a,b,ev[k]) {
		if(uf[a*2]==uf[b*2+1]) {
			num++;
		}
		uf(a*2,b*2+1);
		uf(a*2+1,b*2);
	}
	
	if(L+1==R) {
		ret[L]=num%2;
	}
	else {
		int M=(L+R)/2;
		dfs(k*2,L,M,num);
		dfs(k*2+1,M,R,num);
	}
	
	
	while(uf.hist.size()>cur) uf.pop();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		G[i].push_back({0,x-1});
	}
	FOR(i,Q) {
		cin>>x>>y>>K[i];
		G[x-1].push_back({i+1,y-1});
	}
	FOR(i,N) {
		G[i].push_back({Q+1,0});
		FOR(j,G[i].size()-1) {
			update(G[i][j].first,G[i][j+1].first,{i,G[i][j].second});
		}
	}
	dfs(1,0,1<<19,0);
	FOR(i,Q) {
		if(K[i]%3!=2) {
			cout<<K[i]%3<<endl;
		}
		else {
			if((N-ret[i+1])%2==0) {
				cout<<1<<endl;
			}
			else {
				cout<<2<<endl;
			}
		}
		
	}
	
}

まとめ

この偶数長の閉路の判定法は面白いな。