排列组合 - Page 2

「CODEVS1515」跳
题目描述Description邪教喜欢在各种各样空间内跳。现在，邪教来到了一个二维平面。在这个平面内，如果邪教当前跳到了(x,y)，那么他下一步可以选择跳到以下4个点：(x-1,y),(x+1,y),(x,y-1),(x,y+1)。而每当邪教到达一个点，他需要耗费一些体力，假设到达(x,y)需要耗费的体力用C(x,y)表示。对于C(x,y)，有以下几个性质：1、若x=0或者y=0，则C(x,y)=1。2、若x>0且y>0，则C(x,y)=C(x,y-1)+C(x-1,y)。3、若x<0且y<0，...
72015年1月9日3,840贪心,快速幂,排列组合,乘法逆元

「CF500D」New Year Santa Network
NewYeariscominginTreeWorld!Inthisworld,asthenameimplies,therearencitiesconnectedbyn - 1roads,andforanytwodistinctcitiestherealwaysexistsapathbetweenthem.Thecitiesarenumberedbyintegersfrom1ton,andtheroadsarenumberedbyintegersfrom1ton - 1.Let'sdefined(u, v)astotallengthofroadsonthepathbetweencityuandcityv.Asanannualevent,peopleinTreeWorldrepairsexactlyoneroadperyear.Asaresult,theleng...
02015年1月4日3,592树形动规,排列组合
「BZOJ2281」[SDOI2011] 黑白棋
Description黑白棋（game）「问题描述」小A和小B又想到了一个新的游戏。这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小A和小B轮流操作，现...
22014年12月22日6,599递推与动规,博弈论,排列组合
「BZOJ3398」[Usaco2009 Feb] Bullcow 牡牛和牝牛
Description 约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛．牛们要站成一排．但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛．请计算一共有多少种排队的方法．所有牡牛可以看成是相同的，所有牝牛也一样．Input 一行，输入两个整数N和K.Output 一个整数，表示排队的方法数．SampleInput42Sampl...
02014年10月1日5,301排列组合,乘法逆元
「BZOJ1951」[SDOI2010] 古代猪文
Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王国。猪王国虽然不大，但是土地肥沃，屋舍俨然...
22014年9月14日8,208快速幂,排列组合,模线性方程组,扩展欧几里得算法
「BZOJ2982」combination
DescriptionLMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod10007的值。(1<=m<=n<=200,000,000)Input 第一行一个整数t，表示有t组数据。(t<=200) 接下来t行每行两个整数n,m，如题意。OutputT行，每行一个数，为C(n,m)mod10007的答案。SampleInput451527342SampleOutpu...
02014年8月25日3,650排列组合
「CF451E」Devu and Flowers
Devuwantstodecoratehisgardenwithflowers.Hehaspurchased n boxes,wherethe i-thboxcontains fi flowers.Allflowersinasingleboxareofthesamecolor(hencetheyareindistinguishable).Also,notwoboxeshaveflowersofthesamecolor.NowDevuwantstoselect exactly s flowersfromtheboxestodecoratehisgarden.Devuwouldliketoknow,inhowmanydifferentwayscanheselecttheflowersfromeachbox?Sincethisnumbermaybeverylarg...
12014年7月25日5,948排列组合,乘法逆元,容斥原理
「BZOJ1005」[HNOI2008] 明明的烦恼
Description自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1Output一个整数,表示不同的满足要求的树的个数,无解输出0SampleInput31-1-1SampleOutput2HINT 两棵树分别为1-2-3;1-3-2 题解该题运用到了...
62014年5月30日10,695高精度,prufer编码,排列组合
「BZOJ1211」[HNOI2004] 树的计数
Description一个有n个结点的树，设它的结点分别为v1,v2,…,vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1,d2,…,dn，编程需要输出满足d(vi)=di的树的个数。Input第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。Output输出满足条件的树有多少棵。SampleInput42121SampleOutpu...
02014年5月30日5,045prufer编码,排列组合
「BZOJ3505」[CQOI2014] 数三角形
Description给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。Input输入一行，包含两个空格分隔的正整数m和n。Output输出一个正整数，为所求三角形数量。SampleInput22SampleOutput76数据范围1<=m,n<=1000题解首先在n*m个点选择任意3个然后减去三点共线的三点共线分三种情况，同一行，同一列，斜的用gcd算[crayon-6628fe50749ce659903573/]&nb...
02014年5月15日6,410排列组合
NOIP2011多项式系数
题目描述求(ax+by)^k的展开中x^n*y^m项的系数。由于系数可能很大，只要求输出除以10007的余数。输入一行共五个整数，分别为a,b,k,n,m输出一个整数，为该项系数除以10007的余数。样例输入11312样例输出3提示数据范围：30%0<=k<=10,50%a=1,b=1100%0<=k<=1000,0<=n,m<=k且n+m=k,0<=a,b<=100,000NOIP2011DAY2factor代码2013.11.6[crayon-6628fe5074dac739527437/]2014.4.24乘法逆元可以用于求C[crayon...
12014年4月24日5,887排列组合,乘法逆元
「BZOJ1227」[SDOI2009] 虔诚的墓主人
题目描述 Description小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k棵常青树。...
42014年3月11日6,858树状数组,排列组合