Day 3 下午

依旧是组合数问题

• 先来看一道题

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

如图，一个n*m的方格中，从原点开始，每次只能向上走或者向右走，求走到点(n,m)共有多少种走法

一般做法：

一个一个写，每一个节点的种数=它左边的数量+右边的数量

显然可以DP做

但我们不用DP做(滑稽

组合数：  ans=C(n+m,n)

原因：一共要走n+m步，从中选出n步向右走的，即为答案（C(n+m,m)也是一样滴）

• 经典题：问从(0,0)走到(n,m)且不穿过直线y=x的方案数，如图

 

总的方案减去不合法的方案 对称过去 一定经过(1,0)  

 

 

洛谷P4369

好吧其实这个题简单的一批.....

话说每一个1都可以写成C(n,0)d的形式.....

这下知道怎么做了吧

•1+1+1+1+...+1+(x-k+1) •C(1  ,0)+c(2,0)+...       直接比较组合数是n！的复杂度，显然会tle，而且也不好算，我们可以转而比较log的大小 、

 

•求n!前缀和 •比较log  

•两边展开，系数杨辉三角  

一个神奇的结论：

结合转移矩阵

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄