contest11题解

普及组题解

---

D题

有一个数列，你需要修改不超过k个位置的元素使其变成一个等差数列，如果有多种修改方案，选择首项最小的，如果还有多种，选择公差最小的 k <= min(10, n - 2)

很显然，前k + 2个中一定有两个元素是不会被修改的，那么我们枚举这两个是谁，算出公差然后利用没被修改的数推出其他所有的数，找到最优方案即可
代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
long long a[N], b[N], c[N];
int main() {
    int n, K;
    scanf("%d%d", &n, &K);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    long long ret = 1LL << 60, ret2 = 1LL << 60;
    for (int i = 0; i < K + 2; i++) {
        for (int j = i + 1; j < K + 2; j++) {
            // i , j 位置不变
            long long delta = a[j] - a[i];
            if (delta % (j - i) != 0) {
                continue;
            }
            long long d = delta / (j - i);
            memcpy(b, a, sizeof(a));
            int cnt = 0;
            for (int k = i - 1; k >= 0; k--) {
                if (b[k] + d != b[k + 1]) {
                    b[k] = b[k + 1] - d;
                    cnt++;
                }
            }
            for (int k = i + 1; k < n; k++) {
                if (b[k] - d != b[k - 1]) {
                    b[k] = b[k - 1] + d;
                    cnt++;
                }
            }
            if (cnt <= K) {
                if (b[0] < ret) {
                    ret = b[0];
                    ret2 = d;
                    memcpy(c, b, sizeof(b));
                } else if (b[0] == ret) {
                    if (d < ret2) {
                        ret2 = d;
                        memcpy(c, b, sizeof(b));
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%lld ", c[i]);
    }
    return 0;
}

E题

求

$$(\sum_{i=1}^Ni^4\lfloor \frac{N}{i}\rfloor )\%M$$

数据范围

$1 \leq M \leq 10^5$
$1 \le N \le 10^{10}$

解法

这里有一个重要的性质是$\lfloor \frac{N}{i}\rfloor$的不同的取值只有$2*\sqrt{N}$种

证明：当$i < \sqrt N$的时候，显然只有$\sqrt N$种，当$i > \sqrt N$的时候，$N/i<\sqrt N$,因此最多也只有$\sqrt N$种

还有一个重要的观察就是这些不同的值都是连续在一起的，比如$100/i$的值如下：
100 50 33 25 20 16 14 12 11 10 9 8 7 7 6 6 5 5 5 5 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
因此我们可以找到每一段连续值的左端点和右端点，对同一段快速统计四次方和
怎么计算每一段连续值的左端点和右端点呢？
假设$num = \lfloor \frac{n}{i} \rfloor$是某个连续区间的第一个值，那么$j = \lfloor \frac{n}{num}\rfloor = n / (n / i)$就是满足$\lfloor\frac {n }{ j}\rfloor = num$的最后一个位置，
因为$j = n / num >= i$, 而$(j + 1) * num > n$,所以$n / (j + 1) < num$

一段区间的四次方和等于两个前缀的四次方和相减，所以我们就可以利用四次方和公式快速推出一段区间的数的四次方和
但是我们注意到一个信息是答案是需要取模的，而四次方和公式需要除法(除以30)，取模之后的数可能不再被分母整除，这里有一个技巧就是将模数M扩大30倍，这样就可以保证分子取模后仍然能被30整除
也就是$a/b\%c = a\%(b*c) / b$

证明: 设 a / b = k * c + r, 那么a = k * b * c + b * r, 因此a - k * b * c = b * r
左边模b*c之后等价于 a % (b * c) = b * r，因此取模b*c之后的值仍然能被b整除

至此，七窍已经打通，代码实现如下(取模问题WA了好几发TAT)：

#include <bits/stdc++.h>
using namespace std;
int m;
long long get_sum(long long n) {
    long long ret =  n % m * (n + 1) % m * (2 * n + 1) % m * (n % m * n % m * 3 % m + n * 3 % m - 1) ;
    return (ret % m + m ) % m;
}
int main () {
    int t;
    long long n;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%d", &n, &m);
        m *= 30;
        long long ret = 0;
        long long j;
        for (long long i = 1; i <= n; i = j + 1) {
            j = n / (n / i);
            long long value = n / i;
            ret += value * ( (get_sum(j) - get_sum(i - 1)) % m + m ) % m;
            ret %= m;
        }
        ret /= 30;
        printf("%lld\n", ret);
    }
    return 0;
}

知识延伸：平方和公式推导

$(n+1)^3 - n^3 = 3n^2+3n+1$
$n^3 - (n-1)^3 = 3(n-1)^2+3(n-1)+1$
...
$2^3-1^3=3*1^2+3*1+1$

左边 右边分别相加可以得到
$(n+1)^3-1=3*(1^2+2^2+..+n^2) + 3*(1+2+3..+n) + n$
因此平方和=

$$\frac{(n+1)^3-1-n-3*n*(n+1)/2}{3}$$
化简可得
$$\frac{n*(n+1)*(2n+1)}{6}$$

立方和公式推导

同上

四次方和公式推导

同上
公式为

$$\frac{n(n + 1)(2n+1)(3n^2+3n-1)}{30}$$