为什么要学卡特兰数？ 为了解决一类计数问题 NOIp能考吗：能 以此记录我模拟赛中被强行卡特兰数卡爆的贪心神题 什么是卡特兰数？ 卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。–百度百科 用人话来说，就是开头为1，2，5，14，42，132，429，1430，4862…的数列 卡特兰数的...

题面 传送门：洛谷 Solution 这是一道神奇的题目，我们有两种方法来处理这个问题，一种是DP，一种是组合数。 这题需要高精度，以下省略此声明 . DP 如果你对数学不感兴趣/喜欢写DP/(不想虐待自己)，这里是DP做法。 首先，我们可以发现，这个数最多有$w/k$位(向上取整),如下图所示： 那么，我们就可以以这个特性做DP啦。 设$f[i][j]$表示枚举到第i位(指2^k进制下...

题面 传送门：洛谷 Solution 这是一道很有意思的数论题。 首先，我们可以发现直接枚举a和b会T的起飞。 接下来，我们就可以观察一下式子了，我们略微手算一下，就会有这样的结果： 我们可以发现，a，b在每一项中的数量都可以用同一个斐波那契数列表示。 我们可以用$g[x]$表示斐波那契数列的第x项，那么，我们可以得到$f[x]=a_g[x-1]+b_g[x]$ 接下来，由常识可以知道，...

题面 传送门：洛谷 Solution 这题显然有一个$O(n)$的直接计算法，$60$分到手。 接下来我们就可以拿出草稿纸推一推式子了 首先，取模运算在这里很不和谐，我们得转换一下。 对于任意取模计算，我们都有： 所以，我们可以做以下推算 经过一些手算，我们发现$k/i$(向下取整)是由一段一段的区间组成的，如下图 显然，每段区间的右端点可以通过二分的方法来找 对于每一段区间，我们可...

题面 传送门:洛谷 Solution 一道很有意思的位运算题. 要做这一题,我们首先得了解一个很重要的特点 位运算过程中每一位都不会进位 有了这个特点,我们可以考虑一个很妙的做法 我们可以把每一扇门的那个数转为2进制 就可以在$O(n)$的时间内找到这一位以1或0为初始数,过完所有门后的这位数的结果 显然,结果为1是对答案有贡献的 然后,我们从后往前,一位一位枚举看一下初始值是填1还是填0...