solution
用表示前个元素,删掉了,所能得到的不同序列的数量。
如果先不考虑不同序列的话,那么就有。也就是种方案。然后考虑减去不合法的方案。
对于一个位置,如果上一个和相等的位置为,那么以结尾的每个序列,都可以通过删掉这个区间变成以结尾的序列。这显然是重复的,所以只要让就行了。
code
/* * @Author: wxyww * @Date: 2020-04-24 18:48:43 * @Last Modified time: 2020-04-24 18:59:03 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 100010,mod = 1e9 + 7; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int f[N][12],lst[13]; int main() { int n,m,k; while(~scanf("%d%d%d",&n,&m,&k)) { for(int i = 0;i <= k;++i) lst[i] = 0; f[0][0] = 1; for(int i = 1;i <= n;++i) { int x = read(); f[i][0] = 1; for(int j = 1;j <= min(m,i);++j) { f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod; if(lst[x] && (i - lst[x] <= j)) { f[i][j] -= f[lst[x] - 1][j - (i - lst[x])]; f[i][j] %= mod; } } lst[x] = i; } cout<<(f[n][m] + mod) % mod<<endl; } return 0; }