自动搬运

查看原文

来自洛谷，原作者为

	yizcdl2357 OI(2018.12.30~2025.3.2)

搬运于2025-08-24 22:30:21，当前版本为作者最后更新于2023-03-17 18:05:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

远定义一个集合 $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$。

$k\le 10^{18},n\le 7\times 10^6,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}$$

至此，利用线性求逆看似可 $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，建议加上快读。

#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;
}