whix

组合数学

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 计算几何(1) 题解(9)

/ 注册

全部文章 / 组合数学（共7篇）

Buy the Ticket HDU - 1133【组合数-二维递推+大数】

思路1：详解当m<n时，明显不可能，输出0即可。当m>=n时，对于一个不满足要求的m个50，n个100的序列，其对应着一个m+1个100，n-1个50的必然不成立的序列。那么全部的可能序列的个数为：C [n+m] [m]，而不符合要求的序列的个数为C[n+m][m+1], 所有答...

2019-12-29

0 664

斯特林数

第一类斯特林数： 1.有正负 2.其绝对值是包含n个元素的集合分作k个环排列的方法数目。递推公式： S(n,0)=0; S(1,1)=1; S(n+1,k)=S(n,k-1)+n*S(n,k); 证明： #hdu4372 WA的原因，应该是从b+f-2个环中选出b-1放在后面，而不是n-...

2019-11-15

0 750

母函数

普通型母函数：解决不重复的组合问题，整数拆分问题。基本会构造多项式，然后利用一下多项式的乘法即可。多项式的系数即为方案数。 hdu1085 hdu1398[模板题] hdu1171 hdu1709 hdu1028 hdu2069 hdu2152 (1) hdu1028[模板]: #includ...

2019-11-08

0 496

卡特兰数

常见应用公式： h[n]=C(2n,n)/(n+1)(n=0,1,2,…) h[n]=C(2n,n)-C(2n,n-1)(n=0,1,2,…) 棋盘的不超越对角线问题：小兔的棋盘 HDU - 2067：数据35以内，利用公式： **h[n]=h[0]*h[n-1]+h[1] *h[n-2]+h...

2019-10-26

0 471

Paths on a Grid POJ - 1942（组合数学基础）

只能走上和右，且必有n个右，m个上，共n+m步。把路径写写出就可以发现如：样例1：上上上上右右右右右 … 只要从n+m个里面选出min(n,m)为上或右即可。利用求组合数的递推公式。 #include <cstdio> #include <cstring> #in...

2019-10-09

0 528

Round Numbers POJ - 3252组合数+分类

主要分3种情况： 1.长度比n的2进制表示的长度要小，形如：1xxxxx的格式（首位=1） 2.n能不能满足 3.长度=n的2进制表示，但从某一位开始比n小知识点：利用杨辉三角预处理组合数思想：分类考虑前缀和 #include <cstdio> #include <cs...

2019-10-05

0 424

二项式系数奇偶性判定准则

给出n,k，求C(n,k)的奇偶性：如果k&(n-k)==1,那么为偶数；否则为奇数。 Binomial Coefficients POJ - 3219 #include <cstdio> using namespace std; int main() { int ...

2019-10-04

0 547