置换 - hzwer.com

「BZOJ1478」Sgu282 Isomorphism
Description给定一个N个结点的无向完全图（任意两个结点之间有一条边），现在你可以用M种颜色对这个图的每条边进行染色，每条边必须染一种颜色。若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同，就称这两个染色方案相同。现在问你有多少种本质不同的染色方法，输出结果modP。P是一个大于N的质数。Input仅一行包含三个数，N、M、P。Output仅一行，为染色方法数modP的结果。SampleInput3497S...
32015年4月25日4,759深度搜索,置换,快速幂

「POJ2154」Color
DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceofNbeads(N<=1000000000).Yourjobistocalculatehowmanydifferentkindsofthenecklacecanbeproduced.YoushouldknowthatthenecklacemightnotuseupalltheNcolors,andtherepetitionsthatareproducedbyrotationaroundthecenterofthecircularnecklaceareallneglected.YouonlyneedtooutputtheanswermoduleagivennumberP.InputThefirstlineoftheinputisa...
02015年4月24日4,324置换,筛法,快速幂,欧拉函数
「POJ2409」Let it Bead
Description"LetitBead"companyislocatedupstairsat700CanneryRowinMonterey,CA.Asyoucandeducefromthecompanyname,theirbusinessisbeads.TheirPRdepartmentfoundoutthatcustomersareinterestedinbuyingcoloredbracelets.However,over90percentofthetargetaudienceinsiststhatthebraceletsbeunique.(Justimaginewhathappenediftwowomenshowedupatthesamepartywearingidenticalbracelets!)It'sagoodthingthatbracele...
02015年4月24日3,667置换,快速幂
「BZOJ1998」[HNOI2010] Fsk物品调度
Description现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p)modm。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi)modn，xi,yi是为了...
02015年1月31日4,605置换,并查集
NOIP2005篝火晚会
描述佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳佳可向同学们下达命令，每一个命令的形式如下：(b...
32014年10月21日5,136置换
「BZOJ1119」[POI2009] SLO
Description对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay)若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。Input第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。2<=n<=1000000100<=wi<=65001<=ai,bi<=nai各不相等，bi各不相等(ai)<>(bi)样例中依次交换数字(2,5)(3,4)(1,5)Output一个数，最小代价。...
02014年10月12日3,613置换
「BZOJ1697」[Usaco2007 Feb] Cow Sorting牛排序
Description农夫JOHN准备把他的N（1<=N<=10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。请帮JOHN计算把所有牛排好序的最短时间。Input第1行：一个数，N。...
32014年7月29日5,411置换
「BZOJ1004」[HNOI2008] Cards
Description小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可...
22014年5月26日9,311背包动规,置换,乘法逆元