学步园

这几天小机房选拔考试，向总很神奇的拿来了三套大约为省选难度的试题，嗯，这些题都很经典。

这道题的大意是这样的：给你P个N阶置换，你必须按顺序合成这些置换（1,2,..N,1,2,3,..,N,1,2,3）成为一个单位元，求最少合成步数。（N,P＜200）

这道题数据大水导致我一个模拟+cheat全过。。

其实是很不错的一道题，具体做法如下：

考虑ans mod p = y，ans=p*x+y ，可知前面这P*X个置换合成的置换和后面Y个置换合成的置换互为逆元，那我们枚举Y,就可以知道前P*X个置换该合成什么置换，然后将每一轮的P个置换合成为一个置换，那么就把这道题转化成了把一个置换转换成另一个置换的问题，对于置换群上的每一个位置构造一个模方程，利用同余模方程组即可求出X，复杂度为O(N²logN)。

数学题一向好编，因为这题的数据比较小，没有利用扩展欧几里得解模方程，直接枚举也可以秒出：

 program ex4;<br /> var<br /> go,t:array[0..200,0..200] of longint;<br /> a,b:array[0..200] of longint;<br /> i,j,k,o,n,s,p,lop,ans:longint;<br /> ok:boolean;</p> <p>function gcd(a,b:longint):longint;<br /> begin if b=0 then gcd:=a else gcd:=gcd(b,a mod b) end;</p> <p>begin<br /> assign(input,'plan.in');reset(input);<br /> assign(output,'plan.out');rewrite(output);<br /> readln(n,p);ans:=maxlongint;<br /> for i:=1 to n do<br /> for j:=1 to p do read(go[i,j]);<br /> for i:=1 to n do t[0,i]:=i;<br /> for i:=1 to p do<br /> for j:=1 to n do t[i,go[j,i]]:=t[i-1,j];<br /> for i:=0 to p-1 do begin<br /> ok:=true;<br /> for j:=1 to n do begin<br /> lop:=1;a[j]:=0;<br /> s:=t[i,j];o:=t[p,s];<br /> while o<>s do begin<br /> if o=j then a[j]:=lop;<br /> inc(lop);o:=t[p,o];<br /> end;<br /> if (s<>j)and(a[j]=0) then ok:=false;<br /> b[j]:=lop;<br /> end;<br /> if not ok then continue;<br /> for j:=1 to n do<br /> for k:=1 to n-j do<br /> if b[k]<b[k+1] then begin<br /> lop:=a[k];a[k]:=a[k+1];a[k+1]:=lop;<br /> lop:=b[k];b[k]:=b[k+1];b[k+1]:=lop;<br /> end;<br /> k:=ord(i=0);lop:=1;<br /> for j:=1 to n do begin<br /> while k mod b[j]<>a[j] do inc(k,lop);<br /> lop:=lop * b[j] div gcd(lop,b[j]);<br /> end;<br /> if ans>k*p+i then ans:=k*p+i;<br /> end;<br /> writeln(ans);<br /> close(input);close(output);<br /> end.<br />