IOPC12-IOPC1200 : Hardware upgrade

codechef

問題概要

ノード数V(<10^4)の木がある。次を満たす置換σが何通りあるか求める問題。

  1. σ(0)=0
  2. (v,u) in E ⇒ (σ(v), σ(u)) in E

解法

まず、0を根とした有向木にする。各部分木に対して同型判定が簡単にできれば再帰的に掛け合わせて答えを求めることができる。問題は各部分木に対して同型判定を以下に効率よくやるかだが、部分木にハッシュ値を割り振れば高確率で同型判定ができる。ある部分木のハッシュ値は、そのノードの子を根とした部分木のハッシュ値の集合から生成する。このときローリングハッシュみたいな作り方だと容易に衝突してしまうらしく、ハッシュ値の生成方法を変えることによってWAがとれてACとなった。

acceptされたコード

計算量O(V*log V)くらい？

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;

typedef unsigned long long int64;

const int MAX_N = 1e4;
const int64 MOD = 1000000007;

int N;
int64 fact[MAX_N + 1];
int64 shake[2][MAX_N + 1];
int depth[MAX_N];
bool visited[MAX_N];
vector<int> graph[MAX_N];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		graph[i].clear();
	}
	memset(depth, 0, sizeof(depth));
	for(int i=0; i<N-1; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
}

//有向グラフへの変換のための小細工。depthを計算する。
void order(int v){
	visited[v] = true;
	for(int i=0; i<(int)graph[v].size(); i++){
		const int u = graph[v][i];
		if(!visited[u]){
			depth[u] = depth[v] + 1;
			order(u);
		}
	}
}

//返り値は(場合の数、vを頂点にしたサブツリーのハッシュ値)
pair<int64, pair<int64, int64> > rec(int v){
	int64 ret = 1;
	int64 h1 = 1, h2 = 1; //初期値は適当

	vector< pair<int64,int64> > hs;
	const int M = graph[v].size();
	hs.reserve(M);
	for(int i=0; i<M; i++){
		pair<int64, pair<int64,int64> > x =  rec(graph[v][i]);
		ret = ret * x.first % MOD;
		hs.push_back(x.second);
	}

	sort(hs.begin(), hs.end());

	for(int i=0, cnt=1; i<M; i++){
		h1 += shake[0][i] * hs[i].first;
		h2 += shake[1][i] * hs[i].second;
		if(i<M-1 && hs[i]==hs[i+1]){
			cnt++;
		}
		else{
			ret = ret * fact[cnt] % MOD;
			cnt = 1;
		}
	}

	pair<int64,int64> hash(h1, h2);
	return make_pair(ret, hash);
}

int solve(){
	memset(visited, false, sizeof(visited));
	order(0);

	//0を根とした有向木になるようにグラフをいじる
	for(int i=0; i<N; i++){
		vector<int> tmp;
		for(int j=0; j<(int)graph[i].size(); j++){
			if(depth[i] < depth[graph[i][j]]){
				tmp.push_back(graph[i][j]);
			}
		}
		graph[i] = tmp;
	}

	return (int)rec(0).first;
}

int main(){
	fact[0] = 1;
	for(int i=1; i<=MAX_N; i++){
		fact[i] = i * fact[i-1] % MOD;
	}

	for(int i=0; i<2; i++){
		for(int j=0; j<=MAX_N; j++){
			shake[i][j] = rand();
		}
	}

	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}
	return 0;
}