C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 20116K, 提交时间: 2019-12-11 22:33:45

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans,n,m,p=1e9+9,jc[2010],ny[2010],a[2010],b[1301][1301],g[1301][1301],f[1301];
ll ksm(ll x,ll y){
	ll xlh=1;
	while(y){
		if(y&1)xlh=xlh*x%p;
		x=x*x%p;
		y/=2;
	}
	return xlh;
}
int main(){
	ll i,j;
	scanf("%lld%lld",&n,&m);
	jc[0]=ny[0]=1;
	for(i=1;i<=n;i++)jc[i]=jc[i-1]*i%p,ny[i]=ksm(jc[i],p-2);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
	g[a[1]][1]=1;f[1]=1;b[1][1]=1;
	ans=(ans+b[1][m]*jc[n-1])%p;
	for(i=2;i<=n;i++){
		for(j=1;j<i;j++){
			b[i][j+1]=(b[i][j+1]+f[j]*jc[i-2]%p)%p;
			b[i][j+1]=(b[i][j+1]-g[a[i]][j]*jc[i-2]%p+p+g[a[i]][j+1]*jc[i-2]%p)%p;
	   }
	   b[i][1]=g[a[i]][1]*jc[i-2]%p;
	   for(j=1;j<=i;j++)f[j]=(f[j]+b[i][j]*ny[i-1]%p)%p,g[a[i]][j]=(g[a[i]][j]+b[i][j]*ny[i-1]%p)%p;
	   ans=(ans+b[i][m]*jc[n-1]%p*ny[i-1])%p;
	   //printf("%lld\n",ans);
	}
	printf("%lld",ans);
}