反演题目训练

· · 个人记录

loj 6181. 某个套路求和题

题意：

定义函数 f(n)=\prod_{d|n}\mu(d)。

求 \sum_{i=1}^n f(i)\bmod 998244353。

n\le 10^{10}

题解：

如果 n 是素数，那么 f(n)=-1，如果 n 是多于一个素数的乘积，那么 f(n)=1，其他情况下 f(n)=0。

证明：

设 n 是 k 个素数的乘积，则每个素数给 f(n) 的贡献是 (-1)^{2^{k-1}}，f(n)=(-1)^{2^{k-1}\times k}。

所以只有在 k=1 的情况下 f(n)=-1，其他情况 f(n) 都是 1。

所以我们只需要求出 \sum_{i=1}^n\mu(i)^2，以及 n 以内素数的个数。

考虑 $\sum_{i=1}^n \mu(i)^2$ 如何求。 我们考虑一个函数 $g(n)$，表示最大的满足 $d^2|n$ 的整数 $d$。 则 $$\sum_{i=1}^n \mu(i)^2=\sum_{i=1}^n [g(i)=1]$$ $$=\sum_{i=1}^n\sum_{j|g(i)}\mu(j)$$ $$\sum_{j=1}^{\sqrt n}\mu(j)\lfloor\frac n{j^2}\rfloor$$ 线性筛即可。 总复杂度 $O(\sqrt n+\frac{n^{0.75}}{\log n})$。 ## loj 528. 「LibreOJ β Round #4」求和 题意： 给定两个正整数 $n,m$，你需要计算 $$\sum_{i=1}^n\sum_{j=1}^m\mu^2(\gcd(i,j))\bmod 998244353$$ $1\le n,m\le 10^{13}

题解：

首先来推式子，去掉 \gcd。

\sum_{i=1}^n\sum_{j=1}^m\mu(\gcd(i,j))^2 =\sum_{d=1}^{\min(n,m)}\mu^2(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}\sum_{i=1}^{\lfloor\frac m d\rfloor}[\gcd(i,j)=1] =\sum_{d=1}^{\min(n,m)}\mu^2(d)\sum_{d'=1}^{\lfloor\frac{\min(n,m)}d\rfloor}\mu(d')\lfloor\frac n{dd'}\rfloor\lfloor\frac m{dd'}\rfloor \sum_{T=1}^{\min(n,m)}\sum_{d|T}\mu^2(d)\mu(\frac T d)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor

于是我们来研究 f(T)=\sum_{d|T}\mu^2(d)\mu(\frac T d) 这个函数的性质。

可以发现，只有在 T 的每个质因子的次数都是 2 的时候，f(T)=\mu(\sqrt T)，否则 f(T)=0。

证明：

首先，如果 T 的某个质因子的次数 \ge 3，那么 f(T)=0。

然后对于 T 的每个次数为 2 的质因子，d 和 \frac T d 一定各含有一个这个因子。

如果 T 存在某个质因子次数为 1，我们来说明所有贡献都会被抵消掉。

考虑 T 的任意一个次数为 1 的质因子 p，对于 d\times d'=\frac T p，他们给答案的贡献为 \mu^2(dp)\mu(d')+\mu^2(d)\mu(d'p)=\mu^2(d)\mu(d')-\mu^2(d)\mu(d')=0。

如果 T 的所有质因子次数都是 2，那么 f(T)=\mu(\sqrt T)^2\mu(\sqrt T)=\mu(\sqrt T)。

于是答案就是

\sum_{i=1}^{\sqrt {\min(n,m)}}\mu(i)\lfloor\frac n{i^2}\rfloor\lfloor\frac m{i^2}\rfloor

复杂度 O(\sqrt n)。

loj 6244. 七选五

题意：

给三个数 n,m,k，求有多少个用 1\sim n 中的元素组成的长度为 m 的排列 p，满足下面的式子。

\left(\sum_{i=1}^m [p_i=i]\right)=k

答案对 10^9+7 取模。

题解： 签到题。 考虑容斥，设两个函数 $f(x),g(x)$。 $f(x)$ 表示恰好有 $x$ 个位置满足 $p_i=i$ 的排列数量，$g(x)$ 表示钦定 $x$ 个位置满足 $p_i=i$，其他位置任意的排列数量。 则 $$g(x)=\sum_{i=x}^mf(i)\binom i x=\binom m x(n-x)^{\underline{m-x}}$$ $$=\binom m x(n-m+1)^{\overline{m-x}}$$ 由二项式反演，有 $$f(x)=\sum_{i=x}^m g(i)\binom i x(-1)^{i-x}$$ $$=\sum_{i=x}^m \binom m i(n-m+1)^{\overline{m-i}}\binom i x(-1)^{i-x}$$ 复杂度 $O(n)$。 ## loj 6160. 「美团 CodeM 初赛 Round A」二分图染色 题意： 给一个完全二分图，左右两边各 $n$ 个点。我们要把图中的每条边染成红色、蓝色或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数，对 $10^9+7$ 取模。 $1\le n\le 10^7

题解：

首先考虑如果只有红色和绿色的边如何做，相当于是在左右两边各选择一个点集，然后进行匹配，因此方案数为

\sum_{i=0}^n \binom n i\binom n i i!

然而在有红色和蓝色的时候，不能简单地将上面的式子平方，因为那样就会出现某些边同时被染成红色或蓝色的情况。

所以我们考虑容斥。

记 f(x) 为恰好存在 x 条边被同时染成红色和蓝色的方案数，g(x) 为钦定 x 条边被同时染成红色和蓝色的方案数。

则

g(x)=\sum_{i=x}^n f(i)\binom i x=\binom n x\binom n xx!\left(\sum_{i=0}^{n-x}\binom{n-x}i\binom{n-x}ii!\right)^2

由二项式反演，有

f(0)=\sum_{i=0}^n (-1)^ig(i)

所以我们需要快速求出 g(i)。

考虑如何快速求出

s(x)=\sum_{i=0}^x\binom xi\binom xii!

通过OEIS，可以查到 s(n)=2n\times s(n-1)-(n-1)^2\times s(n-2)

考虑使用 s(x) 的组合意义来为 s 找到一个递推式。

那么考虑左右两边第 $1$ 个点是怎样匹配的。 1. 这两个点都没有匹配，方案数为 $s(x-1)$。 2. 这两个点进行匹配，则方案数为 $s(x-1)$。 3. 这两个点分别与别的点进行匹配，则方案数为 $(x-1)^2s(x-2)$。 4. 这两个点一个有匹配，一个没有匹配，发现这个不容易用之前的 $s$ 来表示。 考虑一个小的容斥。 左边第一个点有匹配，而右边的第一个点没有匹配的方案数 $=$ 钦定左边第一个点有匹配的方案数 $-$ 左右两边第一个点都有匹配的方案数。 于是这个方案数为 $x\times s(x-1)-s(x-1)-(x-1)^2s(x-2)$。 于是 $s(x)=2\times s(x-1)+(x-1)^2s(x-2)+2\times(x\times s(x-1)-s(x-1)-(x-1)^2s(x-2))=2x\times s(x-1)-(x-1)^2\times s(x-2)$。 复杂度 $O(n)$。 ## loj 572. 「LibreOJ Round #11」Misaka Network 与求和 题意： 给两个正整数 $n,m$。 求 $\sum_{i=1}^n\sum_{j=1}^nf^m(\gcd(i,j))\bmod 2^{32}$。 其中 $f(x)$ 表示 $x$ 的次大质因数，重复的质因数计算多次。 $1\le n,m\le 2\times 10^9

题解：

首先来消掉 \gcd。

\sum_{i=1}^n\sum_{j=1}^nf(\gcd(i,j))^m =\sum_{d=1}^nf^m(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}\sum_{j=1}^{\lfloor\frac n d\rfloor}[\gcd(i,j)=1] =\sum_{d=1}^nf^m(d)\sum_{d'=1}^{\lfloor\frac n d\rfloor}\mu(d')(\lfloor\frac n {dd'}\rfloor)^2 =\sum_{T=1}^n\sum_{d|T}f^m(d)\mu(\frac T d)(\lfloor\frac n T\rfloor)^2

考虑如何快速求出 \sum_{d|T}f^m(d)\mu(\frac T d) 的前缀和。

由于 f^m * \mu * 1=f^m * e=f^m，所以如果我们获得了 f^m 在所有 \lfloor\frac n i\rfloor 位置的前缀和，就可以通过杜教筛来求出 f^m * \mu 的前缀和。

考虑使用 min25 筛在转移过程中求出答案。

记 p_k 为第 k 个质数，\min_d(i) 表示 i 的最小质因子。

设 S(n,k) 表示 \sum_{i=1}^n [\min_d(i)\ge p_k][i\not\in Prime]f^m(i)。

考虑转移，如果 p_k 不是次大质因子，那么

S(n,k)=S(n,k+1)+\sum_{p_k^e\le n}S(\lfloor\frac n {p_k^e}\rfloor,k+1)

如果 p_k 是次大质因子，那么它给 S(n,k) 的贡献是

p_k^m\sum_{p_k^e\le n}P(\lfloor\frac n{p_k^e}\rfloor)-k+[e\neq 1] 总复杂度 $O(\frac{n^{0.75}}{\log n}+n^{\frac 2 3})$。 ## loj 2476. 「2018 集训队互测 Day 3」蒜头的奖杯 题意： 给六个长度为 $n$ 的序列 $A,B,C,D,E,F$。 求 $$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}E_{\gcd(i,k)}F_{\gcd(j,k)}$$ $1\le n\le 10^5

题解：

考虑一种 X\rightarrow X' 的变换，使得 X_i=\sum_{j|i}X'_j。

也就是 X=X' * 1,X'=X * \mu。

这个是为了方便地处理 \gcd。

然后开始推式子。

\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}E_{\gcd(i,k)}F_{\gcd(j,k)} =\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_k\sum_{p|i,p|j}D'_p\sum_{q|i,q|k}E'_qF_{\gcd(j,k)} =\sum_{i=1}^nA_i\sum_{p|i}D'_p\sum_{q|i}E'_q\sum_{j=1}^{\lfloor\frac n p\rfloor}B_{pj}\sum_{k=1}^{\lfloor\frac n q\rfloor}C_{qk}F_{\gcd(pj,qk)}

将 D',E' 提前，并设 s=\gcd(p,q)。这样就有 spq\le n。

=\sum_{s=1}^n\sum_{p=1}^{\lfloor\frac n s\rfloor}D'_p\sum_{q=1}^{\lfloor\frac n {sp}\rfloor}E'_q[\gcd(p,q)=1]\sum_{i=1}^{\lfloor\frac n {spq}\rfloor}A_{ispq}\sum_{j=1}^{\lfloor\frac n{sp}\rfloor}B_{spj}\sum_{k=1}^{\lfloor\frac n{sq}\rfloor}C_{sqk}F_{s\times\gcd(pj,qk)}

这样可以设 m=\lfloor\frac n s\rfloor，B1_i=B_{is}，C1_i=C_{is},F1_i=F_{is}。

则后面就变成了

\sum_{j=1}^{\lfloor\frac m p\rfloor}B1_{pj}\sum_{k=1}^{\lfloor\frac m q\rfloor}C_{qk}F1_{\gcd(pj,qk)}

然后对 F1 进行变换

\sum_{j=1}^{\lfloor\frac m p\rfloor}B1_{pj}\sum_{k=1}^{\lfloor\frac m q\rfloor}C_{qk}\sum_{r|pj,r|qk}F1'_r =\sum_{j=1}^m B1_j[j\bmod p=0]\sum_{k=1}^m C1_k[k\bmod q=0]\sum_{r|j,r|k}F1'_r =\sum_{j=1}^m B1_j[j\bmod p=0]\sum_{r|j}F1'_r\sum_{r|k}C1_k[k\bmod q=0]

我们可以枚举 s,p，令 tmp_j=B1_j[j\bmod p=0]，然后令 tmp'_j=F1'_j\sum_{j|k}tmp_k，令 tmp''_j=C1_j\sum_{k|j}tmp'_k。

然后对于一个 q，查询 \sum_{i=1}^m tmp''_j[j\bmod q=0] 即可。

因为 p,q 可以互换，所以我们枚举 p,q 中较小的那个，这样求 tmp 的次数为 \sqrt m。

对于一个 m，复杂度为

O(m^{1.5}\log\log m)

这个是因为在 tmp 变化过程中，可以枚举素数来做到 O(m\log\log m)。

总复杂度

O\left(\sum_{i=1}^n \left(\sqrt{\frac n i}\right)^{1.5}\log\log n\right)=O(n^{1.5}\log\log n)

CF997C Sky Full of Stars

题意：

给一个 n\times n 的正方形网格，要求用红绿蓝三种颜色对每个格子进行染色，求至少有一行或一列为同色的方案数，对 998244353 取模。

1\le n\le 10^6

题解：

考虑二维的容斥，f(x,y) 表示恰好有 x 行 y 列为同色的方案数，g(x,y) 表示钦定 x 行 y 列是同色的方案数。

则

g(x,y)=\sum_{i=x}^n\sum_{j=y}^n f(i,j)\binom i x\binom j y f(x,y)=\sum_{i=x}^n\sum_{j=y}^n g(i,j)\binom i x\binom j y(-1)^{i-x+j-y}

我们只需要求出 f(0,0) 即可。

考虑 g 的表达式。

3^{n^2},& i=0,j=0\\ 3^j\binom n j\times 3^{(n-j)n},& i=0,j>0\\ 3^i\binom n i\times 3^{(n-i)n},& i>0,j=0\\ 3\binom n i\binom n j\times 3^{(n-i)(n-j)},& i>0,j>0 \end{cases}

所以我们要求的

f(0,0)=3^{n^2}+2\sum_{i=1}^n 3^i\binom n i3^{(n-i)n}(-1)^i+3\sum_{i=1}^n\sum_{j=1}^n\binom n i\binom n j3^{(n-i)(n-j)}(-1)^{i+j}

前两个部分都可以容易求出，考虑

\sum_{i=1}^n\sum_{j=1}^n\binom n i\binom n j3^{(n-i)(n-j)}(-1)^{i+j} =\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\binom n i\binom n j3^{ij}(-1)^{i+j} =\sum_{i=0}^{n-1}\binom n i(-1)^i\sum_{j=0}^{n-1}\binom n j(-3^i)^j =\sum_{i=0}^{n-1}\binom n i(-1)^i\left((-3^i+1)^n-(-3^i)^n\right)

复杂度 O(n\log n)。

CF1278F Cards

题意：

有 m 张牌，其中一张是王牌。现在你执行 n 次如下操作：洗牌后查看第一张牌是什么。

令 x 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 m! 种牌的排列出现的概率均相等，求 x^k 的期望值，对 998244353 取模。

1\le n,m< 998244353,1\le k\le 5000

题解：

我们要求的东西是

\sum_{i=0}^n\binom n i\left(\frac 1 m\right)^i\left(\frac {m-1}m\right)^{n-i}i^k

考虑用第二类斯特林数来处理 i^k。

n^m=\sum_{i=0}^m\begin{Bmatrix}m \\ i\end{Bmatrix}n^{\underline i}

上面的式子变为

\sum_{i=0}^n\binom n i\left(\frac 1 m\right)^i\left(\frac {m-1}m\right)^{n-i}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}i^{\underline j} =\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=0}^n\binom n ii^{\underline j}\left(\frac 1 m\right)^i\left(\frac {m-1}m\right)^{n-i} =\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=j}^n\binom n ii^{\underline j}\left(\frac 1 m\right)^i\left(\frac {m-1}m\right)^{n-i} =\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=j}^nn^{\underline j}\binom {n-j}{i-j}\left(\frac 1 m\right)^i\left(\frac {m-1}m\right)^{n-i} =\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline j}\left(\frac 1 m\right)^j\sum_{i=j}^n\binom {n-j}{i-j}\left(\frac 1 m\right)^{i-j}\left(\frac {m-1}m\right)^{n-i} =\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline j}\left(\frac 1 m\right)^j

求出 \begin{Bmatrix}k\\j\end{Bmatrix} 即可 O(k) 计算。

复杂度 O(k^2) 或 O(k\log k)。

agc035f Two Histograms

题意：

有一个 n\times m 的表格，初始时每个位置都是 0。

你需要进行下列操作：

对于每个 1\le i\le n，选出一个整数 0\le r_i\le m，然后给第 i 行的前 r_i 个格子加一。

对于每个 1\le j\le m，选出一个整数 0\le c_j\le n，然后给第 j 列的前 c_j 个格子加一。

求最终能获得多少种表格，答案对 10^9+7 取模。

1\le n,m\le 5\times 10^5

题解：

考虑什么情况会产生重复。

如果存在某一行 i 和某一列 j 满足 r_i=j-1，并且 c_j=i，那么它会和 r_i=j,c_j=i-1 的情况重复。

对于一种方案，从大到小枚举 i，如果存在 j 满足 r_i=j-1 且 c_j=i，就把 r_i 变成 j，c_j 变成 i-1，最后会达到一个不存在 r_i=j-1 且 c_j=i 的方案。

所以我们要求的是对于任意的 i,j，都不满足 r_i=j-1 且 c_j=i 的方案数。

并且，一个行最多和一个列满足 r_i=j-1 且 c_j=i，对于列也是这样。

考虑进行容斥，设 f(x) 为恰好有 x 对行列，满足 r_i=j-1,c_j=i 的方案数，g(x) 为钦定 x 对行列满足 r_i=j-1,c_j=i 的方案数。

g(x)=\sum_{i=x}^{\min(n,m)}f(i)\binom i x f(x)=\sum_{i=x}^{\min(n,m)}g(i)\binom i x(-1)^{i-x} f(0)=\sum_{i=0}^{\min(n,m)}g(i)(-1)^i g(x)=\binom n x\binom m x x!(m+1)^{n-x}(n+1)^{m-x}

复杂度 O(n)。

arc101e Ribbons on Tree

题意：

给一棵 n 个点的树，n 为偶数，要求将 n 个点划分为 \frac n 2 个点对，然后对于每个点对 (x,y)，覆盖 x 到 y 的最短路径。求有多少种方案，满足树上每一条边都被覆盖了至少一次。答案对 10^9+7 取模。

2\le n\le 5000

题解：

考虑进行容斥，设 f(x) 为恰好 x 条边没有被覆盖的方案数，g(x) 表示钦定 x 条边没有被覆盖的方案数，则

g(x)=\sum_{i=x}^{n-1}f(i)\binom i x f(x)=\sum_{i=x}^{n-1}g(i)\binom i x(-1)^{i-x}

我们要求的是

f(0)=\sum_{i=0}^{n-1}g(i)(-1)^i

考虑在树上钦定 x 条边没有被覆盖时，剩下的点被划分为了 x+1 个连通块，设它们的大小为 a_1,a_2,\cdots,a_{x+1}。

设 s(x) 表示一个大小为 x 的连通块的划分方案数。

s(x)=\begin{cases} 0,& x\equiv 1\pmod 2\\ (x-1)(x-3)\cdots1,&x\equiv 0\pmod 2 \end{cases}

则这个方案的贡献是 (-1)^x\prod_{i=1}^{x+1}s(a_i)。

考虑进行 dp，dp(i,j) 表示 i 的子树中 i 所在的连通块大小为 j 时的容斥系数和。

即可 O(n^2) 进行 dp。