本文共 2480 字，大约阅读时间需要 8 分钟。

���������������

������DP���������

������������������������dp

������������������������������\(f[i][j] = f[i - 1][j - 1] + dp[i - 1][j]\)

���������������i���������j������������������i-1���������������j-1���������������i���������������������������i-1������������j���������������i���������

���������������������������������������������������������(���������������������������������������������������������������������������������)

������������������������1���4���7���8���5���1������������������1���4���7���8���5 ���������4���7���8���5���1 ������������������������

���������������������������������������������������1���������������������������������������1 4 7 8 5 1������������1 4 7 8 5 ������4 7 8 5 1

������ \(last[i]\) ��������������������� \(a[i]\) ���������������������������

������������������������������������������������������������������������������������������������������i-last[i]������������������������last[i]-1������������������������������������������������

// RioTian 21/05/11#include 
   
    using namespace std;using ll     = long long;const ll mod = 1e9 + 7;int n, m, k;ll dp[1 << 17][11];ll a[1 << 17], c[1 << 17], last[1 << 17];void solve() {    memset(last, 0, sizeof last);    memset(c, 0, sizeof c);    for (int i = 1; i <= n; i++) {        cin >> a[i];        last[i] = c[a[i]]; //������������������������������������������������        c[a[i]] = i;       //������a[i]������������    }    for (int i = 0; i <= n; i++) dp[i][i] = dp[i][0] = 1; //������������i���������i���������i���������0���������������    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= min(i - 1, m); j++) {            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;                         //������            if (last[i] != 0 && i - last[i] <= j) {                                     //������������������a[i]��������������� ���������������������������������                dp[i][j] = (dp[i][j] - dp[last[i] - 1][j - (i - last[i])] + mod) % mod; //������            }        }    }    cout << dp[n][m] << endl;}int main() {    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);    while (cin >> n >> m >> k) solve();    return 0;}