Codeforces #618 Div1 D. Around the World

これは本番解き切れなかった。
https://codeforces.com/contest/1299/problem/D

問題

N頂点M辺の連結無向グラフが与えられる。
このグラフで頂点1を通る閉路は、長さ3のものしかない。

辺にはコストが設定されており、パスのコストは辺のコストのxorを取ったものとする。
頂点1の辺の一部を削除するとき、頂点1を通るコスト0の閉路が存在しないのは何通りか。

解法

頂点1の隣接点をSとする。
S同士の間に辺が張られることがあったとしても1頂点あたり1個である。
よって、頂点1とつながる辺を削除し、各連結成分内で基底ベクトルを求めよう。

コストは高々31なので、取りえる部分グラフの基底ベクトルはそれほど種類がなく、374通りしかない。
そこで、頂点1とこれらの連結成分をつなげる・繋げないときに基底ベクトルがどう遷移するかをDPで数え上げて行こう。
基底ベクトルが空以外のケースの組み合わせの和を取ればよい。

int N,M;
vector<pair<int,int>> E[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

map<vector<int>,int> BM;
vector<int> B[505];
int mp[400][400];

vector<int> T[101010];
vector<int> V[101010];
int vis[101010];
ll mo=1000000007;

set<pair<int,int>> did;



int gf2_rank(vector<int>& V) { /* input */
	int i,j;
	int N=V.size();
	FOR(i,N) {
		int x=max_element(V.begin()+i,V.end())-V.begin();
		if(V[x]==0) break;
		swap(V[i],V[x]);
		int msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		FOR(j,N) if(j!=i) if(V[j]&msb) V[j]^=V[i];
	}
	return N-count(V.begin(),V.end(),0);
}

void dfs_vec(int cur,vector<int> V) {
	if(cur==-1) {
		int x=gf2_rank(V);
		if(x==V.size() && BM.count(V)==0) {
			int x=BM.size();
			B[x]=V;
			BM[V]=x;
		}
		return;
	}
	
	int i;
	dfs_vec(cur-1,V);
	FOR(i,1<<cur) {
		V.push_back((1<<cur)|i);
		dfs_vec(cur-1,V);
		V.pop_back();
	}
}

void dfs(int cur,int pre,int v,int id) {
	if(cur==0) return;
	if(did.count({pre,cur})) return;
	did.insert({cur,pre});
	if(vis[cur]!=-1) {
		V[id].push_back(v^vis[cur]);
		return;
	}
	vis[cur]=v;
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,v^e.second,id);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	
	scanf("%d%d",&N,&M);
	FOR(i,M) {
		scanf("%d%d%d",&x,&y,&r);
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
		if(x>1 && y>1) uf(x-1,y-1);
	}
	
	FORR(e,E[0]) T[uf[e.first]].push_back(e.first);
	
	B[0]={-1};
	BM[B[0]]=0;
	dfs_vec(4,{});
	for(i=1;i<BM.size();i++) {
		for(j=1;j<=i;j++) {
			vector<int> A=B[i];
			FORR(v,B[j]) A.push_back(v);
			
			if(gf2_rank(A)==A.size()) {
				sort(ALL(A));
				reverse(ALL(A));
				assert(BM.count(A));
				mp[i][j]=mp[j][i]=BM[A];
			}
		}
	}
	ll from[400]={};
	from[BM[{}]]=1;
	MINUS(vis);
	
	for(j=1;j<N;j++) if(uf[j]==j) {
		dfs(j,j,0,j);
		
		if(gf2_rank(V[j])!=V[j].size()) {
			x=0;
		}
		else {
			assert(BM.count(V[j]));
			x=BM[V[j]];
		}
		
		ll to[400]={};
		FOR(i,BM.size()) to[i]=from[i];
		if(T[j].size()==1) {
			FOR(i,BM.size()) to[mp[i][x]]+=from[i];
		}
		else {
			assert(T[j].size()==2);
			int mask=0;
			FORR(e,E[T[j][0]]) if(e.first==0 || e.first==T[j][1]) mask^=e.second;
			FORR(e,E[T[j][1]]) if(e.first==0) mask^=e.second;
			if(mask==0) {
				y=0;
			}
			else {
				y=BM[{mask}];
			}
			FOR(i,BM.size()) {
				to[mp[i][x]]+=2*from[i];
				to[mp[i][mp[x][y]]]+=from[i];
			}
		}
		FOR(i,BM.size()) from[i]=to[i]%mo;
	}
	
	ll ret=0;
	FOR(i,BM.size()) if(i) ret+=from[i];
	cout<<ret%mo<<endl;
	
}

まとめ

言われてみればそうなんだけど本番さっくり書ける気がしない。