Cod sursă (job #735727)

#include <bits/stdc++.h>
using namespace std;
const int KMAX = 1e4;
const int NMAX = 1e4+2;
const int SIGMA = 26;
const int MOD = 1e9+7;
int n,k,lst[KMAX][SIGMA];
string str;

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

struct MInt{
    int val = 0;

    MInt operator + (const MInt &aux) {
        MInt ans;
        ans.val = (val + aux.val)%MOD;
        return ans;
    }

    MInt operator - (const MInt &aux) {
        MInt ans;
        ans.val = (val - aux.val + MOD)%MOD;
        return ans;
    }

    MInt operator = (int aux) {
        val = aux;
        return *this;
    }
} dp[KMAX][NMAX], zero;

int main()
{
    fin >> n >> k;
    fin >> str;
    str = "$"+str;
    dp[0][0] = 1;
    memset(lst, -1, sizeof(lst));
    for(int i = 1; i <= n; i++){
        int ch = str[i]-'a';
        dp[0][i] = 1;
        for(int len = 1; len <= k && len <= i; len++){
            dp[len][i] = dp[len][i-1] + (dp[len-1][i-1] - (lst[len-1][ch] != -1 ? dp[len-1][lst[len-1][ch]] : zero));
        }
        for(int len = 0; len <= k && len <= i; len++){
            lst[len][ch] = i-1;
        }
    }
    fout << dp[k][n].val;
    return 0;
}