Atcoder Beginner Contest 163 D题题解

本文主要是介绍Atcoder Beginner Contest 163 D题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题题解思路学自这位大佬ABC163(Atcoder beginner contest 163)部分题解 本博客仅用于记录自己学习思路，本质都是大佬的解法。
题目链接abc163_d
题目大意：给出N与K, N代表有N+1个数分别是1e100, 1e100+1,1e100+2,…,1e100+N. K代表任选K，K+1,K+2,N+1个数相加，求不同结果的总数mod 1e9+7的结果。
因为每个数都有远大于N的前缀1e100,所以K+1个数相加的结果一定不同于K+2个数相加即相加的个数不同结果一定不同。所以我们可以分别计算K,K+1,K+2…个数相加的结果总数然后再加起来。
对于结果观察可以发现：所有能够取到的和一定是连续的。列如N=3,K=2
当我们选4个数时，只有一种情况：0+1+2+3=6，sum+=1
选3个数：最大的情况是1+2+3=6,最小情况是0+1+2=3，所以能取到的和为：3,4，5,6。sum+=4
选2个数：最大2+3=5，最小0+1=1，所有和情况：1,2，3,4，5，sum+=5.
所以最终结果为1+4+5=10种。
所以只需要从大到小（n+1~k）跑一遍循环求出等差数列和就行了。

#include<stdio.h>
#define ll long long
ll mod=1e9+7;
int main()
{ll n,k,i,j;ll t,t1,t2,ans=1;scanf("%lld %lld",&n,&k);t=((1+n)*(n)/2);//等差数列和 t1=t2=t;for(i=n,j=0;i>=k;i--,j++)//每次减去最大和最小的，得到的新的max和min的区间长度即为本次循环所求 {t1-=i, t2-=j;ans+=(t2-t1+1);ans%=mod;}printf("%lld",ans);return 0;
}

这篇关于Atcoder Beginner Contest 163 D题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---