自动搬运

查看原文

来自洛谷，原作者为

	Stone_Xz 且怒且悲且狂哉 ，且忘且赶且等待

搬运于2025-08-24 23:01:17，当前版本为作者最后更新于2024-07-21 11:52:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

简要题意

一定要把题读懂，可以结合样例和样例解释。

给定一个 $k$ 进制数的每一位 $a_i$，这个数列中每个子串都可以构成一个新的的 $k$ 进制数，求它们的和。并对 $k$ 进制下的 $20070720$ 取模。输出的也应该是一个 $k$ 进制数。

分析：

• 还原赛时思考过程。

1. 首先，题目中所有的运算都建立在 $k$ 进制下，不方便，所以我们等价转换为先在十进制中进行求和、取模运算，再转换为 $k$ 进制输出。

2. 现在我们思考如何计算这个数列中【每个子串构成的 $k$ 进制数】之和。如果暴力求解，时间复杂度怎么也要到 $\mathcal{O}(n^2)$ 以上。题目中的 $n \le 5 \times 10 ^ 5$，在这个时间内不足以计算每个子串的贡献，我们于是转而研究每一位的贡献。

3. 一个位置能贡献多少个子串呢？每个子串都有起始位置和结束位置，对于每一个位置，它都能作为起点，结束位置可以是它右边的任何一个元素。

4. 就拿样例研究，我们列出以某个位置为起点的所有子串。

$$\begin{array}{cc} 位置 & 1 & 2 & 3 \\ -----------&---&---&---\\ 位置上的数 & 1 & 1 & 0 \\ -----------&---&---&---\\ & 1 & 1 & 0\\ 以此为开头的所有子串 & 11 & 10 \\ （这个位置贡献的子串） &110\\ \end{array} $$

5. 我们发现每个位置贡献的的子串很有规律。要求整个数列中每个子串的和，那么，一个位置贡献的所有子串之和（即这个位置的贡献）是多少呢？让我们试着列出每一个位置的贡献（设第 $i$ 个位置的贡献为 $ans_i$）：

$$\begin{aligned} ans_1 = (a_1 \times k^2 + a_2 \times k^1 + a_3 \times k^0) \\ + (a_1 \times k^1 + a_2 \times k^0)\\ + (a_1 \times k^0)\\ = (110)_2 + (10)_2 + (1)_2 \end{aligned} $$

---

$$\begin{aligned} ans_2 = (a_2 \times k^1 + a_3 \times k^0)\\ + (a_2 \times k^0) \\ = (10)_2 + (1)_2 \end{aligned} $$

---

$$\begin{aligned} ans_3 = (a_3 \times k^0)\\ = (0)_2 \end{aligned} $$

6. 每个位置的贡献很有规律，拿 $ans_1$ 的计算为例，$a_1$ 对 $ans_1$ 的贡献为 $a_1 \times (k^2 + k^1 + k^0)$，$a_2$ 对 $ans_1$ 的贡献为 $a_2 \times (k^1 + k^0)$，$a_3$ 对 $ans_1$ 的贡献为 $a_3 \times k^0$，所以$ans_1$ 的计算可以列为规律更加直观的一个式子：

$$\begin{aligned} ans_1 = {\color{Red}a_1 \times (k^2 + k^1 + k^0)}\\ + {\color{Blue}a_2 \times (k^1 + k^0)}\\ + {\color{Green}a_3 \times k^0} \end{aligned} $$

同理：

$$ans_2 = {\color{Blue}a_2 \times (k^1 + k^0)} + {\color{Green}a_3 \times k^0} $$$$ans_3 = {\color{Green}a_3 \times k^0}$$

7. 我们仍没有足够的时间暴力计算上面所有的式子，但是我们发现这其中有大量的重复，将这些重复合并，可以得到如下答案：

$$\begin{aligned} ans_1 + ans_2 + ans_3 = \\ {\color{Red}a_1 \times (k^2 + k^1 + k^0)} \times 1\\ + {\color{Blue}a_2 \times (k^1 + k^0)} \times 2\\ + {\color{Green}a_3 \times k^0} \times 3 \end{aligned} $$

按照这样的的规律，就可以用 $\mathcal{O}(n)$ 的时间计算答案了！上述式子中的括号部分计算也很简单，只需开一个变量 $pow\_$ 维护 $k$ 的幂，同时维护变量 $haha$ （赛时乱取的变量名...） 累加每个 $k$ 的幂即可（变量名与代码相符）。

ps：注意多组数据，取模一定要取到位！不然可能爆零！ 同时要特判 $ans = 0$ 的情况输出 $0$！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5, mod = 20070720;
int n, k, ans, a[N];

void solve()
{
	ans = 0;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i] %= mod;
	}
	int haha = 1, pow_ = k;
	for(int i = n; i >= 1; i--)
	{
		ans = (ans + a[i] % mod * i % mod * haha) % mod;
		haha = (haha + pow_) % mod;
		pow_ = (pow_ * (k % mod)) % mod;
	}
	if(ans == 0) // 特判 
	{
		cout << "0\n";
		return;
	}
	// 转进制 
	stack<int> stk;
	while(ans != 0)
	{
		stk.push(ans % k);
		ans /= k;
	}
	while(!stk.empty())
	{
		cout << stk.top() << " ";
		stk.pop();
	}
	cout << "\n";
}

signed main()
{
	int T;
	cin >> T;
	while(T--) solve(); 
	return 0;
}

• 彩蛋：在写这篇题解时，连着刷新了两下，第二下时竟然刚好碰上洛谷更新文章编辑界面，真的比之前丝滑 + 好看 + 好用太多了，专栏界面全更新了（喜