解题思路

这是一道规律题，我们可以通过以下方式找到写一道题时间的规律。

对于每道题：

• 写第 \(1\) 行代码的时间 \( t_1 = k \times (s_0 + 1) \)。
• 写第 \(2\) 行代码的时间 \( t_2 = k \times (s_0 + 1 + t_1) = k \times (s_0 + 1 + (k \times (s_0 + 1))) \)。
• 写第 \(3\) 行代码的时间 \( t_3 = k \times (s_0 + 1 + t_1 + t_2) = k \times (s_0 + 1 + k \times (s_0 + 1) + k \times (s_0 + 1 + (k \times (s_0 + 1))) \)。

整理得：

• \( t_1 = ks_0 + k \)。
• \( t_2 = ks_0 + k + k^2s_0 + k^2 \)。
• \( t_3 = ks_0 + k + 2k^2s_0 + 2k^2 + k^3s_0 + k^3 \)。

将 \(s_0\) 提取，得：

• \( t_1 = s_0 \times k + k \)。
• \( t_2 = s_0 \times (k + k^2) + k + k^2 \)
• \( t_3 = s_0 \times (k + 2k^2 + k^3) + k + 2k^2 + k^3 \)。

因式分解得：

• \( t_1 = k \times (s_0 + 1) \)。
• \( t_2 = (k + k^2) \times (s_0 + 1) = k \times (k + 1) \times (s_0 + 1)\)
• \( t_3 = (k + 2k^2 + k^3) \times (s_0 + 1) = k \times (k^2 + 2k + 1) \times (s_0 + 1) = k \times (k + 1)^2 \times (s_0 + 1) \)。

至此，我们大致已经能找到规律，即写第 \(i\) 行代码所需要的时间 \( t_i = k \times (s_0 + 1) \times (k + 1)^{i - 1} \)，容易证明此式正确。

所以，写一道代码行数为 \(h\) 的题目，所需花费的总时间为 \( t = t_1 + t_2 + ... + t_h = k \times (s_0 + 1) \times ((k + 1)^0 + (k + 1)^1 + ... + (k + 1)^{h - 1}) \)，这里，我们称 \(k \times ((k + 1)^0 + (k + 1)^1 + ... + (k + 1)^{h - 1})\) 为这道题的**综合系数**，那么，写某道题所需的时间就为 \((s_0 + 1) \times 综合系数\)。

到这里，大概就很容易能想到将综合系数进行排序，然后取最小的前 \(m\) 道题，最后计算答案。但是出现了一个问题：做不同题目的先后顺序对整体时间是否有影响？以下是这个贪心的证明过程：

• 设两道题的综合系数分别为 \(x, y\)，初始疲倦值是 \(s_0\)。
• 先做第一题时：
  • 做第一题的时间 \(t_1 = x \times (s_0 + 1) = xs_0 + x\)。
  • 做完第一题后的疲倦值 \(s_1 = tx + s_0 = xs_0 + x + s_0\)。
  • 做第二题的时间 \(t_2 = y \times (s_1 + 1) = y \times (xs_0 + x + s_0 + 1) = xys_0 + xy + ys_0 + y\)。
  • 总时间 \(t = t_1 + t_2 = xys_0 + xs_0 + ys_0 + xy + x + y\)。
• 同理，先做第二题时：
  • 做第二题的时间 \(t_2 = y \times (s_0 + 1) = ys_0 + y\)。
  • 做完第二题后的疲倦值 \(s_2 = ty + s_0 = ys_0 + y + s_0\)。
  • 做第一题的时间 \(t_1 = x \times (s_2 + 1) = x \times (ys_0 + y + s_0 + 1) = xys_0 + xy + xs_0 + x\)。
  • 总时间 \(t = t_1 + t_2 = xys_0 + xs_0 + ys_0 + xy + x + y\)。
• 综上，做题顺序对总时间**无影响**。

此外，我们可以发现综合系数中的 \((k + 1)^0 + (k + 1)^1 + ... + (k + 1)^{h - 1}\) 是一个等积数列，因此可以将其化简，以下是化简过程：

• \(k\times\sum\limits_{i=0}^{h-1}(k+1)^i\)

• \(k\times\frac{1-(k+1)^h}{-k}\)

• \(k\times\frac{(k+1)^h-1}{k}\)

• \({(k+1)^h-1}\)

而对于 \((k+1)^h\) 的比较，我们可以利用**换底公式**，从而通过比较指数的大小来比较任意两个综合系数的大小。

sort 排序的时间复杂度为 \(O(n log n)\)，可以通过此题。

标程代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 252949711;
const int maxn = 1e6 + 10;
struct node {
    ll k, h;
};
int n, m;
ll s = 0;
ll k[maxn], h[maxn];
node x[maxn];

ll fast_pow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b != 0) {
        if (b & 1)
            ans = (ans * base) % mod;
        base = (base * base) % mod;
        b >>= 1;
    }
    return ans % mod;
}

bool cmp(node a, node b) {
    long double i, j;
    i = 1.0*a.h*log(a.k + 1);
    j = 1.0*b.h*log(b.k + 1);
    return i < j;
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &k[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &h[i]);
        x[i].k = k[i], x[i].h = h[i];
    }
    sort(x + 1, x + 1 + n, cmp);

    for (int i = 1; i <= m; i++)
        s = (s + (s + 1) * (fast_pow(x[i].k + 1, x[i].h) - 1 + mod)) % mod;
    cout << s << endl;
    return 0;
}

数据生成器代码

本题数据使用 python 生成。

import cyaron

from cyaron import *  # 引入CYaRon的库

_n = ati([100, 1E4, 1E6,  1E6, 1E6])
_m = ati([100, 1E4, 1,    1E6, 1E6])
_k = ati([10,  1,   1E9,  1E9, 1E9])
_h = ati([100, 1E6, 1E18, 1,   1E18])

def run():
    for num in range(0, 5):
        for i in range(0, 3):
            data = IO(file_prefix="writer", data_id=num*3+i+1)
            n = cyaron.randint(1, _n[num])
            m = cyaron.randint(1, min(n,_m[num]))
            k = []
            h = []
            for j in range(0, n):
                k.append(cyaron.randint(1, _k[num]))
                h.append(cyaron.randint(1, _h[num]))
            data.input_writeln(n, m)
            data.input_writeln(k)
            data.input_writeln(h)
            data.output_gen("E:\\MyProblems\\writer\\writer_right\\writer.exe")