本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-04 11:37:03

:::::info[题目基本信息] 考察：数学，动态规划 DP，容斥（$2700$）。
题目简介：
给定序列 $\{a_n\}$，设：
$$x_k=\lfloor\frac{x}{10^k}\rfloor\bmod 10$$ $$f(S)=\sum_{i=0}^510^i\min_{x\in S}x_i$$ 求：
$$\bigoplus_{i=0}^{999999}i((\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2)\bmod(10^9+7))$$ 数据范围：

• $1\le n\le 10^5$
• $\forall i\in[1,n],0\le a_i\le 999999$ ::::: 不妨设 $\displaystyle G(i)=\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2$，注意到 $f(S)=i$ 这个条件过于严格，不好统计，考虑容斥。
  设 $\displaystyle g(i)=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2$，其中，定义两个整数 $x,y$ 之间满足 $x\subseteq y$ 当且仅当 $\forall k\in[0,5],x_i\le y_i$，最终我们也可以得到 $g(i)$ 的转移方程式（？）：
  $$\begin{aligned}g(i)&=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2\&=\sum_{S\subseteq\{a_n\}}[\forall x\in S,i\subseteq x](\sum_{x\in S}x)^2\end{aligned}$$ 好像并不容易，我们记 $S_i=\{x\in\{a_n\}|i\subseteq x\}$，则 $\displaystyle g(i)=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2$。
  好像还是不容易，但是我们观察到 $x\subseteq y\Rightarrow S_y\subseteq S_x$，这种情况我们就要考虑从 $y$ 合并到 $x$。
  考虑如何合并，假设有两个集合 $S_p,S_q$，满足 $S_p\cap S_q=\arnothing$ 且 $S_p\cup S_q=S_i$，这时我们要将 $S_p,S_q$ 的信息合并到 $S_i$ 上，容易得到：
  $$\begin{aligned}g(i)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)^2\&=\sum_{S\subseteq S_i}((\sum_{x\in S_p\cap S}x)^2+2(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x)+(\sum_{x\in S_q\cap S}x)^2)\&=(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)^2)+2(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x))+(\sum_{S\subseteq S_i}(\sum_{x\in S_q\cap S}x)^2)\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)(\sum_{x\in s_q}x))+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x))+2^{|S_p|}(\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\end{aligned}$$ 这时，我们要维护什么就显而易见了，设：
  $$\begin{aligned}F(i,2)&=g(i)\&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\end{aligned}$$ $$F(i,1)=\sum_{S\subseteq S_i}\sum_{x\in S}x$$ $$\begin{aligned}F(i,0)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^0\&=\sum_{S\subseteq S_i}1\&=2^{|S_i|}\end{aligned}$$ 最终，我们可以得到： $$F(i,2)=F(p,2)F(q,0)+2F(p,1)F(q,1)+F(p,0)F(q,2)$$ 类似地，我们可以得到：
  $$\begin{aligned}F(i,1)&=\sum_{S\subseteq S_i}\sum_{x\in S}x\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)\&=(\sum_{S\subseteq S_i}\sum_{x\in S_p\cap S}x)+(\sum_{S\subseteq S_i}\sum_{x\in S_q\cap S}x)\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_p}x)+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}\sum_{x\in s_p}x)+2^{|S_p|}(\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\&=F(p,1)F(q,0)+F(p,0)F(q,1)\end{aligned}$$ $$F(i,0)=F(p,0)F(q,0)$$ 现在我们得到了 $g(i)=F(i,2)$，要容斥出 $G(i)$，这个就是平凡的高维差分。
  最后计算出答案即可。
  时间复杂度为 $\Theta(n+V\log V)$，空间复杂度为 $\Theta(V)$。