题解：P10791 『SpOI - R1』强大到让你们所有人注视

· · 题解

题目传送门

简要题意

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

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

分析：

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

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

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

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

\begin{array}{cc} 位置 & 1 & 2 & 3 \\ -----------&---&---&---\\ 位置上的数 & 1 & 1 & 0 \\ -----------&---&---&---\\ & 1 & 1 & 0\\ 以此为开头的所有子串 & 11 & 10 \\ （这个位置贡献的子串） &110\\ \end{array}
  1. 我们发现每个位置贡献的的子串很有规律。要求整个数列中每个子串的和，那么，一个位置贡献的所有子串之和（即这个位置的贡献）是多少呢？让我们试着列出每一个位置的贡献（设第 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}
  1. 每个位置的贡献很有规律，拿 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}

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

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