标签：le frac Stoi2031 题解 sum LGP7489 dfrac prod subseteq
problem
令 \(f_0(S)=\dfrac{\sigma(S)}{\pi(S)}\)，\(f_k(S)=\sum\limits_{T \subseteq S}f_{k-1}(T)\)。
其中 \(\sigma(S)=\sum\limits_{x \in S}x\) 为 \(S\) 中所有元素之和， \(\pi(S)=\prod\limits_{x \in S}x\) 为 \(S\) 中所有元素之积。
给定 \(n,k,p\) 和集合 \(S\)，求 \(f_k(S) \bmod{p}\) 的值。
对于 \(100\%\) 的数据，\(1 \le n \le 7 \times 10^6,1 \le k \le 10^{18},1 \le x_i<p,1<p<2^{31},p\) 是质数，\(x_i\) 互不相同。
solution
\[\begin{aligned}
f_1(S)=\sum_{T\subseteq S}f_0(T)&=\sum_{T\subseteq S}\dfrac{\sum_{x\in T} x}{\prod_{x\in T}x}\\
&=\sum_{T\subseteq S}\sum_{x\in T} x\prod_{x\in T}\frac{1}{x}\\
&=\sum_{T\subseteq S}\sum_{x\in T}\prod_{y\in T,x\neq y}\frac{1}{y}\\
&=\sum_{x\in S}\sum_{T\subseteq S,x\in T}\prod_{y\in T,x\neq y}\frac{1}{y}\\
&=\sum_{x\in S}\sum_{T\subseteq S\backslash\{x\}}\prod_{y\in T}\frac{1}{y}\\
&=\sum_{x\in S}\prod_{y\in S,x\neq y}\left(1+\frac{1}{y}\right)\\
&=\sum_{x\in S}\frac{z}{1+\frac{1}{x}},\text{where }z=\prod_{x\in S}\left(1+\frac{1}{x}\right)\\
&=\prod_{x\in S}\left(1+\frac{1}{x}\right)\sum_{x\in S}\frac{1}{1+\frac{1}{x}},\\
&=\dfrac{\sum_{x\in T}h(x)}{\prod_{x\in T}h(x)},\text{where }h(x)=\frac{1}{1+\frac{1}{x}}=\frac{x}{x+1}.
\end{aligned}\]
\[\begin{aligned}
f_2(S)=\sum_{T\subseteq S}f_1(T)&=\sum_{T\subseteq S}\dfrac{\sum_{x\in T}h(x)}{\prod_{x\in T}h(x)}\\
&=\dfrac{\sum_{x\in T}h(h(x))}{\prod_{x\in T}h(h(x))}.\\
&\Rightarrow f_k(S)=f_{k-1}(h(S))\Rightarrow f_k(S)=f_0(h^{(k)}(S)),\\
&\text{where }h^{(k)}(S)=h^{(k-1)}(\{\frac{x}{x+1}:x\in S\})=\{\frac{x}{kx+1}:x\in S\}.
\end{aligned}\]
标签：le,
frac,
Stoi2031,
题解,
sum,
LGP7489,
dfrac,
prod,
subseteq
From： https://www.cnblogs.com/caijianhong/p/solution-P7489.html