题面 洛咕 CodeForces Solution 这题写得我脑壳疼，我好菜啊 . 显然，这题让我们求$\sum_{i=1}^{n}C_n^i\times i^k$ 这个$i^k$让人浑身难受，我们可以考虑把它搞掉，能搞掉某个数的幂次方的有啥？本蒟蒻只会第二类斯特林数。 . 所以说我们无脑把第二类斯特林数带进去再说： $\sum_{i=1}^{n}C_n^i\times \sum_{j=0}^{i}S(k,j)*j!*C_i^j$ . 然后把组合数展开： $\sum_{i=1}^{n}\frac{n…
本菜鸡尚未学会第二类斯特林数，请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。 Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根（Copenhagen）大学的尼尔森（Niels Nielsen，1865-1931）提出了"Stirlingschen Z…
题面 传送门：洛咕 Solution 真*扩展中国剩余定理模板题。我怎么老是在做模板题啊 但是这题与之前不同的是不得不写龟速乘了。 还有两个重点 我们在求LCM的时候，记得先/gcd再去乘另外那个数，直接乘会乘爆的 我们在做龟速乘之前，要保证要乘的两个数>=0,如果<0的话，龟速乘会爆掉的，我们传进去之间记得膜一下 int128:你说啥？这里风太大，我听不见。 Code //Luogu P4777 【模板】扩展中国剩余定理（EXCRT） //Jan,15th,2019 //中国剩余定理 #include<…
题面 传送门：POJ Solution 就是裸的扩展中国剩余定理嘛qwq 注意几点：一定要时时刻刻去膜取模，否则一定会爆long long，尤其是算出来的$k_0$ 这里给出几组易锅数据：(第三组容易爆long long) input: 4 18373 16147 8614 14948 8440 17480 22751 21618 6 19576 8109 18992 24177 9667 17726 16743 19533 16358 12524 8280 22731 4 9397 38490 22001 250…
为什么要扩展中国剩余定理？ 建议学习前置芝士：中国剩余定理（不学也不要紧，因为并没有啥关系） 我们知道，中国剩余定理是用来解线性同余方程组的算法，类似下面这个： $x \equiv a_0 (p_0)$ $x \equiv a_1 (p_1)$ $x \equiv a_2 (p_2)$ 很不幸，这里要求$p_0,p_1,p_2$两两互质 . 如果不互质怎么办？当然是把出题者拖出去吊起来打啊。这时候就得有请我们的扩展中国剩余定理了。 什么是扩展中国剩余定理？ 如上说述，就是用来求线性同余方程组的定理，但不要求p两两互…
什么是扩展欧几里得？ 扩展欧几里得算法是建立在欧几里得算法(gcd)之上。 首先，我们知道有$ax+by=gcd(a,b)$ 我们怎么求这个$x,y$呢？ 这时候我们就得使用exgcd算法，我们来推导一下吧！ $a*x+b*y=gcd(a,b)$ $a*x+b*y=gcd(b,a\% b)$ $a*x+b*y=b*x'+(a- \left \lfloor \frac{a}{b} \right \rfloor*b)*y'$ $a*x+b*…
题面 传送门： 洛咕 SPOJ Solution 这题的想法挺妙的。 . 首先，对于这种区间求答案的问题，我们一般都可以通过类似前缀和的思想一减来消去a，即求[a,b]的答案可以转化为求[1,b]-[1,a-1] 接下来我们可以先考虑一下每个物品数量不限制的做法。我们可以把这个问题类比为放球问题：我们要在n个相同的盒子里放x个球，这个问题可以用隔板法解决，显然答案为$C_{x+n-1}^{n-1}$ 因为我们的n特别小，而且p为合数，所以可以用分解质因数的方法来算这个组合数。 . 接下来，我们可以考虑一下如何处理多…
题面 传送门：洛咕 Solution 感谢神仙@lizbaka的教学 这题是数位DP的非常非常模板的题目，只是状态有点多 . 这题我使用记忆化搜索实现的 中国有句古话说的好，有多少个要求就设多少个状态。 所以说，考虑这样设置状态: 设$f[i][j][k][2][2][2][2][2]$表示当前填到第i位，上一位填了j，上两位填了k，是否卡上界，上一个数是否为前导零，是否有4，是否有8，是否出现了连续三个相同的数字，之后任意填的可行方案总数 使用记忆化搜索的话，转移是非常容易的，我们只需要像写搜索一样递归写下去就好…
题面 传送门：UOJ Solution 这题的数位DP好蛋疼啊qwq 好吧，我们说回正题。 首先，我们先回忆一下LUCAS定理： $C_n^m \equiv C_{n/p}^{m/p} \times C_{n\%p}^{m\%p} (\%p)$ 我们仔细观察这个定理，就可以发现一个事实：LUCAS定理本质上是在对n，m两个数做K进制下的数位分离 所以说，LUCAS定理我们可以这样表示： $C_n^m \equiv \prod C_{a_i}^{b_i}$ （ai与bi为K进制拆分后的两个数的每一位数，若一个数的位数…
最近评论
hilaolu 发布于 1 年前（03月16日）
Guava 发布于 2 年前（11月30日）
碱式碳酸希 发布于 2 年前（11月30日）
碱式碳酸希 发布于 2 年前（11月04日）
630分苦苦挣扎的菜鸡土豆 发布于 2 年前（05月01日）