题目链接：这里
题意：现在给你n，k和长度为m的串。你需要构造一个长度为n+m的串，使得其中不同的子序列最多，输出数量。
解法：贪心， dp, 构造。
首先先看给定的字符串t，要解决的第一个问题是要如何求字符串t中不相同的子串数量。

这一步可以dp来做，用dp[i]表示位置i之前的子串数量，假设当前已经考虑到了第i个位置，也就是说之前的dp[0]~dp[i-1]已经求了出来，

再用pos[j]表示字符j上次出现的位置

对于当前位置i来说，因为比上一次多了一个字符，所以会增加dp[I-1]个以当前字符结尾的新子串，但是这些子串中有重复的，也就是以当前字符上次位置作为结束位置的子串数量。

所以可以得到转移方程dp[I] = dp[I-1] * 2 - dp[ pos[t[I] - 1] ];

接下来是后面那部分怎么办？

膜拜大神orzzz

//CF 655E

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000010;
const int mod = 1e9+7;
long long dp[maxn];
int pos[30];
char t[maxn];
int n, k;
int main(){
    scanf("%d%d%s", &n, &k, t+1);
    int len = strlen(t+1);
    dp[0] = 1;
    for(int i = 1; i <= len; i++){
        dp[i] = (dp[i-1])*2;
        if(pos[t[i]-'a']>0) dp[i] -= dp[pos[t[i]-'a'] - 1];
        dp[i] %= mod;
        pos[t[i]-'a'] = i;
    }
    for(int i = len+1; i <= len+n; i++){
        dp[i] = dp[i-1]*2;
        int id, p = i;
        for(int j = 0; j < k; j++){
            if(pos[j] < p){
                p = pos[j];
                id = j;
            }
        }
        if(p > 0) dp[i] -= dp[p-1];
        dp[i] %= mod;
        pos[id] = i;
    }
    printf("%d\n", (dp[len+n]%mod+mod)%mod);
    return 0;
}