首页 > 其他分享 >数数 题解

数数 题解

时间:2024-05-06 18:45:32浏览次数:33  
标签:空位 数数 题解 个数 times num binom CD

write by 小超手123

题意:

现在有四种物品,分别有 \(n_{1},n_{2},n_{3},n_{4}\) 个,有多少种排列物品的方案使得任意两个相邻物品的种类不同。

\(n_{1},n_{2} \le 200, \ \ n_{3},n_{4} \le 50000\)。

分析:

可以考虑先把物品 \(A,B\) 排列好,再把物品 \(C,D\) 插入进去。

需要注意的是 \(ABB\) 中 \(BB\) 中间必须填入 \(C,D\)

记 \(f_{i,j,k,0/1}\) 表示用了 \(i\) 个物品 \(A\),\(j\) 个物品 \(B\),其中相邻的且相等有 \(k\) 对,当前最后一个选的物品 \(A/B\)。


step 1 : 分配哪些空位要填入 \(C,D\)

因此有 \(n_{1}+n_{2}+1\) 个空位,总共需用 \(C,D\) 填入 \(j\) 个空位,有 \(i\) 个空位已经强制要求必须填。\(i,j\) 均需要枚举。

那么方案数为:

\[(f_{n_{1},n_{2},i,1}+ f_{n_{1},n_{2},i,1}) \times \binom{n_{1}+n_{2}+1-i}{j-i} \]

step 2 : 把 \(C,D\) 填入空位

可以发现中间空位填的 \(C,D\) 只有三种情况:

  • 类型一:形如 \(CDCDC\)。相当于先放一个 \(C\) 进去,然后放若干个 \([DC]\)。即 \(C\) 的个数比 \(D\) 的个数多 \(1\)。记这样的有 \(X\) 种。
  • 类型二:形如 \(DCDCD\)。相当于先放一个 \(D\) 进去,然后放若干个 \([CD]\)。即 \(D\) 的个数比 \(C\) 的个数多 \(1\)。记这样的有 \(Y\) 种。
  • 类型三:形如 \(DCDC\) 或 \(CDCD\)。相当于直接放若干个 \([CD]\) 或 \([DC]\)。即 \(D\) 的个数与 \(C\) 的个数相等。记这样的有 \(Z\) 种。

不难发现 \(n_{1}-n_{2}=X-Y,Z=j-X-Y\)。因此只需要再枚举 \(X\) 即可。

所以可以给每个要填空位分配一种类型:\(\binom{j}{X} \times \binom{j-X}{Y}\)。

即上文所述 \([CD],[DC]\) 的总个数为 \(num\)。显然 \(num = \frac{n_{3}+n_{4}-X-Y}{2}\)。

将这 \(num\) 个\([CD],[DC]\) 放进 \(j\) 个空位里。需要注意的是对于类型三的空位,至少要放一个 \([CD]\) 或 \([DC]\)

把 \(num\) 减掉 \(Z\),然后插板即可。因此有 \(\binom{num-Z+j-1}{j-1}\) 种情况。

由于类型三有两种小情况,因此还要乘上 \(2^{Z}\)。


乘法原理,需要枚举 \(i,j,X\)。

最后答案就是:

\[(f_{n_{1},n_{2},i,1}+ f_{n_{1},n_{2},i,1}) \times \binom{n_{1}+n_{2}+1-i}{j-i} \times \binom{j}{X} \times \binom{j-X}{Y} \times \binom{num-Z+j-1}{j-1} \times 2^{Z} \]

时间复杂度 \(O((n_{1}+n_{2})^3)\)。

标签:空位,数数,题解,个数,times,num,binom,CD
From: https://www.cnblogs.com/cqyc-sol/p/18175639

相关文章

  • P10385 艺术与篮球 题解
    一道用编程解决的数学题。大概思路是:intmonth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};这是普通年\(12\)个月的天数。然后还要考虑闰年,有\(2000,2004,2008,2012,2016,2020,2024\)。将这些闰年的二月二十九号手算出来能不能打篮球,最后加在结果上就行了。然后循环......
  • MySQL Connection not available问题解决方案
    在后端开发过程中,连接mysql数据库,过几个小时第一次使用会出现MySQLConnectionnotavailable报错这是因为MySql数据库存在一个连接池的回收时间,超过这个时间会导致资源无法正常释放,无法连接到MySql数据库1)在相关引用页面,进行定时刷新功能,这样尽管是同一个连接,但是相当于一个新......
  • 高一下三调|ssy的队列|hash dp|题解
    SSY的队列题目链接解析:考场上看到这个题第一眼是绝望的,毕竟数论咱是一窍不通.但是往下细看了看这个数据范围,N是很小的,就想了想模拟.然而只骗到10分.这个题绩效较高的解法是状压dp,在N<15的范围之内均可薄纱(ppllxx_9G也是成功拿到这70rank1了orz),可得70,但是一到后......
  • AtCoder Beginner Contest 352题解
    AtCoderBeginnerContest352Time:2024-05-04(Sat)20:00-2024-05-04(Sat)21:40AAtCoderLine问题陈述AtCoder铁路线有$N$个车站,编号为$1,2,\ldots,N$。在这条线路上,有趟进站列车从$1$站出发,依次停靠$2,3,\ldots,N$站,有趟出站列车从$N$站出发,依次停......
  • P3193 [HNOI2008] GT考试 题解
    之前学矩阵乘的时候做的题,当时因为不会\(kmp\)搜索一稀里糊涂过去了,现在填个坑。头图是\(Logos\)!P3193[HNOI2008]GT考试题链:洛谷题库题目大意:求有多少个长度为\(n\)的数字串的子串中不包含给出的长度为\(m\)位的串,范围\(n<=1e9\),$m<=20$。思路:首先考虑DP,令\(......
  • CF1630A And Matching 题解
    题目描述有\(n\)个数\(0,1,2,\cdots,n-1\)。你需要把他们两两分组,使得每组两个数按位与的结果之和\(=k\)。如果可能,请构造出一组可能的\(\fracn2\)个数对,否则输出-1。保证\(n\)是\(2\)的幂,\(k\len-1\)思路首先我们发现,\(n\)是二的幂,所以按照二进制的角度看,这......
  • [SDOI2015] 星际战争 题解
    假如将所有激光武器放在一边,所有机器人放在一边,激光武器向它可以伤害的机器人连边,再加超级源/汇点,这就是一个网络流问题。考虑激光武器向机器人连的边容量无限,而机器人向超级汇点连的边容量为机器人的装甲值,而超级源点连向激光武器的边则是用时\(\times\)激光武器伤害。发现假......
  • CF729B Spotlights 题解
    题目简述给出一个$n$行$m$列的$01$矩阵,定义每个点的价值为上下左右四个方向有$1$的方向数,求所有为$0$的点的价值和。题目分析我们首先可以考虑暴力,但是发现是不行的。于是我们考虑动态规划。设$dp_{i,j,0/1/2/3}$分别表示$(i,j)$这个点上方,左方,下方,右方是否有$......
  • [SCOI2007] 蜥蜴 题解
    发现实际上就是在求有多少只蜥蜴能逃出来。发现可以将柱子拆成入点和出点两部分,自己的出点向别人的入点连边,自己的入点向自己的出点连边。最后再加一个超级源点\(S\),连接所有有蜥蜴的柱子入点;再加一个超级汇点\(T\),连接所有能够跳出地图的柱子。我们猛然发现:这个问题不就是求......
  • 题解:AT_abc352_C [ABC352C] Standing On The Shoulders
    考场憋了很久,最后代码贼短……理想状态下,直接全排列解决问题。但是,\(1\len\le2\times10^5\),明显TLE,试都不用试的。咋优化呢?其实,前面的巨人只负责“打地基”,作为“塔尖儿”的巨人有且仅有1个。而前面地基随便排列,地基高度(他们的和)都不会变。所以,我们只需要枚举塔尖即......