n <= 60w，∑n <= 200w，1s。
解：首先有个全排列 + 树状数组的暴力。
然后有个没有任何规律的状压...首先我想的是按照大小顺序来放数，可以分为确定绝对位置和相对位置两种，但是都不好处理字典序。
然后换个思路一位一位的考虑放哪个数。用一维来记录|i - p| - 逆序对数 * 2，还有一维记录是否紧贴下限，一个二进制数记录之前填了哪些数。
当前填到哪一位可以通过二进制中1的个数统计出来。这样就是一个n2的做法，可以过n <= 14的点，得到24分。
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> const int N = , MO = ; int p[N], n; inline void Add(int &a, const int &b) {
a += b;
while(a >= MO) a -= MO;
while(a < ) a += MO;
return;
} inline void out(int x) {
for(int i = ; i < n; i++) {
printf("%d", (x >> i) & );
}
return;
} namespace Sta {
const int DT = , M = ;
int f[DT * ][M][], cnt[M], pw[M];
inline void prework() {
for(int i = ; i < M; i++) {
cnt[i] = + cnt[i - (i & (-i))];
}
for(int i = ; i < M; i++) {
pw[i] = pw[i >> ] + ;
}
return;
}
inline void solve() {
memset(f, , sizeof(f));
f[DT][][] = ;
/// DP
int lm = ( << n) - , lm2 = n * (n - ) / ; /// lm : 11111111111
for(int s = ; s < lm; s++) {
for(int i = -lm2; i <= lm2; i++) {
/// f[i + DT][s][0/1]
if(!f[i + DT][s][] && !f[i + DT][s][]) continue;
//printf("f %d ", i); out(s); printf(" 0 = %d 1 = %d \n", f[i + DT][s][0], f[i + DT][s][1]);
int t = lm ^ s;
while(t) {
int j = pw[t & (-t)] + , temp = i + std::abs(cnt[s] + - j) - cnt[s >> (j - )] * + DT, t2 = s | ( << (j - ));
/// f[i + DT][s][1] -> f[std::abs(cnt[s] + 1 - j) - cnt[s >> (j - 1)] + DT][s | (1 << (j - 1))][1]
Add(f[temp][t2][1], f[i + DT][s][1]);
//printf("1 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
if(j > p[cnt[s] + ]) {
Add(f[temp][t2][], f[i + DT][s][]);
//printf("0 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
}
else if(j == p[cnt[s] + ]) {
Add(f[temp][t2][], f[i + DT][s][]);
//printf("0 > %d ", temp - DT); out(t2); printf(" 0 = %d\n", f[temp][t2][0]);
}
t ^= << (j - );
}
}
} printf("%d\n", f[DT][lm][]);
return;
}
} int main() {
//printf("%d \n", (sizeof(Sta::f)) / 1048576);
int T;
scanf("%d", &T);
Sta::prework();
while(T--) {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &p[i]);
}
Sta::solve();
}
return ;
}
24分状压
然后我们必须开始找规律了......这里我是完全没思路(太过SB)
冷静分析一波发现，一个合法的排列等价于一个不存在长度为三的下降子序列的排列。
因为如果存在长度为3的下降子序列，那么中间那个元素一定有一次移动不是如它所想的。而不存在的话，我们就可以归纳，冒泡排序每一步都会减少一对逆序对，下降子序列一定不会变长。（全是口胡，意会就行了）
然后有一个44分的状压DP出来了，我没写...
80分nDP，先考虑怎么求答案。枚举哪个位置开始自由，如果在i开始自由的话就要知道后面有多少种填法。所以我们需要一个从当前状态到终态的状态，而不是从初态到当前。
（看题解）发现如果前缀最大值为j，那么当前要么填比j小的最小的，要么填比j大的。因为如果填了比j小的又不是最小的，就会有一个长为3的下降子序列。
然后设f表示还剩i位要填，能填的数中比max(1~i)大的有j个，填满的方案数。
于是有f[i][j] = ∑f[i - 1][k] = f[i][j - 1] + f[i - 1][j]
于是枚举在哪自由，然后把对应的j求出来。每个位置要加上f
注意有两个地方要break，一个是后面没有比max(1~i)大的数了，还有就是当前填了长为3的下降子序列了。
100分：发现f这个东西其实就是格路径方案数......特别注意i < j的时候为0，所以有一条线不能跨过......
组合数学一波，就能O（1）计算f了。然后发现这个东西f不就是f吗？然后就完事了，nlogn。
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> typedef long long LL;
const int N = , MO = ; int p[N], n;
int fac[N << ], inv[N << ], invn[N << ]; inline LL C(int n, int m) {
if(n < || m < || n < m) return ;
return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;
} inline void Add(int &a, const int &b) {
a += b;
while(a >= MO) a -= MO;
while(a < ) a += MO;
return;
} inline void out(int x) {
for(int i = ; i < n; i++) {
printf("%d", (x >> i) & );
}
return;
} namespace Sta {
const int DT = , M = ;
int f[DT * ][M][], cnt[M], pw[M];
inline void prework() {
for(int i = ; i < M; i++) {
cnt[i] = + cnt[i - (i & (-i))];
}
for(int i = ; i < M; i++) {
pw[i] = pw[i >> ] + ;
}
return;
}
inline void solve() {
memset(f, , sizeof(f));
f[DT][][] = ;
/// DP
int lm = ( << n) - , lm2 = n * (n - ) / ; /// lm : 11111111111
for(int s = ; s < lm; s++) {
for(int i = -lm2; i <= lm2; i++) {
/// f[i + DT][s][0/1]
if(!f[i + DT][s][] && !f[i + DT][s][]) continue;
//printf("f %d ", i); out(s); printf(" 0 = %d 1 = %d \n", f[i + DT][s][0], f[i + DT][s][1]);
int t = lm ^ s;
while(t) {
int j = pw[t & (-t)] + , temp = i + std::abs(cnt[s] + - j) - cnt[s >> (j - )] * + DT, t2 = s | ( << (j - ));
/// f[i + DT][s][1] -> f[std::abs(cnt[s] + 1 - j) - cnt[s >> (j - 1)] + DT][s | (1 << (j - 1))][1]
Add(f[temp][t2][1], f[i + DT][s][1]);
//printf("1 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
if(j > p[cnt[s] + ]) {
Add(f[temp][t2][], f[i + DT][s][]);
//printf("0 > %d ", temp - DT); out(t2); printf(" 1 = %d\n", f[temp][t2][1]);
}
else if(j == p[cnt[s] + ]) {
Add(f[temp][t2][], f[i + DT][s][]);
//printf("0 > %d ", temp - DT); out(t2); printf(" 0 = %d\n", f[temp][t2][0]);
}
t ^= << (j - );
}
}
} printf("%d\n", f[DT][lm][]);
return;
}
} namespace Stable { int ta[N]; inline void add(int i) {
for(; i <= n; i += i & (-i)) ta[i]++;
return;
}
inline int ask(int i) {
int ans = ;
for(; i; i -= i & (-i)) {
ans += ta[i];
}
return ans;
}
inline void clear() {
memset(ta + , , n * sizeof(int));
return;
} inline bool check() {
int ans = , cnt = ;
for(int i = n; i >= ; i--) {
cnt += std::abs(i - p[i]);
ans += ask(p[i] - );
add(p[i]);
}
clear();
return cnt == ans * ;
} inline int cal() {
int ans = ;
for(int i = ; i <= n; i++) {
if(p[i] < p[i - ]) ans++;
}
return ans + ;
} inline void work() {
for(n = ; n <= ; n++) {
for(int i = ; i <= n; i++) p[i] = i;
do {
if(check()) {
for(int i = ; i <= n; i++) {
printf("%d ", p[i]);
}
}
else {
printf("ERR : ");
for(int i = ; i <= n; i++) {
printf("%d ", p[i]);
}
}
printf(" cal = %d \n", cal());
} while(std::next_permutation(p + , p + n + ));
getchar();
}
return;
}
} namespace DP {
const int M = ;
int f[M][M], ta[N];
inline void add(int i) {
for(; i <= n; i += i & (-i)) ta[i]++;
return;
}
inline int ask(int i) {
int ans = ;
for(; i; i -= i & (-i)) {
ans += ta[i];
}
return ans;
}
inline int getSum(int l, int r) {
return ask(r) - ask(l - );
}
inline int F(int i, int j) {
if(i < j) return ;
return (C(i + j - , j) - C(i + j - , i + ) + MO) % MO;
}
inline void solve() {
/*memset(f, 0, sizeof(f));
f[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= i; j++) {
f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MO;
}
}*/ /*for(int j = n; j >= 0; j--) {
for(int i = 0; i <= n; i++) {
printf("%3d ", f[i][j]);
}
puts("");
}*/ int ans = , pre = ;
for(int i = ; i < n; i++) {
/// [1, i - 1] == i >
pre = std::max(pre, p[i]);
int k = n - pre - getSum(pre + , n);
//printf("i = %d k = %d \n", i, k);
if(!k) break;
/*for(int j = 0; j < k; j++) {
Add(ans, F(n - i, j));
//printf("add f %d %d \n", n - i, j);
}*/
Add(ans, F(n - i + , k - ));
add(p[i]);
if(p[i] < pre && ask(p[i]) != p[i]) break;
}
printf("%d\n", ans);
memset(ta + , , n * sizeof(int));
return;
}
} int main() {
//printf("%d \n", (sizeof(Sta::f)) / 1048576);
//Stable::work();
fac[] = inv[] = invn[] = ;
fac[] = inv[] = invn[] = ;
for(int i = ; i < N * ; i++) {
fac[i] = 1ll * fac[i - ] * i % MO;
inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;
invn[i] = 1ll * invn[i - ] * inv[i] % MO;
}
int T;
scanf("%d", &T);
//Sta::prework();
while(T--) {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &p[i]);
}
DP::solve();
}
return ;
}
AC代码