zcmimi's blog

arrow_back递推共4篇文章

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

细节: 如果从n开始有连续一段空白,那么这段空白要去掉

转换后可以发现只需要m+1张牌就可以

考虑每次"亵渎"的贡献

第一次"亵渎"的贡献就是\displaystyle \sum_{i=1}^n i^k剪掉空位的贡献

在空位p上使用"亵渎",有贡献的位置: [p+1,n],贡献为\displaystyle \sum_{i=1}^{n-p} i^k

减去空位多算的贡献即可

求自然数幂和可以考虑拉格朗日插值,递推法,伯努利数等

avatar
zc
2020-03-19 17:10:00
查看原题

点击跳转

首先L=\left \lceil \frac LK\right \rceil,H=\left \lceil \frac HK\right \rceil

问题转化为在[L,H]中取 N\gcd=1的数 的方案数

f_i为选出 N个不完全相同\gcd=i的数 的方案数

x[L,R]i的倍数的个数,x=\sum_{j=L}^H [i|j]=\left \lfloor \frac Hi \right \rfloor-\left \lfloor \frac Li \right \rfloor

暂时令f_i=x^N-x(所有减去完全相同的)

这时候f_i实际上是选出 N个不完全相同i|\gcd的数 的方案数

假设我们已经知道了f_{2i},f_{3i},...的最终结果

那么把f_i减去f_{2i},f_{3i},...就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

原本打算写dp的,但是仔细观察一下,只要第一个点确定了,后面的点也确定了

答案只有可能是0,1,2中的一种

(可能是我扫雷玩太少了)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

第二类斯特林数

n个不同的球放进m个相同的盒子,保证盒子非空,求方案数。

容斥法:

S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i

枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式

由于盒子相同,所以除以m!

递推法:

S(n,m)=S(n-1,m-1)+mS(n-1,m)

相当于考虑现在要放的求是否单独在一个盒子里:

  1. 不占一盒:

    其余n-1个球放到m-1个盒子里

  2. 放到某个有球的盒子里:

    m个盒子可放(m种可能),其余n-1个球放到m个盒子里

此题要求的是S(n,m) \mod 2

m为偶数,S(n,m) \equiv S(n-1,m-1)

m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

(x,y)y为奇数时,可以走到(x+1,y+1)(a变换

否则可以走到(x+1,y+1)(a变换,或(x+1,y)(b变换

求从(0,0)走到(n,m)的方案数\mod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m==m时,C(n,m) \equiv 1 \bmod 2

1/1
Search
search