kmjp's blog

競技プログラミング参加記です

Codeforces #278 Div1 C. Prefix Product Sequence

かなり速く解けたと思ったのに、コーナーケース見落とした…。
http://codeforces.com/contest/487/problem/C

問題

Nが与えられる。

1~NのPermutationとなるA[i]のうち、A[0]%N、A[0]*A[1]%N、A[0]*A[1]*A[2]%N、…A[0]*A[1]*...*A[N-1]%Nが0~(N-1)のPermutationとなるようなものを答えよ。

解法

B[i]=A[0]*A[1]*...*A[i]とする。
途中A[i]==Nとすると以後B[i]=B[i+1]=...=0となり、0が複数回出てしまう。
よってA[i]==Nとなるのは最後のi=N-1でなければならない。

また、B[N-2]までは0にならないようにしないといけない。
Nが合成数の場合、Nの約数が何度か出てくるので、B[N-2]==B[N-1]==0となり条件を満たせない。
ただし例外が2つあり、N==1とN==4である。

  • N==1の時、解はA[0]=1一択である。
  • N==4の時、A=[1,3,2,4]とするとB=[1,3,2,0]となり条件を満たす。
  • その他Nが素数の時、B=[1,2,3,...,N-1,0]となるようにAを決めればよい。すなわちA[0]=1、A[1]=2/1、A[2]=3/2、…、A[i]=(i+1)/iとすればよい。
ll rev(ll a, ll mo) {
	ll r=1, n=mo-2;
	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;
	
	int N;
	cin>>N;
	if(N==1) return _P("YES\n1\n");
	if(N==4) return _P("YES\n1\n3\n2\n4\n");
	
	for(i=2;i*i<N;i++) if(N%i==0) return _P("NO\n");

	_P("YES\n1\n");
	FOR(i,N-2) _P("%d\n", (i+2)*rev(i+1,N)%N);
	_P("%d\n",N);
}

まとめ

N==4の見逃しが痛い…。
恐らく同じミスした人は多数いただろう。