这个题目和邓老师前几天出的题目差不多...
首先把这个题目分解,分解就是一个1.n长度的数列选k个+2.(不重复)
第一个子问题就是Cn k对吧?用dp表示呢?
首先我定义dp,dp[i][j],i j表示在我选第i个的时候在j的范围的方案数
那么是不是 在我选第i个的时候在j的范围=在我第i个的时候j-1的范围(就是单纯的保存下前面记录的答案而已)+在我第i-1个的时候在j-1的范围（记录上个状态选的j-1的个数啊）;所以方程就是这个dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])；
考虑不重复我们就可以思考重复怎么来的了?是不是我在第i个的时候选了这个字母下次还是选了这个字母这样就来了,这个问题怎么解决呢?第一种解决方案就是从后面选择最后一个这样既记录了所有答案又不会重复,但是这种请大家自己思考...我介绍一种简单的解决方法,这次我选了这个字母对吧,下次我选这个字母的时候-这次选这个字母的方案数是不是就是我现在的方案数了呢?肯定是的啊!dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]-dp[i-1][l-1]);方程就是这个;最后注意下做减法时候的取模~
代码:

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e3+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x){ return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll dp[N][N];//i j表示在我选第i个的时候在j的范围
ll vis[N][300];//标记看我这个
char a[N];
int main()
{
    ll n,k;
    cin>>n>>k;
    scanf("%s",a+1);
    for(ll i=0;i<=n;i++) dp[0][i]=1;
    for(ll i=1;i<=k;i++)
    {
        for(ll j=i;j<=n;j++)
        {
           if(!vis[i][a[j]])   dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mod,vis[i][a[j]]=j;//假如这个字母没选
           else               {ll l=vis[i][a[j]];dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]-dp[i-1][l-1]+mod)%mod;vis[i][a[j]]=j;}//选了就记录值
        }
    }
    cout<<dp[k][n]<<endl;
    return 0;
}