Cod sursă (job #785619)

#include <fstream>
#include <string>

using namespace std;

ifstream fin("director.in");
ofstream fout("director.out");

const int Nmax = 10005;
const int SIGMA = 26;
const int MOD = 1000000007;

int n, k;
string sir;

/// dp[i][j] = numarul de coduri distincte de i litere care se termina pe pozitia j
/// Stocam doar 2 linii in dp deoarece recurenta depinde doar de rezultatele obtinute cu i-1 litere.

int dp[2][Nmax];
int coduri_terminate_cu_litera[SIGMA];

void citire(){
    fin >> n >> k;
    fin >> sir;

    sir = "." + sir;
}

void preinitializare_dp(){
    for(int i = 1; i <= n; i++){
        dp[1][i] = 1;
    }
}

void resetare_vector_litere(){
    for(int i = 0; i < SIGMA; i++){
        coduri_terminate_cu_litera[i] = 0;
    }
}

void calculare_dp(){
    int nr_coduri;
    bool linie, linie_anterior;

    for(int i = 2; i <= k; i++){
        linie = i & 1;
        linie_anterior = !linie;

        resetare_vector_litere();
        nr_coduri = 0;

        for(int j = i - 1; j <= n; j++){
            dp[linie][j] = nr_coduri;
            nr_coduri = (1LL * nr_coduri - coduri_terminate_cu_litera[sir[j] - 'a'] + dp[linie_anterior][j] + MOD) % MOD;
            coduri_terminate_cu_litera[sir[j] - 'a'] = dp[linie_anterior][j];
        }
    }
}

void calculare_si_afisare_solutie(){
    int sol = 0;
    bool linie;

    linie = k & 1;
    resetare_vector_litere();

    for(int j = 1; j <= n; j++){
        sol = (1LL * sol - coduri_terminate_cu_litera[sir[j] - 'a'] + dp[linie][j] + MOD) % MOD;
        coduri_terminate_cu_litera[sir[j] - 'a'] = dp[linie][j];
    }

    fout << sol;
}

int main(){
    citire();

    preinitializare_dp();
    calculare_dp();

    calculare_si_afisare_solutie();

    return 0;
}