Codeforces Round #295 (Div. 1 C / Div. 2 E) - Pluses everywhere

Problem Statement:
521C - Pluses everywhere

Solution:
Let's start from what we know and concretely find out what we don't know.

Let d[1..n] be the digits on the number that is given to us. Focus on d[i..j] for some i, j. We know exactly how many times it will appear by simple combinatorics deduction: there are \(n-1\) spaces to place '+' signs in between d[1], d[2], ..., d[n], but d[i..j] should not have any plus signs inside, which eliminates \(j-i\) candidates to place the sign, and finally we must place a sign right before d[i] and right after d[j], hence eliminating further 2 places, which gives us \( n-1-(j-i)-2 \) places to choose from. Furthermore, since we must use two plus signs to define d[i..j], we are left with k-2 plus signs to place. Hence in total, d[i..j] appears \({{n-1-(j-i)-2} \choose  {k-2}} \) times in the summations. Let's call this value M(i,j), the "multiplier" of d[i..j]. By the way, notice that we may also have cases where \(i = 1\) or \(j = n\) in which we only need to use a sign to define d[i..j], hence the computations will differ slightly, but can be computed precisely.



(For all d[i..j] with i = 1, we say that d[i..j] is a prefix. On the other hand, if j = n, we say that d[i..j] is a suffix.)

Hence the simplest approach would be to iterate through all possible i and j, which gives us an \( O(n^2) \) run time complexity. But we can actually do better by employing some dynamic programming ideas.

Firstly, let's consider all d[i..j] for which their lengths are exactly k. For all such d[i..j] which are not a prefix or a suffix, we actually have M(i,j) the same for all of them. Hence if we can compute the sum of all such d[i..j] efficiently, what we need to do to arrive to the answer is just multiplying the sum with M(i,j).

Let S(k) be the sum of all d[i..j] with length k. We know that :
S(k) = d[1..k] + d[2..k+1] + ... + d[n-k+1 .. n]

But equivalently, We have :
S(k) = ( S(k-1) - d[n-k+2 .. n]  ) * 10 - sum of digits in d[k-1..n].

This allows us to compute all S(k) in O(n) time, instead of \(O(n^2)\) time.

With that, we have a O(n) DP approach to the problem. The implementation requires some manipulations on number theory (using euclid's algorithm for finding inverse modulus of a number) and O(n) implementation of computing the required combinatorial combinations, which can be deciphered in my implementation below.

While the idea to solve the problem is pretty interesting, the overall my overall impression of this problem is of a tedious, error-prone, implementation-heavy problem..

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

long long MOD = (long long) 1e9 + 7LL;

void gcd(long long a, long long b, long long &m, long long &x, long long &y) {
    if(a > b) {
        gcd(b, a, m, y, x);
        return;
    }
    if(a == 0) {
        m = b;
        x = 0;
        y = 1;
        return;
    }
    long long _x, _y;
    gcd(b%a, a, m, _y, _x);
    y = _y;
    x = _x - (b/a) * y;
    x %= MOD;
    y %= MOD;
}

long long inv[100005];
long long fact[100005], inv_fact[100005];
long long S[100005], sum[100005];
int N, K;
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;++i){
        long long m,x,y;
        gcd(i,MOD,m,x,y);
        inv[i] = x;
    }
    fact[N-K-1] = 1LL;
    for(int i=N-K;i<=N-1;++i){
        fact[i] = fact[i-1] * i;
        fact[i] %= MOD;
    }
    inv_fact[0] = 1LL;
    for(int i=1;i<=N;++i){
        inv_fact[i] = inv_fact[i-1] * inv[i];
        inv_fact[i] %= MOD;
    }
    string d;
    cin >> d;
    if( K == 0 ) {
        long long ans = 0;
        for(int i=0;i<N;++i){
            ans *= 10LL;
            ans += d[i] - '0';
            ans %= MOD;
        }
        cout << ans << endl;
        return 0;
    }
    for(int i=0;i<N;++i){
        sum[i] = d[i] - '0';
        if(i > 0) sum[i] += sum[i-1];
        sum[i] %= MOD;
    }
    long long last_term = 0;
    long long pow10 = 1LL;
    for(int i=1;i<=N;++i){
        if(i == 1) {
            S[i] = sum[N-1];
        } else {
            S[i] = ((S[i-1] - last_term) * 10LL)%MOD + sum[N-1] - sum[i-2];
            S[i] %= MOD;
        }
        last_term += (d[N-i] - '0') * pow10;
        last_term %= MOD;
        pow10 *= 10LL;
        pow10 %= MOD;

    }
    long long mult, nmult = (K == 1 ? 1 : fact[N-2] * inv_fact[K-1]);
    long long ans = 0;
    if(K >= 2) mult = ( K == 2 ? 1 : fact[N-3] * inv_fact[K-2]);
    else mult = 0;
    mult %= MOD;
    nmult %= MOD;
    long long suffix = 0, prefix = 0;
    pow10 = 1LL;
    for(int i=1;i<=N-K;++i){
        suffix += (d[N-i] - '0') * pow10;
        prefix *= 10LL;
        prefix += d[i-1] - '0';
        prefix %= MOD;
        suffix %= MOD;
        pow10 *= 10LL;
        pow10 %= MOD;
        ans += ((S[i] - suffix - prefix) * mult)%MOD + ((suffix + prefix) * nmult)%MOD;
        ans %= MOD;

        if(K!=2) mult *= (inv[N-i-2] * (N-i-2-K+2))%MOD;
        if(K!=1) nmult *= (inv[N-i-1] * (N-i-1-K+1))%MOD;
        mult %= MOD; nmult %= MOD;
        if(nmult < 0) nmult += MOD;
    }
    if(ans<0)ans += MOD;
    cout << ans << endl;
    return 0;
}