GoldenPotato137的小屋

GoldenPotato137的小屋
一名HITer/LLer/ACMer的个人博客
数学

[CF932E] Team Work

题面 洛咕 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…

2019年2月25日 0条评论 861点热度 0人点赞 GoldenPotato137 阅读全文
学习笔记

第二类斯特林数学习笔记

本菜鸡尚未学会第二类斯特林数,请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学,Stirling数可指两类数,第一类Stirling数和第二类Stirling数,都是由18世纪数学家James Stirling提出的。 Stirling数有两种,第一类和第二类Stirling数,它们自18世纪以来一直吸引许多数学家的兴趣,如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根(Copenhagen)大学的尼尔森(Niels Nielsen,1865-1931)提出了"Stirlingschen Z…

2019年2月25日 0条评论 697点热度 0人点赞 GoldenPotato137 阅读全文
同余

[Luogu P4777] 【模板】扩展中国剩余定理(EXCRT)

题面 传送门:洛咕 Solution 真*扩展中国剩余定理模板题。我怎么老是在做模板题啊 但是这题与之前不同的是不得不写龟速乘了。 还有两个重点 我们在求LCM的时候,记得先/gcd再去乘另外那个数,直接乘会乘爆的 我们在做龟速乘之前,要保证要乘的两个数>=0,如果<0的话,龟速乘会爆掉的,我们传进去之间记得膜一下 int128:你说啥?这里风太大,我听不见。 Code //Luogu P4777 【模板】扩展中国剩余定理(EXCRT) //Jan,15th,2019 //中国剩余定理 #include<…

2019年2月25日 0条评论 686点热度 0人点赞 GoldenPotato137 阅读全文
同余

[POJ 2891] Strange Way to Express Integers

题面 传送门: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…

2019年2月25日 0条评论 530点热度 0人点赞 GoldenPotato137 阅读全文
同余

扩展中国剩余定理学习笔记

为什么要扩展中国剩余定理? 建议学习前置芝士:中国剩余定理(不学也不要紧,因为并没有啥关系) 我们知道,中国剩余定理是用来解线性同余方程组的算法,类似下面这个: $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两两互…

2019年2月25日 0条评论 810点热度 0人点赞 GoldenPotato137 阅读全文
数学

扩展欧几里得算法+推论

什么是扩展欧几里得? 扩展欧几里得算法是建立在欧几里得算法(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*…

2019年2月25日 0条评论 653点热度 0人点赞 GoldenPotato137 阅读全文
容斥

SPOJ16607 IE1 - Sweets

题面 传送门: 洛咕 SPOJ Solution 这题的想法挺妙的。 . 首先,对于这种区间求答案的问题,我们一般都可以通过类似前缀和的思想一减来消去a,即求[a,b]的答案可以转化为求[1,b]-[1,a-1] 接下来我们可以先考虑一下每个物品数量不限制的做法。我们可以把这个问题类比为放球问题:我们要在n个相同的盒子里放x个球,这个问题可以用隔板法解决,显然答案为$C_{x+n-1}^{n-1}$ 因为我们的n特别小,而且p为合数,所以可以用分解质因数的方法来算这个组合数。 . 接下来,我们可以考虑一下如何处理多…

2019年2月25日 0条评论 451点热度 0人点赞 GoldenPotato137 阅读全文
动态规划

[Luogu P4124] [CQOI2016]手机号码

题面 传送门:洛咕 Solution 感谢神仙@lizbaka的教学 这题是数位DP的非常非常模板的题目,只是状态有点多 . 这题我使用记忆化搜索实现的 中国有句古话说的好,有多少个要求就设多少个状态。 所以说,考虑这样设置状态: 设$f[i][j][k][2][2][2][2][2]$表示当前填到第i位,上一位填了j,上两位填了k,是否卡上界,上一个数是否为前导零,是否有4,是否有8,是否出现了连续三个相同的数字,之后任意填的可行方案总数 使用记忆化搜索的话,转移是非常容易的,我们只需要像写搜索一样递归写下去就好…

2019年2月25日 0条评论 810点热度 0人点赞 GoldenPotato137 阅读全文
LUCAS

[UOJ 275/BZOJ4737] 【清华集训2016】组合数问题

题面 传送门: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进制拆分后的两个数的每一位数,若一个数的位数…

2019年2月25日 0条评论 737点热度 0人点赞 GoldenPotato137 阅读全文
其他

一些很妙的网站

米奇妙♂妙♂屋 1.妙不可言的一键作图网站 https://csacademy.com/app/graph_editor/ (抄自神仙lbc的博客) 2.妙妙识图网站 http://www.iqdb.org/ 3.妙妙图床 https://imgchr.com/ 4.妙妙sitemap自动生成网站 https://www.xml-sitemaps.com/ 5.不可描述 https://blog.sprov.xyz/2019/08/03/v2-ui/

2019年2月25日 0条评论 826点热度 0人点赞 GoldenPotato137 阅读全文
12345…6

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 2 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 2 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号