P7489 「Stoi2031」手写的从前 题解
yizcdl2357
·
·
题解
题意
远定义一个集合 S 的 权值 为 \dfrac{\sigma(S)}{\pi(S)}，其中 \sigma(S)=\sum\limits_{x \in S}x 为 S 中所有元素之和， \pi(S)=\prod\limits_{x \in S}x 为 S 中所有元素之积。甜问他，一个集合 S 的 所有子集 的 权值 和是多少？远很快就算出了答案。甜又问，那 所有子集 的 所有子集 的 权值 和之和是多少？远又很快就算了出来。于是甜又问了一个问题，问题中总共有 k 个 所有子集，这下远算不完了，所以他找你帮忙。远不需要回答一个太大的数，所以答案只要取模 p。
# 解法
容易想到计算 $S$ 的每个子集对答案的贡献。
于是本题自然分为两步：每个子集对答案贡献多少次？贡献之和是多少？
## 第一步
要求一个子集在“所有子集 的 ……（$k$ 个）的 所有子集”中出现多少次。
即，在 $S$ 中选出 $k$ 个子集 $S_1,\cdots,S_k$ 使得 $S_i\subseteq S_{i-1}$ 且 $S_k=T$，问有几种方法。
显然，只要两种选取方法中某个数的出现次数不同，这两种方法就是不同的。（因为子集前一个包含后一个）于是反过来思考：考虑每个数属于多少个集合。
对于集合 $T$ 中的数，必然属于所有 $k$ 个子集；对于不在 $T$ 中的数（$|S|-|T|$ 个），可以有 $k$ 中不同的“属于方式”：属于 $0$ 个子集、$1$ 个子集……$k-1$ 个子集。（为什么不能属于 $k$ 个？因为它不在 $S_k$ 中。）
因此 $T$ 出现了 $k^{|S|-|T|}$ 次。
## 第二步
答案是每个子集 $T$ 的出现次数乘上 $\dfrac{\sigma(T)}{\pi(T)}$：
$$\begin{aligned}
&\sum_{T\subseteq S}k^{|S|-|T|}\dfrac{\sigma(T)}{\pi(T)}\\
=&\sum_{T\subseteq S}\dfrac{k^{|S|-|T|}}{\pi(T)}\sum_{x\in T} x\\
=&\sum_{x\in S} x\sum_{T\subseteq S,x\in T}\dfrac{k^{|S|-|T|}}{\pi(T)}\\
=&\sum_{x\in S} \dfrac{x}{1+kx}\sum_{T\subseteq S,x\in T}\dfrac{(1+kx)k^{|S|-|T|}}{\pi(T)}\\
=&\sum_{x\in S} \dfrac{x}{1+kx}\sum_{T\subseteq S,x\in T}\dfrac{k^{|S|-|T|+1}\times x}{\pi(T)}+\dfrac{k^{|S|-|T|}}{\pi(T)}\\
=&\sum_{x\in S} \dfrac{x}{1+kx}\sum_{T\subseteq S,x\in T}\dfrac{k^{|S|-(|T|-1)}}{\dfrac{\pi(T)}{x}}+\dfrac{k^{|S|-|T|}}{\pi(T)}\\
=&\sum_{x\in S} \dfrac{x}{1+kx}\sum_{T\subseteq S}\dfrac{k^{|S|-|T|}}{\pi(T)}\\
=&\sum_{x\in S} \dfrac{xk^{|S|}}{1+kx}\sum_{T\subseteq S}\dfrac{1}{\prod_{y\in T} ky}\\
\end{aligned}$$
对此式后半部分因式分解：
$$\begin{aligned}
=&\left(\sum_{x\in S} \dfrac{xk^{|S|}}{1+kx}\right)\prod_{x\in S}1+\dfrac{1}{kx}\\
\end{aligned}$$
至此，利用[线性求逆](https://www.luogu.com.cn/problem/P5431)看似可 $O(n)$ 计算，但是有一个小问题：$1+kx$ 的逆元可能不存在。因此，将原式变形为
$$\begin{aligned}
&\left(\sum_{x\in S} \dfrac{x}{1+kx}\right)\prod_{x\in S}\dfrac{1+kx}{x}\\
=&\left(\sum_{x\in S} \dfrac{x\prod_{y\in S}1+ky}{1+kx}\right)\prod_{x\in S}\dfrac{1}{x}\\
=&\left(\sum_{i=1}^n \dfrac{a_i\prod_{j=1}^n1+ka_j}{1+ka_i}\right)\prod_{i=1}^n\dfrac{1}{a_i}\\
=&\left(\sum_{i=1}^n a_i\prod_{j=1}^{i-1}1+ka_j\prod_{j=i+1}^{n}1+ka_j\right)\dfrac{1}{\prod_{i=1}^na_i}\\
\end{aligned}$$
用前缀积预处理出
$$\text{pre}_x=\prod_{j=1}^{x}1+ka_j,\text{suf}_x=\prod_{j=x}^{n}1+ka_j$$
即可计算。并且只用求一次逆元，不需要线性求逆。
# 代码
记得开 `long long`，建议加上快读。
```cpp
#include<bits/stdc++.h>
#define int long long
#define N 7000000
using namespace std;
int n,k,M,a[N+5],prod=1,pre[N+5],suf[N+5],ans;
inline int read()
{
int x=0;
char cc=getchar();
while(cc<'0'||cc>'9')cc=getchar();
while(cc>='0'&&cc<='9')x=x*10+cc-'0',cc=getchar();
return x;
}
inline int tyfc(int x,int y)
{
if(y==1) return 0;
return ((1-y*tyfc(y%x,x))/x%y+y)%y;
}
signed main()
{
n=read(),k=read(),M=read();k%=M;
for(int i=1;i<=n;i++)
a[i]=read(),
prod=prod*a[i]%M,
pre[i]=suf[i]=(1+k*a[i])%M;
pre[0]=suf[n+1]=1;
for(int i=2;i<=n;i++) pre[i]=pre[i]*pre[i-1]%M;
for(int i=n-1;i>=1;i--) suf[i]=suf[i]*suf[i+1]%M;
for(int i=1;i<=n;i++) ans=(ans+a[i]*pre[i-1]%M*suf[i+1]%M)%M;
cout<<ans*tyfc(prod,M)%M;
return 0;
}
```