什么是裴蜀定理 裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科 用人话来说就是： $\sum a_i*...

为什么要学卡特兰数？ 为了解决一类计数问题 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进制下...