题解 AT4515 【[AGC030F] Permutation and Minimum】

wrpwrp · 2020-10-14 11:06:24 · 题解

我们把位置在(2i - 1, 2i)的两个点叫做一对点。

显然如果这对点两个都被限定了直接丢掉完事。

如果有一个没有被限定就先留下来。

注意到其他的形如(-1, -1)的顺序是可以随便变化的， 所以先不考虑， 最后乘上一个阶乘就可以了。

考虑用f(i, j, k)表示当前填第i个数， 剩下j个(-1, d)对， 这种对是自己搞出来的， 还剩下k个(-1, e)对， 是被限定了的。

从这里可以发现， 我们的i应该从大到小枚举， 这样才可以避免后效性， 否则前面选了一个数， 后面就没法改变这一对的值， 从而出现后效性。

然后就直接分类讨论dp就好了。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define R register
const int N = 600 + 5;
const int P = 1e9 + 7;

inline int read() {
    int x = 0, f = 1; char a = getchar();
    for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
    for(; a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
    return x * f;
}

int n;
int a[N], ok[N], vis[N];
int f[N][N][N];
int S[N];
int tot1 = 0, tot2 = 0;

int main() {
    #ifdef IN
    freopen("a.in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif
    n = read(); n <<= 1;
    for(R int i = 1; i <= n; i ++) a[i] = read();
    for(R int i = 1; i <= n; i += 2) {
        if(a[i] > 0 && a[i + 1] > 0) {
            vis[a[i]] = 1;
            vis[a[i + 1]] = 1;
            continue;
        }
        else {
            if(a[i] == -1 && a[i + 1] == -1) tot1 ++;
            else {
                tot2 ++;
                if(a[i + 1] == -1) ok[a[i]] = 1;
                else ok[a[i + 1]] = 1;      
            }
        }
    }
    int m = 0;
    for(R int i = n; i >= 1; i --) if(vis[i] == 0) S[++ m] = i;
    f[0][0][0] = 1;
    for(R int i = 1; i <= m; i ++) 
        for(R int j = 0; j <= n; j ++)
            for(R int k = 0; k <= n; k ++) {
                if(! ok[S[i]]) {
                    if(j) f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k]) % P;
                    f[i][j][k] = (f[i][j][k] + f[i - 1][j + 1][k]) % P;
                    f[i][j][k] = (f[i][j][k] + 1LL * f[i - 1][j][k + 1] * (k + 1) % P) % P;
                }
                else {
                    f[i][j][k + 1] = (f[i][j][k + 1] + f[i - 1][j][k]) % P;
                    if(j) f[i][j - 1][k] = (f[i][j - 1][k] + f[i - 1][j][k]) % P;
                }
            }
    int ans = f[m][0][0];
    for(R int i = 1; i <= tot1; i ++) ans = 1LL * ans * i % P;
    printf("%d\n", ans);
    return 0;
}