小蒟蒻yyb的博客

摘要： 组合计数和反演 包含内容 二项式反演、斯特林反演、莫比乌斯反演、第一类斯特林数、第二类斯特林数。 反演 首先我们有两个数列$\{f_i\}$和数列$\{g_i\}$，他们之间满足 $$g_n=\sum_{i=0}^n a[n][i]f_i$$ 这里我们可以通过$\{f_i\}$的值推出$\{g_i\ 阅读全文

摘要： 有标号的DAG计数系列 有标号的DAG计数I 题意 给定一正整数$n$，对$n$个点有标号的有向无环图(可以不连通)进行计数，输出答案$mod \ 10007$的结果。$n\le 5000$ 题解 显然是$O(n^2)$来做。 设$f(i)$表示$i$个点有标号的有向无环图的个数。而$DAG$中的特 阅读全文

摘要： [复习]多项式和生成函数相关内容 多项式 涉及的方面 主要在于多项式的乘法，也就是$FFT,NTT,MTT$。 但是也多项式的求逆，$exp$，$ln$，开根，求导，积分等操作。 多项式乘法 并没有什么好复习的，记好板子就行了。同样也是多项式运算的基础。 泰勒展开&麦克劳林级数 泰勒展开： 如果$f 阅读全文

摘要： 题面 "洛谷" 题解 模板题。。。 我直接蒯我写的东西。。。 这个除法是带余除法，所以并不能直接求逆解决。 要求的就是给定两个多项式$A(x),B(x)$，其项数为$n,m$ 求解一个$n m$项的多项式$C(x)$，以及一个小于$n m$项的多项式$R(x)$。 满足：$A(x)=B(x) C(x 阅读全文

摘要： 冬令营前的一些计划&记录 计划 yyb发现自己很多以前学过的东西完完全全不记得了，所以在接下来的时间里可能会留下多篇复习向的博客，当然也可能因为觉得没有必要复习而到处乱做题。 现在先大概归类一下： 多项式&生成函数： ~~估计停课以后没多久我可能就要讲，所以先复习一遍再对于我自己的课件进行一定量的补 阅读全文

摘要： 【HDU1693】Eat the Trees（插头dp） 题面 "HDU" "Vjudge" 大概就是网格图上有些点不能走，现在要找到若干条不相交的哈密顿回路使得所有格子都恰好被走过一遍。 题解 "这题" 的弱化版本吧。。。 因为可以任意分配哈密顿回路的数量，因此根本不需要再考虑插头的配对问题了，那 阅读全文

摘要： 【BZOJ1814】Ural 1519 Formula 1 （插头dp） 题面 "BZOJ" "Vjudge" 题解 "戳这里" 上面那个链接里面写的非常好啦。 然后说几个点吧。 首先是关于为什么只需要考虑三进制状态，因为哈密顿回路是不可能出现自交的，因此对于当前的轮廓线一定直接分割了哈密顿回路的一 阅读全文

摘要： 【BZOJ3817/UOJ42】Sum（类欧） 题面 "BZOJ" "UOJ" 题解 令$x=\sqrt r$，那么要求的式子是$$\sum_{d=1}^n( 1)^{[dx]}$$ 不难发现，对于每个$d$而言的取值只和$[dx]$的奇偶性相关。 如果$x$是个整数，也就是$r$是完全平方数的时候 阅读全文

摘要： 【BZOJ3821/UOJ46】玄学（二进制分组，线段树） 题面 "BZOJ" "UOJ" 题解 呜，很好的题目啊QwQ。 离线做法大概可以线段树分治，或者直接点记录左右两次操作时的结果，两个除一下就可以直接计算。 强制在线的话，一般而言，分治在线就弄成二进制分组。把所有修改操作进行二进制分组，每次 阅读全文

摘要： 【BZOJ4822】[CQOI2017]老C的任务（扫描线） 题面 "BZOJ" "洛谷" 题解 没有修改操作，都不需要分治了。。。 直接排序之后扫描线算贡献就好了。。。 不知道为啥洛谷上过不了。。。 cpp include include include include include inclu 阅读全文

摘要： 【BZOJ4821】[SDOI2017]相关分析（线段树） 题面 "BZOJ" "洛谷" 题解 看看询问要求的东西是什么。把所有的括号拆开，不难发现要求的就是$\sum x,\sum y,\sum xy,\sum x^2$ 考虑修改操作。先是区间加法，对于$\sum x,\sum y$而言直接加就好 阅读全文

摘要： 【BZOJ4820】[SDOI2017]硬币游戏（高斯消元） 题面 "BZOJ" "洛谷" 题解 第一眼的感觉就是构$AC$自动机之后直接高斯消元算概率，这样子似乎就是$BZOJ1444$了。然而点数太多了，三方的消元没法做。 考虑如何优化点数，首先我们的所有点可以分为两种，一种是终止节点，另外一种 阅读全文

摘要： 【BZOJ4815】[CQOI2017]小Q的表格（莫比乌斯反演，分块） 题面 "BZOJ" "洛谷" 题解 神仙题啊。 首先$f(a,b)=f(b,a)$告诉我们矩阵只要算一半就好了。 接下来是$b f(a,a+b)=(a+b) f(a,b)$ 这个式子怎么看呢？ $$\begin{aligned 阅读全文

摘要： 【BZOJ4813】【CQOI2017】小Q的棋盘（贪心） 题面 "BZOJ" "洛谷" 题解 果然是老年选手了，这种题都不会做了。。。。 先想想一个点如果被访问过只有两种情况，第一种是进入了这个点所在的子树并且还要再次回到它的父亲，那么为了访问这个点你要花费$2$步，另外一种是进入了这个点你不回去 阅读全文

摘要： 【BZOJ3811】玛里苟斯（线性基） 题面 "BZOJ" 题解 $K=1$很容易吧，拆位考虑贡献，所有存在的位出现的概率都是$0.5$，所以答案就是所有数或起来的结果除二。 $K=2$的情况，我们直接拆开平方式，平方项的贡献直接算，出现的概率还是$0.5$，然后$2ab$这样子的东西出现的概率是$ 阅读全文

摘要： 【BZOJ4738/UOJ 276】汽水（点分治，分数规划） 题面 "BZOJ" "UOJ" 题解 今天考试的题目，虽然说是写完了，但是感觉还是半懂不懂的来着。 代码基本照着$Anson$爷的码的，orz。（然后Anson爷的UOJrk1不保了） 首先拿到这道题目的一个比较显然的思路就是分数规划二分 阅读全文

摘要： 【BZOJ4712】洪水（动态dp） 题面 "BZOJ" 然而是权限题QwQ，所以粘过来算了。 Description 小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到 山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山 阅读全文

摘要： 动态dp 这个鬼玩意我已经点开 关上无数次了，当时dkw给洛谷贡模板题的时候还问过我一次来着......然而我并不会，然后，，，，然后NOIP就爆炸了。 所以，趁着难得滚到机房的时间，赶快学习一下QwQ。 直接搬洛谷上的模板题吧 题面 "【P4719】动态dp" 给定一棵$n$个节点的树，点有点权， 阅读全文

摘要： 题面 "洛谷" 题解 等下发链接 代码： cpp include include include include include include include using namespace std; define ll long long define MAX 100100 define inf 阅读全文

摘要： NOIP2018游记 似乎是一些奇怪的东西 没想到我竟然更博了！虽然今天是$11.20$了。 emmmm，为啥是今天呢？因为咕咕F本来说昨天出成绩的，所以本来是昨天更的，然而咕咕F咕了，所以我也咕了，所以就今天更了。 然而NOIP似乎也已经过去了$10$天了，所以可能记忆会有些混乱了，就不要太在意了 阅读全文

摘要： NOIP2015题解 Day1 神奇的幻方 magic 模拟裸题。~~我在NOIP切掉的第一道题~~ 子串 substring $dp$题。 设$f[i][j][k][0/1]$表示当前考虑$A$串的第$i$位，$B$串匹配了第$j$个字符，当前已经分了$k$段，当前$i$位置的字符是否在最后一段中 阅读全文

摘要： NOIP2014题解 Day1 生活大爆炸版石头剪刀布 rps 简单模拟题，注意细节 cpp include include using namespace std; inline int read() { int x=0;bool t=false;char ch=getchar(); while( 阅读全文

摘要： NOIP2013题解 Day1 转圈游戏 circle 快速幂模板题。 花匠 flower 发现要求的就是一个最长波动序列。考虑一种$dp$做法，设$f[i][0/1]$表示当前第$i$个位置，它是峰开始谷，转移的时候分类讨论一下。如果$h_i h_{i+1}$，那么$f[i][1]=f[i 1][ 阅读全文

摘要： NOIP2012题解 Day1 Vigenère 密码 vigenere 直接模拟就好了，对于那张表找找规律就很短了。 Day2 同余方程 mod $exgcd$模板题 疫情控制 blockade 好题。 不难发现可以二分答案。考虑如何$check$。 首先如果一支军队不能走到根节点那么显然它就停在 阅读全文

摘要： NOIP2011题解 当然还是早就做完了啊，重新写一遍。 Day1 铺地毯 carpet 倒着检查最后被哪个覆盖了就好了。 选择客栈 hotel 对于每种颜色维护一下前面有多少个可以和当前这个酒店配对，显然这个是单调递增的。每次找到一个合法的咖啡馆之后显然可以把前面一段连续区间加入贡献，直接开一个桶 阅读全文