巧妙的转化；f前两维大小开反TLE了一发……
如果一个序列的相邻两项差的绝对值小于等于1，那么我们说这个序列是完美的。
给出一个有序数列A，求有多少种完美序列排序后和数列A相同。
Input
第一行一个数n（<=30000）表示完美序列的长度 第二行n个数，表示数列A（每个数<=10^9，每个数出现次数<=100）
Output
仅包含一个整数，表示可能的方案总数（对1,000,000,007取模）
题目分析
暑假讲过的题，今天第一眼还以为是什么玄妙计数……
因为从左到右构造不现实，于是考虑将数字从小到大构造。这样的好处在于现在插入的$i$只和上一次$i-1$的状态有关系。
$f[i][j][0/1][0/1]$表示处理到第$i$个数，第$i-1$个数两两间存空$j$个，左右两边分别是否有第$i-1$个数。转移的话就是用组合数统计，记得要预处理组合数。
所以总时间复杂度$O(n*4*100)$.
1 #include<bits/stdc++.h> 2 const int MO = 1000000007; 3 const int maxn = 30035; 4 5 int f[maxn][103][3][3]; 6 int fac[103],C[103][103]; 7 int n,m,ans,a[maxn],t[maxn]; 8 9 int read() 10 { 11 char ch = getchar(); 12 int num = 0; 13 for (; !isdigit(ch); ch=getchar()); 14 for (; isdigit(ch); ch=getchar()) 15 num = (num<<1)+(num<<3)+ch-48; 16 return num; 17 } 18 int qmi(int a, int b) 19 { 20 int ret = 1; 21 while (b) 22 { 23 if (b&1) ret = 1ll*ret*a%MO; 24 a = 1ll*a*a%MO, b >>= 1; 25 } 26 return ret; 27 } 28 inline void Add(int &x, int y){x = (x+1ll*y)%MO;} 29 int main() 30 { 31 n = read(), fac[0] = 1; 32 for (int i=1; i<=n; i++) a[i] = read(); 33 for (int i=1; i<=100; i++) fac[i] = 1ll*fac[i-1]*i%MO; 34 for (int i=0; i<=100; i++) 35 for (int j=0; j<=i; j++) 36 C[i][j] = 1ll*fac[i]*qmi(1ll*fac[j]*fac[i-j]%MO, MO-2)%MO; 37 for (int i=1, j=1; i<=n; i++) 38 { 39 while (j<=n&&a[i]==a[j+1]) j++; 40 if (a[i]+1 < a[j+1]){ 41 puts("0"); 42 return 0; 43 } 44 t[++m] = j-i+1, i = j; 45 } 46 f[1][t[1]-1][1][1] = 1; 47 for (int i=1; i<m; i++) 48 for (int j=0; j<t[i]; j++) 49 for (int s1=0; s1<=1; s1++) 50 for (int s2=0; s2<=1; s2++) 51 if (f[i][j][s1][s2]) 52 for (int k=0; k<=j; k++) 53 for (int l1=0; l1<=s1; l1++) 54 for (int l2=0; l2<=s2; l2++) 55 if (k+l1+l2&&t[i+1] >= k+l1+l2) 56 Add(f[i+1][t[i+1]-k-l1-l2][l1][l2], 1ll*f[i][j][s1][s2]*C[j][k]%MO*C[t[i+1]-1][k+l1+l2-1]%MO); 57 for (int i=0; i<=100; i++) 58 for (int j=0; j<=1; j++) 59 for (int k=0; k<=1; k++) 60 Add(ans, f[m][i][j][k]); 61 printf("%d ",ans); 62 return 0; 63 }
END