AT_abc163_d题解

· · 题解

题意简化

给定一组项数为 n+1 的递增的数，求取 k 个及以上个数之和的可能数。

解法分析

若我们把 10^{100} 看作 0，那么整个数列就是 \left[0,n\right]。

首先，要考虑一个问题：

什么情况下加和会重复？

第一种，选了数量不相同的两组数，但这是不可能的，因为每个数都大于等于 10^{100}，哪怕数量只差一也相差了 10^{100}，并且 n 远小于 10^{100}，所以不用考虑。

第二种，选了相同数量的两组数，那么我们就举例子：

找到规律了！如果选 k 个数，那么答案就是前 k 个数减去后 k 个数再加一。

程序大体思路也就显而易见了：枚举 k，求出选 k 个数时的答案，加上后求余。

代码主体也就长成这个样子：

cin>>n>>k;
for(int i=k;i<=n+1;i++){
    long long tmp=sum/*高斯求和*/(n-i+1,n)-sum(0,i-1)+1;//选i个数时的答案 
    ans=(ans+tmp)%1000000007;
}
cout<<ans;//输出答案

可能有人不知道什么是高斯求和，这里有详细的讲解。公式就是下面这个（首项加末项的和乘项数除以二）

\sum_x^y=\frac{(x+y)\times(y-x+1)}{2}

那么求和部分就是这样：

long long sum(int x,int y){
    return (long long)(x+y)*(y-x+1)/2;//套公式 
}

最后说一句，我比较推荐万能头文件，这样可以省去很多不必要的麻烦。

完整代码

//已通过 
#include<bits/stdc++.h>
//万能头文件 
using namespace std;
int n,k;
long long ans;
long long sum(int x,int y){
    return (long long)(x+y)*(y-x+1)/2;//套公式 
}
int main(){
    cin>>n>>k;
    for(int i=k;i<=n+1;i++){
        long long tmp=sum/*高斯求和*/(n-i+1,n)-sum(0,i-1)+1;//选i个数时的答案 
        ans=(ans+tmp)%1000000007;
    }
    cout<<ans;//输出答案 
    return 0;
}