信息學(xué)集訓(xùn)隊(duì)作業(yè)taszad

1、Tasowanie原題中文翻譯算法分(c1,c2,c3,cn)，可將這個(gè)狀態(tài)用置換表示為1 2 3 c1 c2 c3 1 2 3 n a1 a2 a3 an給出一個(gè)1至n的置換B，求一個(gè)1至n的置換A，使Al=B把置換寫成若干個(gè)循環(huán)相乘的形式，設(shè)A=(a1,0 a1,2 a1,k1-1)(a2,0 a2,1 a2,k2-1)(am,0 am,1 am,km-1計(jì)算l(l*)時(shí)ai1j1與ai2j2(i1i2中ai1j1ai1,)，ai1,的后繼與ai1,是一個(gè)循環(huán)的，因此在2中ai1,j1的后繼在中與ai1,j12中與ai1,j1A中與ai1,j1l中與ai1,j1是一個(gè)循環(huán)的，在中與ai1

2、題目來(lái)源：POI設(shè)A=(a0 a1 am-1)，則在計(jì)算Al時(shí)，有可能出現(xiàn)分成多個(gè)循環(huán)的情況。a0由于A可以寫成(a1 a2 am-1 a0)，這和(a0 a1 am-1)在形式上是一樣的，當(dāng)l=k時(shí)，ap的后繼將由Ak-1中的a(p+k-1) mod m變?yōu)閍(p+k-1) mod m在A中的后繼即a(p+k) mod mgcd(l,m)表示l與m的最大公約數(shù)。因?yàn)閍p的后繼為a(p+lmodm，而a(p+lmod m后繼為a(p+2l) mod m。要完成一個(gè)循環(huán)，必定要把一個(gè)aq的后繼為ap，設(shè)q=(p+(x-1)*lmod m，則 p=(p+x*lmod m。其中x就是循環(huán)節(jié)長(zhǎng)度的整數(shù)

3、倍，在中間取一個(gè)最小的正整數(shù)即原來(lái)A中的一個(gè)循環(huán)，怎么做呢？現(xiàn)在假設(shè)要將B1=(b10 b11 b1m1-1)、B2=(b20 b21 b2m2-1)、Bt=(bt0bt1 btm1)，設(shè)A中的一個(gè)循環(huán)節(jié)A=(a0a1 的后繼為a(0+l) mod m，而b10的后繼為b11，因此al mod m=b10，同理可找到所有B1中的元1256源程參考書籍算法藝術(shù)與信息學(xué)競(jìng)劉汝佳 亮 組合數(shù)學(xué)(第3 版盧開澄 盧華明 感謝1：5 1253412453或21453POI 2003 Copyright (C), 03-2004,$I-,Q-,R-,S-inf = ; / 輸入文件 ouf = ; / 輸

4、出文件 maxn = 1000000;maxl=1000000; buf : array0.16383 of a / 已知的b : array1.maxn of / 臨時(shí)存放aaa : array0.maxn of checked : array1.maxn of toti表示b中長(zhǎng)為i的循環(huán)的個(gè)數(shù)，這里用的是桶排序 tot : array0.maxn of longint;nexti表示b中與i所代表循環(huán)長(zhǎng)度相等的下一個(gè)循環(huán) next : array1.maxn of longint;firsti表示b中長(zhǎng)度為i的第一個(gè)循環(huán)的代表元素 first : array1.maxn of longi

5、nt;lpp_li,1表示第i個(gè)質(zhì)數(shù)，pp_li,2表示l中只含有pp_1i,1的最大的約數(shù) tpp_l : longint;pp_l : array0.maxn, 1.2 of / n和n, l : / 輸入 procedureinit; i:longint; assign(input,inf);reset(input); settextbuf(input, buf);read(n, fori:=1tondo / 對(duì)lprocedureready; i : longint; tmp:longint;tmp := l; tpp_l:=0;fori:=2toround(sqrt(tmp)do i

6、ftmpmodi=0then pp_ltpp_l,1:=i; pp_ltpp_l,2:=1; pp_ltpp_l,2:=pp_ltpp_l,2*i; tmp := tmp div i;untiltmpmodi0; iftmp0then pp_ltpp_l,1:=tmp; pp_ltpp_l, 2 := procedureGetC; i,j:longint; this : fillchar(first, sizeof(first), fillchar(next, sizeof(next), fillchar(checked,sizeof(checked),0); for i := 1 to n

7、doifnotcheckedithen j := i; this:=0;whilenotcheckedjdo checkedj:=true; j := bj; nexti:=firstthis; firstthis := i;procedure b中所有長(zhǎng)度為L(zhǎng)One的循環(huán)，將它們按t個(gè)循環(huán)一組，組成a中的一個(gè)循環(huán)，并將這個(gè)循環(huán)還原到aprocedure_Back(LOne,t:longint); i,j,k,ii,_Inc,r,w,p,tt:longint; tt := t * _Inc:=lmodtt; w := fori:=1tototLOnedivtdo fillchar(aa0,tt

8、*sizeof(aa0),0); k := 0;forj:=1totdo p := whileaak0doinc(k); r := k;forii:=1toLOnedo aar := r := r + ifr=ttthendec(r,tt); p := bp;w:=nextw; for j := 0 to tt - 2 do aaaj := aaj + aaatt-1:=aa0; i,j,m:longint; for i := 1 to n do iftoti0then m := for j := 1 to tpp_l ifimodpp_lj,1=0then m := m * pp_lj, 2;_Back