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;
        if (b&1) res = (res*a)%M1;
        a = (a*a)%M1;
    return res;

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

Leave a Reply