集训队作业-shufflemachine解题报告

江苏省常州高级中学/r/n/r/n[/r/n问/r/n题/r/n描/r/n述/r/n剀剀和/r/n有/r/nN/r/n张牌（依次标号为/r/n1/r/n，/r/n2/r/n，/r/n……/r/n，/r/nN/r/n）和一台/r/n。假设/r/nN/r/n是奇数/r/n。/r/nI/r/n（/r/n1/r/n≤/r/nI/r/n≤/r/nN/r/n/r/n位置/r/nJ/r/n上的牌是/r/nK/r/n，那么通过/r/n后位置/r/nI/r/n上的牌将是/r/nK/r/n1/r/n，/r/n2/r/n，/r/n……/r/n，/r/nN/r/n的一个随机排列：/r/na/r/n1/r/na/r/n2/r/na/r/nN/r/n。然后他这样来排列牌/r/na/r/ni/r/na/r/ni+1/r/n（/r/n1/r/n≤/r/ni/r/n≤/r/nN-/r/n1/r/n，而/r/na/r/nN/r/n/r/na/r/n1/r/n。这样排列后，牌的顺序就/r/n为/r/nx/r/n1/r/n,/r/nx/r/n2/r/n,...,x/r/nN/r/n然后/r/n他把/r/n这种顺序排列的牌放入/r/n洗/r/n牌/r/nS/r/n次/r/n得到牌的顺序为/r/np/r/n1/r/n,p/r/n2/r/n,...,p/r/nN/r/n现在/r/n剀/r/n剀把牌的最后顺序和洗牌次数告诉/r/n要/r/n猜出牌的最初顺序/r/nx/r/n1/r/n,/r/nx/r/n2/r/n,/r/n...,/r/nx/r/nN/r/nN/r/nS/r/n。/r/n1/r/n≤/r/nN/r/n≤/r/n1000/r/n，/r/n1/r/n≤/r/nS/r/n≤/r/n1000/r/n。第二行为牌的最终顺序/r/np/r/n1/r/n,p/r/n2/r/n,...,p/r/nN/r/n。/r/nx/r/n1/r/nx/r/n2/r/nx/r/nN/r/n。/r/n /r/n /r/n 2541/r/n4153/r/n[/r/n题/r/n目/r/n来/r/n源/r/nCEOI/r/n1998Day/r/nProblem/r/nShuffle/r/n[/r/n算/r/n法/r/n分/r/n析/r/n/r/n/r/nn/r/n1,2,…,n/r/n之间的一个置换为/r/n

/r/n2/r/n/r/n.../r/n/r/nn/r/n/r/n/r/n1/r/n1/r/nn/r/na/r/n1/r/na/r/n1/r/n/r/na/r/n2/r/n/r/n.../r/na/r/nn/r/n/r/n2/r/n1/r/nn/r/na/r/n2/r/n取代，……，/r/nn/r/n1/r/nn/r/na/r/nn/r/na/r/n1/r/n,a/r/n2/r/n,…,a/r/nn/r/n互不相/r/n置/r/n换/r/n的/r/n乘/r/n法/r/n运/r/n算/r/n /r/n4/r/n/r/n/r/n2/r/n/r/n /r/n/r/n123/r/n

/r/n /r/n/r/n/r/n /r/n /r/n3/r/n/r/n /r/n312/r/n循/r/n环/r/n

/r/n /r/n /r/n /r/n/r/na/r/n1/r/n/r/na/r/n2/r/n.../r/na/r/nn/r/n/r/n1/r/n/r/na/r/nn/r/n/r/n记/r/n(/r/na/r/n1/r/na/r/n2/r/n.../r/na/r/nn/r/n/r/n)/r/n/r/n/r/n

/r/na/r/n/r/n.../r/n/r/n

/r/n/r/nn/r/na/r/n/r/n/r/n2/r/n/r/n /r/n /r/n1/r/n/r/n1/r/n/r/n246/r/n回/r/n到/r/n刚/r/n才/r/n的/r/n问/r/n题/r/n，/r/n题/r/n目/r/n中/r/n说/r/n洗/r/n牌/r/n的/r/n过/r/n程/r/n是/r/n：/r/n对/r/n所/r/n有/r/n位/r/n置/r/n/r/nI/r/n（/r/n1/r/n≤/r/nI/r/n≤/r/nN/r/n，/r/n如/r/n果/r/n位/r/n置/r/n/r/nI/r/n/r/n上的/r/n牌/r/n是/r/n/r/nJ/r/n，/r/n而/r/n且/r/n位/r/n置/r/n/r/nJ/r/n/r/n上/r/n的/r/n牌/r/n是/r/n/r/nK/r/n，/r/n那/r/n么/r/n通/r/n过/r/n后/r/n位/r/n置/r/n/r/nI/r/n/r/n上/r/n的/r/n牌/r/n将/r/n是/r/n/r/nK/r/n。/r/n如/r/n果/r/n把/r/n洗/r/n牌/r/n前/r/n的/r/n2/r/n3/r/n/r/n/r/n531/r/n24/r/n

/r/n/r/n/r/n/r/n

/r/n345/r/n/r/n/r/n /r/n413/r/n/r/n/r/n2/r/nS/r/n2/r/n经过/r/nS/r/n次自乘后等于/r/nP/r/n。更抽象一点就是：解方程/r/n /r/n/r/n/r/nP/r/n写/r/n下/r/n数/r/n1/r/n，/r/n2/r/n，/r/n……/r/n，/r/nN/r/n的/r/n一/r/n个/r/n随/r/n机/r/n排/r/n列/r/n：/r/na/r/n1/r/na/r/n2/r/n,...,/r/na/r/nN/r/n。/r/n然/r/n后/r/n他/r/n这/r/n样/r/n来/r/n排/r/n列/r/n牌/r/n的/r/n顺/r/n序/r/n：/r/n位/r/n1/r/n，/r/nx/r/nN/r/n这/r/n句/r/n话/r/n告/r/n诉/r/nX/r/n/r/n不/r/n是/r/n一/r/n般/r/n的/r/n置/r/n换/r/n而/r/n是/r/n一/r/n个/r/nn/r/n/r/n阶/r/n循/r/n环/r/n由/r/n循/r/n环/r/n的/r/n性/r/n质/r/n有/r/nX/r/np/r/n=X/r/nq/r/n(p≡q(mod/r/n/r/n分析到这里，前面的那个方程就很好解了。具体步骤：/r/n1/r/n2/r/nS/r/n*m≡1(mod/r/n/r/nn)/r/n 2/r/n/r/n 2/r/n/r/n /r/n /r/n/r/n/r/nP/r/n，所以/r/nX/r/n/r/n/r/n/r/n /r/n/r/n/r/nP/r/n/r/n。/r/nP/r/n/r/n是已知的/r/nm/r/nX/r/nO(n/r/n2/r/n)/r/n，/r/nO(n)/r/n。/r/n[/r/n源/r/n程/r/n序/r/nprogram/r/na,b:array/r/n[1..maxn]/r/nof/r/nlongint;/r/nprocedure/r/ninput_data;/r/n/r/nfor/r/ni:=1/r/nto/r/nn/r/ndo/r/nread(a[i]);/r/nprocedure/r/nsolve;/r/nfor/r/ni:=1/r/nto/r/ns/r/ndo/r/npow:=pow*2/r/nmod/r/nn;forp:=0ton-1do/r/nif/r/