D – Sum of Large Numbers

Problem Statement : here

The tricky part is the addition of 10^100. So, let us assume that we are using k numbers to generate our sum. Clearly, in this case, the coefficient of 10^100 will be k. If we would have used k+1 terms, the coefficient would have differed and this makes the two numbers different. So the cases like 1+ 8 = 3+5+1 are not possible, because each of them has different coefficients of 10^100.

So, what we are left with?

 Given k -> number of terms, what are the possible values of the sum I can get? 

So, if I calculate the minimum possible sum and the maximum possible sum, then I claim that we can get any number in between this sum range. It is a well-known fact. So, we use it in order to solve this question. The proof – intuitive that can be taken to convince is :

min-sum  = 0 + 1 + 2 + 3 ………. + k-1

max-sum = n-(k-1) + n-(k-2) + n-(k-3) + ……. + n

To get any sum in this range, we can start distributing the difference between given value and min-sum to 0 (until it becomes n-(k-1)), remaining to 1 and so on up to k-1 (until it becomes n).

ll modp(ll a, ll b){
    ll res = 1;
    while(b>0){
        if (b&1) res = (res*a)%M1;
        a = (a*a)%M1;
        b>>=1;
    }
    return res;
}

ll minsum[200005];
void solve()
{
    ll n,k;
    cin>>n>>k;
    minsum[1] = 0;
    ll maxsum = (((n*(n+1))%M1)*modp(2,M1-2))%M1;
    rep(i,2,n+2){
        minsum[i] = (minsum[i-1] + i-1 + M1)%M1;
    }
    ll ans = 0;
    rep(i,k,n+2){
        ans = (ans + maxsum - minsum[n-i + 1] - minsum[i] + 1 + M1)%M1;
    }
    cout << ans << endl;
    
}

Leave a Reply