D - Sum of Large Numbers
Problem Statement : here
Solution -
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).
The code :
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;
}
