yukicoder : No.2045 Two Reflections

シンプルで良い。
https://yukicoder.me/problems/no/2045

問題

正整数N,P,Qが与えられる。
A[i]=iであるようなN要素の整数列Aが与えられる。
以下の処理を任意回数繰り返すとき、生成できる数列は何通りか。

• Aのprefix P要素を反転する
• Aのsuffix Q要素を反転する

解法

コーナーケースとして、P,Qの片方が1かNである場合や、P+Q≦Nである場合はまぁ自明なので先に片付けてしまおう。
あとは、P,Qが2以上N未満で、かつP+Q＞Nの場合である。

同じ処理を2回連続で行う意味はないので、行うとすると前者と後者の処理を交互に行う1択である。
各要素について、元の位置に戻るまでの処理回数を求めよう。
それらの最小公倍数を求めればそれが解。

int N,P,Q;
const ll mo=998244353;
int vis[202020];

void out(ll v) {
	cout<<v<<endl;
	exit(0);
}

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

int go1(int x) {
	if(x<P) return P-1-x;
	return x;
}
int go2(int x) {
	if(x>=N-Q) return N-1-(x-(N-Q));
	return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P>>Q;
	
	if(P==1) out((Q>1)+1);
	if(Q==1) out((P>1)+1);
	if(P==N&&Q==N) out(2);
	if(P==N||Q==N) out(4);
	if(P+Q<=N) out(4);
	
	map<ll,int> V;
	FOR(i,N) if(vis[i]==0) {
		x=i;
		int step=0;
		while(step==0||x!=i) {
			vis[x]=1;
			x=go1(x);
			x=go2(x);
			step+=2;
		}
		auto W=enumpr(step);
		FORR2(a,b,W) V[a]=max(V[a],b);
	}
	
	ll ret=1;
	FORR2(a,b,V) {
		FOR(x,b) ret=ret*a%mo;
	}
	cout<<ret<<endl;
}

まとめ

問題設定がシンプルな問題はいいよね。