【题解】CQOI2012局部最小值

　　上课讲的一道题，感觉也挺厉害的~正解是容斥 + 状压dp。首先我们容易发现一共可能的局部最小值数量是十分有限的，最多也只有 \(8\) 个。所以我们可以考虑状压。

　　建立出状态 \(f[i][j]\) 表示我们从小到大往方格当中填数，填完前\(i\) 个数之后，局部最小值的填充状态为 \(j\) 的方案数。这样一共有两种转移：

\(f[i][j] = f[i - 1][j] * (g[j] - ((i - 1) - |j|)) + \sum f[i][j']\)

　　分别表示加入了一个局部最小值 / 其他位置的值。其中的 \(g[j]\) 表示在 \(j\) 的状态下可以放入的非局部最小值的个数。但这样做出来还是不够的——我们虽然保证了要求的位置上一定是局部最小值，但是其余的位置上也有可能是局部最小值，而这是不符合要求的。我们考虑用容斥来处理，用全集 - 至少有一个非局部最小值成为了局部最小值的方案数，+至少两个，-至少三个……

　　每一个dfs出来的状态都用上面的方法dp加入到答案中去就可以了。

#include <bits/stdc++.h>

using namespace std;

#define maxn 400

#define maxm 500

#define int long long

#define mod 12345678

int n, m, N, tot, cnt, ans;

int Map[maxn][maxn], id[maxn][maxn];

int f[maxn][maxm], g[maxm], T;

int dx[] = {-, , , -, , -, , };

int dy[] = {-, -, -, , , , , };

struct node

{

    int x, y;

}P[maxn];

void Up(int& x, int y) { x = (x + y) % mod; }

int DP()

{

    int K = ( << tot) - ;

    for(int k = ; k <= K; k ++)

    {

        g[k] = ; int tem = k, len = ;

        while(tem) len += (tem & ), tem >>= ;

        for(int i = ; i <= n; i ++)

            for(int j = ; j <= m; j ++)

            {

                int flag = ; if(Map[i][j]) continue;

                for(int l = ; l < ; l ++)

                {

                    int x = i + dx[l], y = j + dy[l];

                    if(Map[x][y] && !(( << (id[x][y] - )) & k))

                    { flag = ; break; }

                }

                if(!flag) g[k] ++;

            }

        g[k] += len;

    }

    memset(f, , sizeof(f)); f[][] = ;

    for(int i = ; i <= N; i ++)

        for(int j = ; j <= K; j ++)

        {

            Up(f[i][j], f[i - ][j] * (g[j] - (i - )));

            int tem = j, len = ;

            while(tem) len ++, tem >>= ;

            for(int k = ; k < len; k ++)

                if(j & ( << k)) Up(f[i][j], f[i - ][j ^ ( << k)]);

        }

    return f[N][K];

}

void DFS(int x, int y)

{

    if(y > m) x += , y = ;

    if(x > n)

    {

        if((tot - cnt) & ) ans = (ans - DP() + mod) % mod;

        else ans = (ans + DP()) % mod;

        return;

    }

    DFS(x, y + );

    if(Map[x][y]) return;

    for(int i = ; i < ; i ++)

        if(Map[x + dx[i]][y + dy[i]]) return;

    Map[x][y] = , P[++ tot].x = x, P[tot].y = y; id[x][y] = tot;

    DFS(x, y + );

    tot --, Map[x][y] = , id[x][y] = ;

}

signed main()

{

    scanf("%lld%lld", &n, &m); N = n * m;

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= m; j ++)

        {

            char c; cin >> c;

            if(c == 'X')

            {

                P[++ tot].x = i, P[tot].y = j;

                Map[i][j] = , id[i][j] = tot;

            }

        }

    cnt = tot;

    for(int i = ; i <= tot; i ++)

    {

        T |= ( << (i - ));

        for(int j = ; j < ; j ++)

            if(Map[P[i].x + dx[j]][P[i].y + dy[j]])

            {

                printf("");

                return ;

            }

    }

    DFS(, );

    printf("%lld\n", ans);

    return ;

}

巴特西

【题解】CQOI2012局部最小值

最新文章

热门文章