scmmm's blog

咕咕咕 fft 虚树 splay 计算几何 考古学习 网络瘤 线性基 背包9讲 题目/比赛报告 题目 比赛 CF 372C CF GR 831

算法学习 写的题 20221020 沈阳ICPC 2019 L 感觉像铜牌题 完全图中剔除一棵树，询问剩下的图存在多少种边为n的匹配，很容易想到容斥，并且只剔除了一颗树，剩下的一定可以在剩下子图中匹配。 考虑 fi,j,0/1f_{i,j,0/1}fi,j,0/1​ 表示以 iii 为根的子树中包含 kkk 种匹配的方案数，那么显然有一个树形背包的转移方式。 123g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp;g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp;g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp; 根据容斥原理，总的方案数即为 ans=∑i=0n(−1)nf1,i,0/1ans=\sum_{i=0}^{n}\limits(-1)^n{f_{1,i,0/1}}ans=i=0∑n​(−1)nf1,i,0/1​ 12345678910111213141 ...

前言 本文只要写一些数论以及它的trick 最基础的部分 唯一分解定理 x=Πpikix=\Pi{p_i^{k_i}}x=Πpiki​​ 公约数 欧几里得求法 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb) 辗转相除法 gcd⁡(a,b)=gcd⁡(a−b,b)\gcd(a,b)=\gcd(a-b,b)gcd(a,b)=gcd(a−b,b) 显然的，小的哪个数应该放在后面，如果小的是 000 ，说明没有余数，最大公约数是 aaa 唯一分解定理 gcd⁡(a,b)=Πpimin⁡(k1i,k2i)\gcd(a,b)=\Pi{p_i^{\min(k1_i,k2_i)}}gcd(a,b)=Πpimin(k1i​,k2i​)​ exgcd 当我们想要ax+by=k∗gcd⁡(a,b),k∈Z,K≠0ax+by=k*\gcd(a,b),k\in Z , K \neq 0ax+by=k∗gcd(a,b),k∈Z,K=0的时候，这个时候就需要拓展欧几里得（至于为啥是这么多,看下面的证明） 假设我们现 ...

博客标准： 与其说是标准，不如是规划： 目前准备接着上一代的基础，规划为以下几个部分 生物学部分 OI(ACM) AI 一些没啥用的基础 算法学习笔记 图形分析 可能有些软件使用方法？ XCPC 游记 NLP 可能有些算法学习？ 日常刷题记 python R语言 应该会有很多重合的，不一定会这么弄，但是这个表格也会更新的。 20221029 草我怎么在考古式学习 20221101 我瑞曲星了，居然才知道 mathjax\text{mathjax}mathjax 换行要爆炸，可能我会考虑改成 katex\text{katex}katex ? 20221107 每周练题都放在训练记里面，里面不弄算法学习，如果自己觉得有很好的 tricks\text{tricks}tricks 就会放在别的博客里。

删去 butterfly 的在页脚标识 这个太丑了，因此删去 找到 "\themes\butterfly\layout\includes\footer.pug" 改成 123456789101112131415161718#footer-wrap if theme.footer.owner.enable - var now = new Date() - var nowYear = now.getFullYear() if theme.footer.owner.since && theme.footer.owner.since != nowYear .copyright!= `©${theme.footer.owner.since} - ${nowYear} By ${config.author}` else .copyright!= `©${nowYear} By ${config ...

经过接近两年的 AFO\text{AFO}AFO 本蒟蒻终于上了威海某个世界一流大学，但是专业并不理想，但并不会放弃 ACM,CTF\text{ACM,CTF}ACM,CTF 等 CS\text{CS}CS 东西，并且准备搞生物信息学 目前会放一些算法学习笔记，并且重置一下初高中写过的东西，也许现在太菜了，并且自己有完美主义（实际上应该是每个人都应该具备的学术严谨），可能会很咕。

图论入门 前言 可能有锅 内容 比较基础的定义 图的定义 ： 一个G={V,E,w}G=\{V,E,w\}G={V,E,w} 分别为边集，点集，关系 也有二元组定义 重边的定义：(u,v)(u,v)(u,v)重复的边 独立集(或者稳定集)定义：图 $G $中两两互不相邻的顶点构成的集合 二部图(或二分图)定义:设G=(V,E)G=(V,E)G=(V,E)是一个无向图，如果顶点VVV可分割为两个互不相交的子集(A,B)(A,B)(A,B)，并且图中的每条边(i，j)(i，j)(i，j)所关联的两个顶点iii和jjj分别属于这两个不同的顶点集 图的色数χ(G)\chi(G)χ(G) 给定图形边缘所需的最少颜色数量称为图形的边色数。 一个图是k−k-k−分的当且仅当色数为kkk 子图的定义 V(H)⊆V(G),E(H)⊆E(G)V(H) \subseteq V(G),E(H)\subseteq E(G)V(H)⊆V(G),E(H)⊆E(G)或者说GGG包含HHH 同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个 ...