A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2669: [cqoi2012]局部极小值 状压dp+容斥原理
发表于: | 分类: Oi | 评论:0 | 阅读:72

这题666

看到什么最小最大八成就是枚举最小值枚举最大值,这题显然是从小到大填,然后注意到最多有8个最小值所以显然是可以$f(i,sta)$状压dp的

如果写到这你就结束了然后过了样例然后get Wa……

考虑你这么做只让X是局部最小值然后没让.不是局部最小值所以GG了

我当时想到这里然后不知道怎么做然后看了大爷题解


正解其实非常傻逼qwq……

直接枚举额外多出一个局部最大值方案数然后减两个的加三个的……

暴搜所有情况容斥就行了

复杂度是$O(跑的过)$

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int Maxm = (1<<8)+5;
const int mod = 12345678;
const int dx[] = {-1,-1,-1,0,0,1,1,1,0};
const int dy[] = {-1,0,1,-1,1,-1,0,1,0};
typedef long long LL;
#define fir first
#define sec second
int n, m, ans;
char str[10][10];
pair <int,int> stack[10];
int top, cnt[Maxm], F[30][Maxm];

inline int calc() {
    memset(F, 0, sizeof F);
    memset(cnt, 0, sizeof cnt);
    int top = 0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(str[i][j] == 'X') {
                stack[++top] = make_pair(i,j);
            }
        }
    }
    int Max = (1 << top) - 1;
    bool vis[10][10] = {};
    for(int sta = 0; sta <= Max; ++ sta) {
        memset(vis, false,sizeof vis);
        for(int i=1;i<=top;++i) {
            if(((1<<(i-1))&sta) == 0) {
                vis[stack[i].fir][stack[i].sec] = 1;
            }
        }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=m;++j) {
                bool flag = true;
                for(int k=0;k<9;++k) {
                    if(vis[i+dx[k]][j+dy[k]]) {
                        flag = false;
                        break;
                    }
                }
                if(flag) cnt[sta] ++;
            }
        }
    }
    F[0][0] = 1;
    for(int i=1;i<=n*m;++i) {
        for(int sta = 0 ; sta <= Max; ++ sta) {
            (F[i][sta] += (LL) F[i-1][sta] * max(cnt[sta]-i+1, 0) % mod) %= mod;
            for(int j=1;j<=top;++j) {
                if(sta & (1<<(j-1))) {
                    (F[i][sta] += F[i-1][sta-(1<<(j-1))]) %= mod;
                }
            }
        }
    }
    return F[n*m][Max];
}

inline void DFS(int x,int y,int cnt) {
    if(y == m + 1) {
        DFS(x+1,1,cnt);
        return;
    }
    if(x == n + 1) {
        (ans += calc() * (cnt & 1 ? (-1) : 1)) %= mod;
        return;
    }
    DFS(x, y+1, cnt);
    bool flag = true;
    for(int i=0;i<9;++i) {
        if(str[x+dx[i]][y+dy[i]] == 'X') flag = false;
    }
    if(flag) {
        str[x][y] = 'X';
        DFS(x,y+1,cnt+1);
        str[x][y] = '.';
    }
}

int main() {
//  freopen("tt.in","r",stdin);
    cin >> n >> m;
    for(int i=1;i<=n;++i) scanf("%s", str[i]+1);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(str[i][j] == 'X') {
                for(int k=0;k<8;++k) {
                    if(str[i+dx[k]][j+dy[k]]=='X') return 0*puts("0");
                }
            }
        }
    }
    DFS(1,1,0);
    cout << (ans % mod + mod) % mod << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP