正难则反

赛时：一直想着就正着推，正着写，觉得自己能写过来，就硬着头皮去写，去推，但其实他正着是很难很难做出来的，数据在哪摆着。腿了40多分钟，发现正着推，推不出来，只能换个思路，就是题目中说至少k，那么我至多(k-1)这个好像要比这个至少k要好计算。再用没有k的限制一减。好像就能做出来。但是时间到了。

正难则反！正难则反！正难则反！！！。

通过正常一步一步的难计算出，就要转变思路别一直扣，掉进死胡同里，不回头永远出不去。

不考虑k的限制

我们先来看总的也就是不考虑k的限制。我们找到连续相同的将其划分到一组，然后会把这个字符串划分成$x_1,x_2,……x_m$m组，第i组连续字符个数为$x_i$。所以没有k这个限制则会产生
$$ x_1\times x_2 \times ……\times x_m $$
当然别忘了对1e9+7取模。

至多(k-1)个的限制

在之多(k-1)个的限制下，我们知道k是小于2000的，所以我们可以用dp[i+1][j]表示用前i组构造长为j的初始字符串的方案。

初始值dp[0][0]=1空字符串只有1种

假设第i组有$x_i$个字母，枚举第i组的长度$l=[1,x_i]$,问题转化成用前i-1组构造出j-l的方案数。即dp[i][j-l].

累加得：
$$ dp[i+1][j]=\sum^{x_i}_{l=1}dp[i][j-l] $$
注意$j-l>=0$，上式等价于
$$ dp[i+1][j]=\sum^{j-1}_{l=max(j-x_i,0)}dp[i][l] $$
那么我们可以用前缀和来优化$\sum^{j-1}_{l=max(j-x_i,0)}dp[i][l]$这个。用s表示从dp[i]得前缀和。即
$$ dp[i+1][j]=s[j-1]-s[max(j-x_i,0)] $$
最后将dp[m][0]……dp[m][k-1]从结果出减去就行。注意取模操作。

class Solution {
public:
    int possibleStringCount(string word, int k) {
        int n=word.size();
        if(n<k) return 0;//长度一开始就不够
        int mod=1e9+7;
        vector<int> x;//组
        long long ans=1;//记录答案
        int tmp=0;//组号
        for(int i=0;i<n;i++){
            tmp++;
            if(i==n-1||word[i]!=word[i+1]){ //来新的组了(遇到不相同得了)，或者到最后了
                if(x.size() < k ){//长度比k都多后面也不用在进来了，后面重要剪枝
                    x.push_back(tmp);//前一组相同元素数量。
                }
                ans = ans*tmp%mod;
                tmp = 0; //清零
            }
        }
        int m=x.size();
        if(m>=k) {//无论怎么删都会符合至少为k得条件。重要剪枝
            return ans;
        }
        vector<vector<int>> dp(m+1,vector<int>(k,0));
        dp[0][0]=1;
        vector<int> s(k+1);//维护前缀和
        for(int i=0;i<m;i++){
            for(int j=0;j<k;j++){
                s[j+1]=(s[j]+dp[i][j])%mod;//维护前缀和
            }
            for(int j=i+1;j<k;j++){
                dp[i+1][j]=(s[j]-s[max(0,j-x[i])])%mod;
            }
        }
        for(int i=0;i<k;i++){
            ans=(ans-dp[m][i]+mod)%mod;
        }
        return (ans%mod+mod)%mod;
    }
};