莫比乌斯反演题目总结
掌握莫反的核心：通过不断的变换枚举顺序和莫反的常见性质及推论，来把问题转换为一部分可以直接进行枚举，另一部分可以预处理的形式. YY的GCD（洛谷P2257） 给定 N,MN, MN,M，求 1≤x≤N1 \leq x \leq N1≤x≤N，1≤y≤M1 \leq y \leq M1≤y≤M 且 gcd(x,y)\gcd(x, y)gcd(x,y) 为质数的 (x,y)(x, y)(x,y) 有多少对。 输入格式 第一行一个整数 TTT 表述数据组数。 接下来 TTT 行，每行两个正整数，N,MN, MN,M。 输出格式 TTT 行，每行一个整数表示第 iii 组数据的结果。 T=104T = 10^4T=104，N,M≤107N, M \leq 10^7N,M≤107。 由题意可知，让求： ∑i=1n∑j=1m[gcd(i,j)∈prime]\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]∑i=1n∑j=1m[gcd(i,j)∈prime] 按照莫反的套路，把枚举顺序改为先枚举gcdgcdgcd，不妨令n≤mn\le...
多项式基础知识（3）
例题（本部分主要讲解一些比较经典的多项式问题和一些icpcicpcicpc区域赛的真题） 付公主的背包（洛谷P4389） 付公主有一个可爱的背包qwq,这个背包最多可以装 10510^5105 大小的东西 付公主有 nnn 种商品，她要准备出摊了，每种商品体积为 viv_ivi，都有无限件.给定 mmm，对于 s∈[1,m]s\in [1,m]s∈[1,m]，请你回答用这些商品恰好装 sss 体积的方案数. 第一行两个正整数 n,mn,mn,m。 第二行 nnn 个正整数，表示每种商品的体积。 1≤n,m≤1051\le n,m \le 10^51≤n,m≤105，1≤vi≤m1\le v_i \le...
多项式基础知识（2）
（一）多项式求逆 给定一个多项式 F(x)F(x)F(x) ，请求出一个多项式 G(x)G(x)G(x)， 满足 F(x)∗G(x)≡1(modxn)F(x) * G(x) \equiv 1 \pmod{x^n}F(x)∗G(x)≡1(modxn)。系数对 998244353998244353998244353 取模。 1≤n≤1051 \leq n \leq 10^51≤n≤105，0≤ai≤1090 \leq a_i \leq 10^90≤ai≤109。 设原多项式为AAA，模xnx^nxn的逆元为BBB，模x⌈n2⌉x^{\lceil\frac{n}2\rceil}x⌈2n⌉逆元为B′B'B′,则可得: A∗B′≡1 (mod x⌈n2⌉) 1◯A*B'\equiv 1\ (mod \ x^{\lceil\frac{n}2\rceil})\ \ \ \text{\textcircled 1}A∗B′≡1 (mod x⌈2n⌉) 1◯ A∗B≡1 (mod x⌈n2⌉) 2◯A*B \equiv 1\ (mod \...
多项式基础知识（1）
（一）多项式乘法(无模数) 核心算法：FFT算法（本质上是利用复数的循环性，并通过分治来优化） 单位根的性质 ωnk=cos(2kπn)+sin(2kπn)i{\omega_n}^k =...