题解
首先可以想到分组后,去掉两边都填了数的组。
然后就会剩下\((-1,-1)\)和\((-1,x)\)或\((x,-1)\)这两种情况
因为是最小值序列的情况数,我们可以考虑从大到小填数,一个组填完了最小值就是当前填的数
设\(f[i][j][k]\)表示已经填到数\(i\)剩余\(j+k\)个填了一个数的组,其中有\(j\)个组是第一种情况填出来的,\(k\)个是第二种情况来的
分情况转移
如果这个数属于第一种情况,那么可以转移到:
\(f[i][j+1][k]:\)填到一个\((-1,-1)\)中
\(f[i][j-1][k]:\)和之前填了一个数的\((-1,-1)\)完成一组
\(f[i][j][k-1]:\)和\((x,-1)\)完成一组
如果属于第二种情况,那么可以转移到:
\(f[i][j][k+1]:\)不是最小值
\(f[i][j-1][k]:\)是最小值
最后因为\((-1,-1)\)是无序的,所以答案要乘上一个阶乘
Code
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i < 2 * n; i += 2) {
if (a[i] == a[i + 1])
cnt2++;
else {
if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
if (a[i] == -1) cnt1++, flg[a[i + 1]] = 1;
else vis[a[i]] = vis[a[i + 1]] = 1;
}
}
int m = 0;
f[0][0][0] = 1;
for (int i = 2 * n; i >= 1; i--)
if (!vis[i]) {
m++;
if (!flg[i]) {
for (int j = 0; j <= cnt1 + cnt2; j++)
for (int k = 0; k <= cnt1; k++) {
pls(f[m][j + 1][k], f[m - 1][j][k]);
if (j) pls(f[m][j - 1][k], f[m - 1][j][k]);
if (k) pls(f[m][j][k - 1], 1ll * k * f[m - 1][j][k] % Mod);
}
}
else {
for (int j = 0; j <= cnt1 + cnt2; j++)
for (int k = 0; k <= cnt1; k++) {
pls(f[m][j][k + 1], f[m - 1][j][k]);
if (j) pls(f[m][j - 1][k], f[m - 1][j][k]);
}
}
}
int ans = f[m][0][0];
for (int i = 1; i <= cnt2; i++)
ans = 1ll * ans * i % Mod;