Codeforces #588 Div1 D. Wojtek and Card Tricks

結構実装が面倒な問題。
https://codeforces.com/contest/1229/problem/D

問題

1～KのPermutationがN通り与えられる。
f(L,R)とはPermutationのL～R番目のものを任意回数適用して得られる置換の組み合わせ数とする。
0≦L≦R＜Nの全通りにおけるf(L,R)の総和を求めよ。

解法

Kが5なのでPermutationは高々120通り。
事前にPermutationの積も求めておこう。
仮にLを固定すると、Rを大きくするごとに置換の数が増加していく。
そこで、Lを大きなところからだんだん小さくしていき、その際に置換の数が変化するRの位置をずらしていこう。
そのようなRは高々120か所しかないので、およそO(N*K!)で解ける。

int N,K;
int P[202020];

vector<vector<int>> V;
map<vector<int>,int> T;
int pre[120];
int did[120];
int mult[120][120];

 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	vector<int> W;
	FOR(i,K) W.push_back(i);
	set<pair<int,int>> S;
	do {
		V.push_back(W);
		x=T.size();
		T[W]=x;
		pre[x]=N;
		S.insert({N,x});
	} while(next_permutation(ALL(W)));
	
	
	FOR(x,V.size()) FOR(y,V.size()) {
		vector<int> a=V[x];
		vector<int> b=V[y];
		vector<int> c;
		FORR(i,b) c.push_back(a[i]);
		mult[x][y]=T[c];
	}
	
	
	FOR(y,N) {
		vector<int> C(K);
		FOR(x,K) cin>>C[x], C[x]--;
		P[y]=T[C];
	}
	
	ll ret=0;
	for(x=N-1;x>=0;x--) {
		ZERO(did);
		vector<int> C;
		S.erase({pre[P[x]],P[x]});
		pre[P[x]]=x;
		S.insert({pre[P[x]],P[x]});
		
		int num=1;
		did[0]=1;
		int pre=x;
		FORR(s,S) {
			ret+=(s.first-pre)*num;
			pre=s.first;
			if(did[s.second]==0) {
				C.push_back(s.second);
				num=1;
				ZERO(did);
				did[0]=1;
				queue<int> Q;
				Q.push(0);
				while(Q.size()) {
					int cur=Q.front();
					Q.pop();
					FORR(c,C) {
						y=mult[cur][c];
						if(did[y]==0) {
							num++;
							did[y]=1;
							Q.push(y);
						}
					}
				}
			}
			
		}
		ret+=(N-pre)*num;
		
	}
	cout<<ret<<endl;
	
}

まとめ

やりたいことはわかっても実装が割とめんどい。