我计划预习五个小时离散，然后hmc补了这道他自认为非常的裸并且很傻逼自己可以一眼秒的简单题，然后给我讲了讲，然后我失去了一整晚的生命迹象。
首先我们可以发现一个神奇的现象，啊，先排个序，然后我们会发现，一个数 是 合法的(指左边的全部小于等于它，右边的全部大于等于它)，当且仅当它在自己拍完序的位置上。
先不考虑很多相同的。 所以我们可以怎么做呢。从左到右枚举每个 合法的数，然后从左到右 枚举 起点。这样考虑，用dp[n]表示 从 1到 n ，n是合法的数的时候的方案数，ans[n]表示从1到n ， 不合法的方案数。 c[n] 表示从 1 到 n 的 排列总数。 显然 。。。好难描述。
唔，显然我们这样枚举会有很多重复的情况对吧。 艹，我先把hmc讲给我我听懂了的复述一下，一个数是 合法的 方案数， 就是 它左边的数xjb排和右边的数xjb排然后乘起来吧。
好啊其实我觉得他就说了这一局有用的。
所以我们可以采用 总排列数-所有合法情况。然后合法情况会有重复的，这个时候就要进行类似容斥的操作对不对。ex： 1,2 1,2；被计算了两次
所以我们可以 计算出 左边 不合法的 方案数。 用不合法的 再去乘 右边合法的 就一定不会和 之前的重复了，因为之前计算的是左边的合法的。
那么首先我们要知道每个子区间的排列总数，可以边计算顺便枚举，也可以先预处理出来。我比较傻逼混在一起就神志不清了就预处理出来的。
然后我们用 ans[i] 表示 到i 为止 的答案， dp[i]表示到 i为止 合法的 方案数。
第一层枚举 现在的区间 ，[1,i]； 第二层枚举 子区间, j from 1 to i ;
然后维护就好了。
emmm你要是不知道费马小定理的话，，，我也木有办法 也可以用递推式求对不对。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod = 1e9+9; 5 const int N = 5005; 6 ll inv[N]; 7 ll n,c[N][N],a[N]; 8 ll qpow(ll a,ll x){ 9 ll res = 1; 10 while (x){ 11 if(x&1) 12 res=res*a%mod; 13 a=a*a%mod; 14 x>>=1; 15 } 16 return res; 17 } 18 void init(){ 19 inv[1]=1; 20 for(int i=2;i<=5000;i++) 21 inv[i]=qpow(i,mod-2); 22 } 23 void slove(int n){ 24 map<int,int> mp; 25 for(int i=1;i<=n;i++){ 26 c[i][i-1]=1; 27 mp.clear(); 28 for(int j=i;j<=n;j++){ 29 c[i][j]=c[i][j-1]*(j-i+1)%mod*inv[++mp[a[j]]]%mod; 30 } 31 c[i+1][i]=1; 32 } 33 } 34 ll dp[N],ans[N]; 35 int main(){ 36 init(); 37 ios::sync_with_stdio(false); 38 cin>>n; 39 for(int i=1;i<=n;i++){ 40 cin>>a[i]; 41 } 42 sort(a+1,a+1+n); 43 slove(n); 44 ans[0]=1; 45 for(int i=1;i<=n;i++){ 46 for(int j=1;j<=i;j++){ 47 dp[i]=(dp[i]+ans[j-1]*c[j+1][i])%mod; 48 } 49 //cout<<dp[i]<<' '; 50 ans[i]=(c[1][i]-dp[i]+mod)%mod; 51 //cout<<ans[i]<<endl; 52 } 53 cout<<ans[n]<<endl; 54 }