子集计数2

• 题目大意

  给定集合 \(S=\{x\ |\ 1\le x\le n,(x,n)=1\}\) ，求有多少 \(T\sube S\) ，满足 \(\sum_{t\in T}t\equiv k\pmod n\) 。

  对 \(998244353\) 取模。

  \(2\le n <998244353,0\le k<n\)

• 题解

  考虑生成函数，显然 \(OGF\) 为：

  \[F(x)=\prod_{(i,n)=1}(1+x^i) \]

  那么我们也就是要求：

  \[Ans=\sum_{i\ge0}[n|(i-k)][x^i]F(x)\=\sum_{i\ge0}\frac{1}{n}\sum_{j=1}^n\omega_n^{(i-r)j}[x^i]F(x)\=\frac{1}{n}\sum_{j=1}^n\omega_n^{-rj}\sum_{i\ge0}\omega_n^{ij}[x^i]F(x)\=\frac{1}{n}\sum_{j=1}^n\omega_n^{-rj}F(\omega_n^j)\\]

  到这里发现不太好做，考虑将 \(F(\omega_n^j)\) 展开，那么有：

  \[Ans=\frac{1}{n}\sum_{j=1}^n\prod_{(i,n)=1}(1+\omega_n^{ij})\omega_n^{-rj}\\]

  发现后面的乘长得很像分圆多项式，考虑令 \((n,j)=d\) ，所以：

  \[Ans=\frac{1}{n}\sum_{j=1}^n\prod_{(i,n)=1}(1+\omega_{\frac{n}{d}}^{i\frac{j}{d}})\omega_{\frac{n}{d}}^{-r\frac{j}{d}} \]

  因为此时 \((\frac{n}{d},\frac{j}{d})=1\) ，所以我们考虑 \(\prod_{(i,n)=1}(1+\omega_d^i)\) 与 \(\prod_{(i,d)=1}(1+\omega_d^i)\) 的关系。

  令 \(A_1=\{x\ |\ (x,n)=1,1\le x\le n\},\ A_2=\{x\ |\ (x,d)=1,1\le x\le d\}\) ，那么不难发现对于群 \(G_1=<A_1,\times_{mod\ n}>,G_2=<A_2,\times_{mod\ d}>\) ，存在映射 \(f:G_1\to G_2: x\bmod d\) 为同态。由同态基本定理知 \(G_1/Kerf\cong Imf\) ，所以 \(\prod_{(i,n)=1}(1+\omega_d^i)=\left[\prod_{(i,d)=1}(1+\omega_d^i)\right]^{\frac{\varphi(n)}{\varphi(d)}}\) 。

  那么我们有：

  \[Ans=\frac{1}{n}\sum_{j=1}^n\left[\prod_{(i,\frac{n}{d})=1}(1+\omega_{\frac{n}{d}}^{i})\right]^\frac{\varphi(n)}{\varphi(\frac{n}{d})}\omega_{\frac{n}{d}}^{-r\frac{j}{d}}\=\frac{1}{n}\sum_{d|n}\left[\prod_{(i,\frac{n}{d})=1}(1+\omega_{\frac{n}{d}}^i)\right]^\frac{\varphi(n)}{\varphi(\frac{n}{d})}\sum_{j=1}^\frac{n}{d}\omega_\frac{n}{d}^{-rj}[(j,\frac{n}{d})=1]\\]

  在后面套个莫比乌斯反演，可得：

  \[Ans=\frac{1}{n}\sum_{d|n}\left[\prod_{(i,\frac{n}{d})=1}(1+\omega_{\frac{n}{d}}^i)\right]^\frac{\varphi(n)}{\varphi(\frac{n}{d})}\sum_{t|\frac{n}{d}}\mu(t)\frac{n}{dt}[\frac{n}{dt}|r]\=\frac{1}{n}\sum_{d|n}\left[\prod_{(i,d)=1}(1+\omega_{d}^i)\right]^\frac{\varphi(n)}{\varphi(d)}\sum_{t|(d,r)}\mu(\frac{d}{t})t \]

  那么我们只需要求出 \(\prod_{(i,d)=1}(1+\omega_d^i)\) 。

  考虑分圆多项式，我们有：

  \[\Phi_n(x)=\prod_{(i,n)=1}(x-\omega_n^i)\\Phi_n(-x)=\prod_{(i,n)=1}(-x-\omega_n^i)\(-1)^{\varphi(n)}\Phi_n(-x)=\prod_{(i,n)=1}(x+\omega_n^i) \]

  不妨设 \(S_n=(-1)^{\varphi(n)}\Phi_n(-1)\) 所以：

  \[Ans=\frac{1}{n}\sum_{d|n}S_d^\frac{\varphi(n)}{\varphi(d)}\sum_{t|(d,r)}\mu(\frac{d}{t})t \]

  通过一番打表可以发现，\(S_d\neq 1\iff d=2p^k\ (p\in prime)\or d=1,2\) 。其中

  • \(S_1=2\)
  • \(S_2=0\)
  • \(S_{2p^k}=p\)

  这样我们就能在 \(\mathcal O (d(n)^2)\) 的复杂度解决问题。

• 关于最后分圆多项式值的证明

  首先有：

  • \(\Phi_1(x)=x-1\to S_1=2\)
  • \(\Phi_2(x)=x+1 \to S_2=0\)
  • \(\Phi_{2p^k}(x)=\sum_{i=0}^{p-1}(-1)^ix^{ip^{k-1}}\to S_{2p^k}=p\ (p\in prime\and k\ge1)\)

  接下来考虑非特殊情况。

  根据定义，我们可以得到：

  \[\prod_{d|n}\Phi_d(x)=x^n-1 \]

  即：

  \[\Phi_n(x)=\frac{x^n-1}{\prod_{d|n\and d<n}\Phi_d(x)} \]

  考虑归纳证明。

  显然有 \(\Phi_3(x)=x^2+x+1\to S_3=1\) ，我们分奇偶性讨论。

  • \(2\nmid n:\)

    根据给出的式子以及归纳假设不难发现 \(\Phi_n(-1)=-1\to S_n=1\)

  • \(2\mid n:\)

    因为 \(\Phi_2(-1)=0\) 无法代值除去，考虑因式分解。

    不妨设 \(n=2^{k+1}q\ (k\ge 0,2\nmid q)\)，那么：

    \[x^n-1=x^{2^{k+1}q}-1=(x^{2^kq}+1)(x^{2^{k-1}q}+1)\cdots(x^q+1)(x^q-1) \]

    考虑利用 \(x^q+1\)，有：

    \[\frac{x^q+1}{x+1}=\sum_{i=0}^{q-1}(-1)^ix^i \]

    所以扣掉 \(\Phi_2(x)\) 后，代入 \(-1\) ，有：

    \[\Phi_n(-1)=\frac{2^kq\times(-2)}{(-2)\times2^kq}=1 \]

    所以 \(S_n=1\) 。

  综上所述，除了我们给出的特殊情况外 \(S_n\) 均等于 \(1\) ，命题得证。

子集计数2

原文：https://www.cnblogs.com/leukocyte/p/14546551.html