bzoj 1600 排列组合

Advertisement

题意:长度为n的木板分成4份组成一个合法的四边形(面积不为0),求不同的方案数(切割点不同就是不同的方案)

这难道不是隔板法的经典模型么 2333, ans=c(n-1,3)

但是,这时并不能保证我们分成的四份能组成合法的四边形

能拼成面积为正四边形 即 三条短边长的和大于第四边
每一边的长度都小于n/2

所以要在ans中减去最长边大于等于n/2的所有方案数,等价于 减去长度为(n-m)的木板分成3份的方案数 * 4(最长木板的切割位置有4种情况)即

注意:虽然最终答案在int范围内但中间求组合数的过程会爆int,所以还是要开long long

var
        c               :array[0..2500,0..5] of int64;
        ans             :int64;
        i               :longint;
        n,m             :longint;
procedure pre_do;
var
        i,j:longint;
begin
   for i:=1 to 2500 do c[i,0]:=1;
   c[1,1]:=1;
   for i:=2 to 2500 do
     for j:=1 to 4 do c[i,j]:=c[i-1,j]+c[i-1,j-1];
end;

begin
   pre_do;
   read(n);
   ans:=c[n-1,3];
   m:=(n+1) div 2;
   for i:=m to n-1 do dec(ans,int64(4)*c[n-i-1,2]);
   writeln(ans);
end.

——by Eirlys
bzoj 1600 排列组合

Similar Posts:

  • BZOJ 2729: [HNOI2012]排队|排列组合

    这显然是一道排列组合的纯数学题(偏题) 考虑将男生和老师先排出来,然后再插入女生 因为两个老师不能靠在一起,可以先计算排完男生和老师后两个老师在一起的方案数为,把两个老师绑在一起看成一个男生A(n+1,n+1)∗A(2,2) 这样两个老师之间必须插入一个女生,然后剩下的m−1个女生就任意插入男生之间,这样总的方案数为 m∗A(n+1,n+1)∗A(2,2)∗C(n+2,m−1)∗A(m−1,m−1) 然后两个老师和男生排完队不相邻时的方案数为A(n+2,n+2)−A(n+1,n+1)∗A(2,2

  • 动态规划与排列组合

    动态规划与排列组合 By 刘未鹏(pongba) C++的罗浮宫(http://blog.csdn.net/pongba) TopLanguage(http://groups.google.com/group/pongba) 像所有的新手一样,对一种算法思想的理解需要经历从肤浅(流于表面形式)到逐渐触摸到本质的过程.为什么说"逐渐"触摸到本质,是因为很多时候你并不确定一个解释是不是最本质的,有时候会有好几个等价的解释,各自在不同的场景下具有启发. 比如对动态规划(DP)的理解,一开始我

  • PHP的排列组合问题 分别从每一个集合中取出一个元素进行组合,问有多少种组合?

    首先说明这是一个数学的排列组合问题 C(m,n) = m!/(n!*(m-n)!) 比如:有集合('粉色','红色','蓝色','黑色'),('38码','39码','40码'),('大号','中号') 分别从每一个集合中取出一个元素进行组合,问有多少种组合? 解:C(4,1) * C(3,1) * C(2,1) = (4!/(1!*(4-1)!)) * (3!/(1!*(3-1)!)) * (2!/(1!*(2-1)!)) = 24/6 * 6/2 * 2 = 4 * 3 * 2 = 24(种

  • HDU 4497 GCD and LCM(分解质因子+排列组合)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4497 题意:已知GCD(x, y, z) = G,LCM(x, y, z) = L.告诉你G.L,求满足要求的(x, y, z)有多少组,并且要考虑顺序. 思路:如果L%G != 0显然不存在这样的(x, y, z),相反肯定存在.具体做法就是将L/G分解质因子,得到:L/G = P1^t1 * P2^t2 * ... * Pk^tk,我们来考虑任意一个因子Pi^ti,此时(x/G, y/G, z/

  • HDU-计算机学院大学生程序设计竞赛(2015’11)1005 ACM组队安排(排列组合)

    1001-搬砖(贪心):http://blog.csdn.net/idealism_xxm/article/details/50097051 1002-投币洗衣机(模拟):http://blog.csdn.net/idealism_xxm/article/details/50097231 1003-玩骰子(枚举) :http://blog.csdn.net/idealism_xxm/article/details/50097691 1004-质方数(打表):http://blog.csdn.ne

  • HDU 1521 排列组合(指数型母函数)

    HDU 1521 排列组合(指数型母函数):http://acm.hdu.edu.cn/showproblem.php?pid=1521 题面描述: Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3369 Accepted Submission(s): 1409 Problem Description 有n种物品,并且知道每种物品的数量.要

  • (转自网络)数据结构:排列组合通用算法分析

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • 排列组合知识

    百科名片 排列组合是组合学最基本的概念.所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序.组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序.排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数. 排列组合与古典概率论关系密切. 目录 定义及相关 例题分析 音乐专辑 展开 定义及相关 例题分析 音乐专辑 展开 编辑本段定义及相关 定义及公式 排列数公式 排列的定义及其计算公式:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列

  • hdu 2451Simple Addition Expression(排列组合)

    http://acm.hdu.edu.cn/showproblem.php?pid=2451 题目大意:有一个关于 简单加法表达式 的定义告诉你,就是 选一个数字i 如果 i+ (i+1) +(i+2) 它的和,没有任何一位进位的话,那就是 一个ie简单加法表达式. 例如:11+12+13就是,而 13+14+15就不是,因为它个位进位了. 现在给你一个n,叫你求出小于n的值中有多少个i可以构成简单加法表达式. 解题思路:要想个位不进位,明显的个位数字只能取 0-2,其他高位不进位,必然只能取0

  • 针对如&quot;123456&quot;之类的任意字符序列,输出它们所有的排列组合 .

    思想:针对排列问题,应该将每个位置上可能出现的情况列出来,如有四个不同字符(暂时不考虑有相同情况),那么第一个位置就有四种可能的情况,当第一个位置确定后,第二个位置就只有三种情况,依次类推,最后一个位置只有一种情况,这个对于学过排列组合的人来说,很好理解,关键在于怎样用程序实现呢? 根据上面的分析我们只要挨个把每个位置上出现的字符确定下来,那么这个序列就确定下来了,现在关键是我们针对某个位置出现的情况应该怎样确定呢?比如第一个位置有4种情况,而且每个位置上的字符不相同,那么就可以用整体左移或者右