かなり速く解けたと思ったのに、コーナーケース見落とした…。
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の見逃しが痛い…。
恐らく同じミスした人は多数いただろう。