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

cff_0102 · 2024-09-29 15:28:38 · 题解

首先显然的我们可以忽略 k，它是多少不影响平均值是不是整数。

长度为 n 的等差数列的平均值为它的和除以 n。设首项为 0（因为它不重要），则等差数列各项之和为 \frac{(0+(n-1)d)\times n}{2}，平均值为其再除以 n，也就是 \frac{(n-1)d}{2}。我们要求它是整数，即 (n-1)d 是偶数。当 d 是偶数则平均数必然是整数；当 d 是奇数时则要求 n 需要是奇数。

不难发现长度为 n 的等差数列的子串包含 1 个长度为 n 的等差数列，2 个长度为 n-1 的等差数列，……，n 个长度为 1 的等差数列。

所以答案应该分类讨论：当 d 是偶数，答案就是 1+2+\dots+n=\frac{n(n+1)}{2}，如果是奇数，则答案为 n+(n-2)+\dots+(n\bmod2)（即，n 个长度为 1 的序列，n-2 个长度为 3 的序列，……），这个等差数列的项数为 \lfloor\frac{n+2}2\rfloor，和即为 \frac{(n+(n\bmod2))\times\lfloor\frac{n+2}2\rfloor}{2}。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--){
        int n,k,d;cin>>n>>k>>d;
        if(d%2==0)cout<<n*(n+1)/2<<endl;
        else{
            cout<<(n+(n%2))*((n+2)/2)/2<<endl;
        }
    }
    return 0;
}