AtCoder Beginner Contest 163(D)

D - Sum of Large Numbers

题意:题目的大概意思就是存在N+1个数,分别为10100,10100+1,10100+2,10100+3.........10100+N。从中至少选出K个数,求选出的K个数的和总共有多少种。

题解:这一题是一个很好的思维题,你看,选择K数,和选择K+1个数相加的和是绝对不可能相等的。这样,我们就只需要遍历一遍去多少个数就可以了,然后算出当取K个数时,算出和的最小值与最大值,中间的值我们都可以取到。

代码:

#include<iostream>
#define ll long long
using namespace std;
const ll mod=1e9+7;
int main(){
    ll N,K;
    ll ans=0;
    cin>>N>>K;//从[ 0  ~  N] 中选
    ll sum=(1+N)*N/2;//总和 
    for(int i=K;i<=N;i++){//表示取  K  个数 
        //分别求出取 k 个数的最大值、与最小值
        ll t1=(0+i-1)*i/2;//和最小
        ll t2=(N+(N-i+1))*i/2;
        ll max_n=sum-t1;
        ll min_n=sum-t2;
        ans=ans+(max_n-min_n+1)%mod;
    }
    cout<<(ans+1)%mod<<endl;
    return 0;
} 

 

上一篇:算术生成算法——accumulate


下一篇:如何折叠/积累numpy矩阵乘积(点)?