AtCoder ARC #118 : D - Hamiltonian Cycle

Dで手間取りすぎた。
https://atcoder.jp/contests/arc118/tasks/arc118_d

問題

素数Pと、P未満の正整数a,bが与えられる。
以下を満たすP要素の数列を構築せよ。

• A[0]=A[P-1]=1、A[1]～A[P-2]には2～(P-1)が1回ずつ登場
• 隣接要素同士について、片方が片方のa倍またはb倍を満たす(mod Pで)

解法

P=2の時は自明なので、以下Pが3以上の時を考える。
aかbがPの原子根になるなら、P[i]=a^iとかP[i]=b^iが解になる。

そうでない場合、以下のグリッドを考えよう。
サイズをH*Wとする。H,Wはa^H,b^Wが1となる最小の正整数とする。
左下セルに1が書かれており、各セルには上に行くとa倍、右に行くとb倍(mod Pで)の値が書かれている。

このグリッド上で、左下セルから初めて(P-1)マスの長方形の区間を1回ずつたどって元の位置に戻る巡回路を考える。
この訪問でセルの値を拾い上げると、条件を満たす数列が作れる。(これで前者の条件を満たすことの証明はEditorial参照)
この長方形は、高さか幅が偶数なので、下記問題の通り巡回できる。
yukicoder : No.85 TVザッピング(1) - kmjp's blog

int P,A,B;
ll mo;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>A>>B;
	
	if(P==2) {
		cout<<"Yes"<<endl;
		cout<<"1 1"<<endl;
		return;
	}
	
	mo=P;
	set<int> S;
	if(A>1) S.insert(A);
	if(B>1) {
		if(modpow(B)!=A) S.insert(B);
	}
	
	FORR(x,S) {
		ll cur=1;
		FOR(i,P-2) {
			cur=cur*x%mo;
			if(cur==1) break;
		}
		if(i==P-2) {
			cout<<"Yes"<<endl;
			cur=1;
			FOR(i,P) {
				cout<<cur<<" ";
				cur=cur*x%mo;
			}
			cout<<endl;
			return;
		}
	}
	if(S.size()<=1) {
		cout<<"No"<<endl;
		return;
	}
	int x1=*S.begin();
	int x2=*S.rbegin();
	int r1=modpow(x1);
	int r2=modpow(x2);
	set<ll> T[2];
	vector<ll> V[2];
	
	FOR(j,2) {
		ll cur=1;
		V[j].push_back(1);
		FOR(i,P) {
			if(j==0) cur=cur*x1%mo;
			else cur=cur*x2%mo;
			if(cur==1) break;
			T[j].insert(cur);
			V[j].push_back(cur);
		}
	}
	
	FOR(k,2) {
		for(int tl=2;tl<=V[0].size();tl+=2) if((P-1)%tl==0) {
			int tw=(P-1)/tl;
			if(tw>V[1].size()) continue;
			
			vector<ll> R;
			set<ll> A;
			ll cur=1;
			FOR(y,tl) {
				R.push_back(cur);
				A.insert(cur);
				if(y<tl-1) cur=cur*x1%mo;
			}
			cur=cur*x2%mo;
			for(y=tl-1;y>=0;y--) {
				if(R.size()!=A.size()) break;
				FOR(x,tw-1) {
					R.push_back(cur);
					A.insert(cur);
					if(R.size()!=A.size()) break;
					if(x<tw-2) {
						if(y%2==1) {
							cur=cur*x2%mo;
						}
						else {
							cur=cur*r2%mo;
						}
					}
				}
				if(y) cur=cur*r1%mo;
			}
			if(A.size()==P-1) {
				R.push_back(1);
				cout<<"Yes"<<endl;
				FORR(r,R) cout<<r<<" ";
				cout<<endl;
				return;
			}
			
		}
		swap(x1,x2);
		swap(r1,r2);
		swap(T[0],T[1]);
		swap(V[0],V[1]);
	}
	
	cout<<"No"<<endl;
}

まとめ

過去の自分の作問がちょっとだけ役に立った。