Cod sursă (job #733526)

#include <stdio.h>
 
const char inputUrl[] = "director.in";
const char outputUrl[] = "director.out";
 
const int MAX = 1e4 + 1;
const int MOD = 1e9 + 7;
 
int S[2][MAX];
int poz[255];
char s[MAX];
int w[MAX];
int n, k;
int ans;
 
void norm(int& X) {
	if(X < 0)
		X += MOD;
	else if(X > MOD)
		X -= MOD;
}
 
void solve() {
	bool id = 0;
	for(int i = 1; i <= n; i++) {
		w[i] = 1;
		S[1][i] = S[1][i - 1] - w[poz[s[i]]] + w[i];
		norm(S[1][i]);
		poz[s[i]] = i;
	}
 
	for(int i = 1; i < k; i++) {
		for(int i = 'a'; i <= 'z'; i++)
			poz[i] = 0;
 
		for(int i = 1; i <= n; i++) {
			w[i] = S[id ^ 1][i - 1];
			S[id][i] = S[id][i - 1] - w[poz[s[i]]] + w[i];
			norm(S[id][i]);
			poz[s[i]] = i;
		}
		id ^= 1;
	}
 
	ans = S[id ^ 1][n];
}
 
void readInput() {
	FILE *fin = fopen(inputUrl, "r");
 
	fscanf(fin, "%d %d\n", &n, &k);
	fscanf(fin, "%s", (s + 1));
 
	fclose(fin);
}
 
void printAns() {
	FILE *fout = fopen(outputUrl, "w");
 
	fprintf(fout, "%d\n", ans);
 
	fclose(fout);
}
 
signed main()
{
	readInput();
	solve();
	printAns();
	return 0;
}