链接：https://www.nowcoder.com/acm/contest/139/E
来源：牛客网
题目描述
Bobo has a sequence of integers s1, s2, ..., sn where 1 ≤ si ≤ k.
Find out the number of distinct sequences modulo (109+7) after removing exactly m elements.
输入描述:
The input consists of several test cases and is terminated by end-of-file. The first line of each test case contains three integers n, m and k. The second line contains n integers s1, s2, ..., sn.
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
3 2 2 1 2 1 4 2 2 1 2 1 2
输出
复制
2 4
备注:
* 1 ≤ n ≤ 105
* 1 ≤ m ≤ min{n - 1, 10}
* 1 ≤ k ≤ 10
* 1 ≤ si ≤ k
* The sum of n does not exceed 106.
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define ll long long
#define MAX 1000000000
#define ms memset
using namespace std;
const int mod=1e9+7;ll dp[maxn][11];
int a[maxn],nxt[maxn][11];
int n,m,k;
/*
题目大意：给定n个数，要求范围为1到k,删除m个数，
则要求计数出现的不同序列的个数。比赛时感觉这是动态规划，但是计数类型和状态转移性质
的观察还是不熟练。
首先分析计数的性质和特征（感觉有点像拓扑排序的原理），
如果计算好了(i,j),那么计数(i,j)可以累加到什么地方呢，
根据题解，在删除i位置元素的i到下一个同样的元素出现的地方之间的数
时可以构成一个新的序列，这样计数累加性质就出来了
（其实也是看了题解了，自己也没完全明白）。。。
*/int main()
{while(~scanf("%d%d%d",&n,&m,&k)){for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=k;i++) nxt[n][i]=n+1;for(int i=n;i>=1;i--){for(int j=1;j<=k;j++) nxt[i-1][j]=nxt[i][j];nxt[i-1][a[i]]=i;///为什么是这样的填充完毕？///在进入到i时其已经计算好了}memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=0;i<n;i++)for(int j=0;j<=m;j++)for(int l=1;l<=k;l++){int n1=nxt[i][l],n2=n1-i-1;///填充计数的思想，找一种状态的性质，然后从前往后推，推的过程是计数累加的过程if(n2+j<=m) dp[n1][n2+j]=(dp[n1][n2+j] + dp[i][j])%mod;}ll ans=0;for(int j=0;j<=m;j++) ans=(ans+dp[n-j][m-j])%mod;printf("%lld\n",ans);}return 0;
}