题解：P11129 【MX-X5-T1】「GFOI Round 1」Inverted World

· · 题解

借此题介绍一种打在线比赛快速过规律题的技巧。本题解没有严谨证明，想看证明请移步其他题解。

首先写出暴力程序：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int main() {
    int t; cin >> t;
    while(t--) {
        int n,k,d; cin >> n >> k >> d;
        a[1] = k;
        for(int i = 2;i <= n;i++) a[i] = a[i-1] + d;
        ll num = 0;
        for(ll i = 1;i <= n;i++) {
            for(ll j = i;j <= n;j++) {
                ll sum = 0;
                for(int k = i;k <= j;k++) sum += a[k];
                if(sum % (j-i+1) == 0) num++;
            }
        }
        cout << num << endl;
    }
    return 0;
}

此时提交可以获得 28 分的高分。

看部分分：此时 k=1。

那么我们先将所有的 k=1,2,3,\dots 和 n=5,d=1 输入，容易发现 k 的值和答案没有关系。

那么我们接着将 n=1,2,3,4,\dots 和 k=1,d=1 输入，得到如下式子：

1,2,4,6,9,12,\dots

如果你瞪眼能力强，那么应该可以看出答案了。但是，如果没看出来呢？我们可以使用一个在线查询数列的网站 oeis.org，进入后在输入框输入 1,2,4,6,9,12，根据查询结果我们可以得到通项为 ans = \frac{(n+1)^2}{4}，于是我们就可以拿到这档部分分了。此时能拿到 63 分。

那么让我们将这种结论继续扩展：还是用之前的暴力程序，取 n=6,k=1,d=1,2,3,4,\dots 进行求解。可以发现，令 q \in \N，当 d=2q+1 时，答案相同；当 d=2q 时，答案也相同。那么当 d=2q+1 时，显然答案和上面 d=1 时答案相同；于是我们取 d=2,4,6,\dots 求解，这个数列很好瞪出来（看不出来，同理使用 OEIS 即可），通项公式即为 ans=\frac{n(n+1)}{2}。那么我们只需判断一下 d 的奇偶性即可。至此，我们在本题获得了 100 分。

时间复杂度 \Theta(1)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t; cin >> t;
    while(t--) {
        int n,k,d; cin >> n >> k >> d;
        cout << (d % 2 ? 1ll * (n+1) * (n+1) / 4 : 1ll * (n+1) * n / 2) << endl;
    }
    return 0;
}