容斥与简单反演乱写

AtCoder-ARC114_ANotcoprime\(50\)内的质数只有\(15\)个，可能的答案也就只有\(2^{15}\)个，直接枚举。提交记录：Submission-AtCoderAtCoder-ARC114_BSpecialSubsets就是\(i\)与\(f_i\)连边，每个连通块都是基环树，一定能剥叶子变成环，所以答案就是连通块非空子集个数。......

题目问有多少个长度为\(n\)的排列\(P\)满足\(|P_i-i|=1\)的\(i\)的个数恰好为\(k\)个分析设\(dp_{i,j,k}\)表示前\(i\)个数钦定\(j\)个数满足上述条件且现在\(i\)和\(i+1\)因此被占用的方案数。那么第\(i\)个满足上述条件无非就是放入\(i-1\)或者\(......

前言/声明首先，本人的数论水平极低，目前莫反只是刚刚入门的水平，此博客的主要作用是用于记录本人的学习过程，真的想要深入了解莫反的话这边推荐cmd大佬的博客（点这里），应该对你有更大帮助。建议学习的时候能多理解些就多去理解，少硬记些结论，这样更不容易忘记。前置知识：最基础的数论。......

莫比乌斯反演今天是世纪性的一天，因为我又又又又来看数论且弄懂了qwq。前置知识:,(我们需要将式子化为整数分块可以解决的形式)莫比乌斯函数->函数构成当时,当,且为互异质数时,;(也就是就是分解质因数后，没有幂次大于2的质因子，此时函数值根据分解的个数决定)只要含有......

前置知识\(1.\)艾佛森括号：\([P]=\begin{cases}1&\mathtt{(if\P\is\true)}\\0&\mathtt{(otherwise)}\end{cases}\)\(2.\)\(a\midb\)表示\(a\)是\(b\)的因子\(3.\)整除分块：\(\displaystyle\sum_{i=1}^n\lfloor\dfrac{N}{i}\rfloor\......

前置知识整除分块把之前写的博客搬过来了模型求\(\large\sum^{n}_{i=1}\lfloor{\frac{n}{i}}\rfloor\)假设\(n\)等于10，我们可以列出下表：\(\i\)12345678910\(\frac{10}{i}\)10532211111如果我们的\(n\)更大时，我们可以发现\(\fra......

前言某次考试不会这个被打爆了，现在觉得可能有学习的必要。Min-Max容斥我们现在有一个全集\(U\)，设\(\min(S)\)为集合\(S\)中的最小值，\(\max(S)\)为最大值。\[\max(S)=\sum_{T\subseteqS}(-1)^{|T|+1}\min(T)\\\min(S)=\sum_{T\subseteqS}(-1)^{|T|+1}\max(T)\\\]然......

故事的起因是模拟赛遇到了一道题：\(N,M\le1e7\)赛时想到了其实可以去枚举原地不动的步数，然后catalan去计算方案数，但是有一个问题，就是这个限制：这个过程不能走出格子这就相当于说我有一个栈，大小为m，要放入i个数，2*i次操作每次选择放入和拿出的方案数，但是栈不能取空，同时也不能爆栈......

01容斥定理容斥定理（简单情况）对任意两个有限集合 A 和 B ，有=+-其中，分别表示 A ，B 的元素个数．推广结论：对于任意三个有限集合 A , B , C ，有= ++---+有限集合的计数方法1：利用容斥定理的上述两个公式计算有限集合的元素个数．有限集合的计数方法2：文氏图法，即首先根......

基本内容莫比乌斯函数\(\mu\)定义为\(1\)的逆。一些小性质：\(\mu*1=\epsilon\)\(\mu*\text{id}=\varphi\)反演内容我的理解是：\[[a=1]=\sum\limits_{d|a}\mu(d)\]典型例题例1P2398GCDSUM求\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j)\]来推下式......