UVALive - 8144 Sacred Scarecrows DP + FMT 未解決

簡略題意： R∗C 的莊稼地，有些地方已經種了莊稼了。現在需要放置一些稻草人，使得滿足以下兩個條件：

1 . 所有行都包含稻草人。

2. 相鄰的兩列至少包含兩個稻草人。

這題目前還沒有 AC ，但是值得記錄。

注意到行很少，是以可以狀壓進行 DP 。

令 dp[i][0/1][j] 代表，前i列的稻草人存放了那些行，目前列是否有稻草人。

用 ∗∗ 代表集合并卷積，那麼轉移有如下：

1.dp[i][0]=dp[i−1][1]∗∗g[0]

2.dp[i][1]=dp[i−1][0]∗∗g/g[0]+dp[i−1][0]∗∗g/g[0]=(dp[i−1][0]+dp[i−1][1])∗∗g/g[0]

障礙物的處理直接把對應卷上的 g 給置零即可，是以可以用FMT來優化到 R∗(2R)∗C 。

經過用 assert 得出測試資料至少有 20 組…上述算法無法通過。

qls給出了如下解法：

對行容斥，可以知道每列有多少空地，然後 O(c) 的 dp .

容斥用 dfs 枚舉集合可以 2r ，可以做到 O(2R∗C) .

暫時還沒太了解，先想一想。

#define others
#ifdef poj
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#endif // poj
#ifdef others
#include <bits/stdc++.h>
#endif // others
//#define file
#define all(x) x.begin(), x.end()
using namespace std;
#define eps 1e-8
const double pi = acos(-);

typedef long long LL;
typedef unsigned long long ULL;
void umax(int &a, int b) {
    a = max(a, b);
}
void umin(int &a, int b) {
    a = min(a, b);
}
int dcmp(double x) {
    return fabs(x) <= eps?:(x > ?:-);
}
void file() {
    freopen("data_in.txt", "r", stdin);
    freopen("data_out.txt", "w", stdout);
}

const LL mod = +;

int r, c, lim;
LL dp[][][], f[], g[], h[];
char G[][];

LL add(LL a, LL b) {
    a += b;
    if(a >= mod) a -= mod;
    return a;
}

LL mul(LL a, LL b) {
    LL sum = l * a * b;
    if(sum >= mod) a %= mod;
    return sum;
}

LL sub(LL a, LL b) {
    a -= b;
    if(a < ) a += mod;
    return a;
}

void FMT(int col, int on) {
    for(int i = ; i < lim; i++) g[i] = ;
    if(on) {
        for(int i = ; i < lim; i++) {
            bool isok = ;
            for(int j = ; j < r; j++) {
                if((i & ( << j)) && G[j][col] == 'v') isok = ;
            }
            if(isok) g[i] = ;
        }
    } else {
        g[] = ;
    }
    for(int i = ; i < r; i++)
        for(int j = ; j < lim; j++)
            if((j >> i) & )
                f[j] = add(f[j], f[j^(<<i)]);
    for(int i = ; i < r; i++)
        for(int j = ; j < lim; j++)
            if((j >> i) & )
                g[j] = add(g[j], g[j^(<<i)]);
    for(int i = ; i < lim; i++)
        h[i] = mul(f[i], g[i]);
    for(int i = ; i < r; i++)
        for(int j = ; j < lim; j++)
            if((j>>i)&)
                h[j] = sub(h[j], h[j^(<<i)]);
}

void cpy(LL x[], LL y[]) {
    for(int i = ; i < lim; i++)
        x[i] = y[i];
}

int main() {
//    file();
int ff = ;
    while(~scanf("%d%d", &r, &c)) {
        ff++;
//    assert(ff <= 30);
        lim =  << r;
        for(int i = ; i < r; i++)
            for(int j = ; j <= c; j++)
                scanf(" %c", &G[i][j]);
        for(int i = ; i < ; i++)
            for(int j = ; j < ; j++)
                for(int k = ; k < lim; k++) dp[i][j][k] = ;
        LL ans = ;
        dp[][][] = ;
        for(int i = ; i <= c; i++) {
            int now = i & , pre = now ^ ;
            for(int j = ; j < lim; j++) dp[now][][j] = dp[now][][j] = ;
            for(int j = ; j < lim; j++)
                dp[now][][j] = dp[pre][][j], dp[pre][][j] = add(dp[pre][][j], dp[pre][][j]);

            cpy(f, dp[pre][]);
            FMT(i, );
            cpy(dp[now][], h);
        }
        cout<<(dp[c&][][(<<r)-] + dp[c&][][(<<r)-])%mod<<'\n';
    }
    return ;
}