JZOJ 6452 小 D 的奶牛

发表于 | 分类于 |

真就 Meet in the Middle \(O(n 2^{n/2})\) 过 \(50\) 啊……

考虑 Meet in the Middle，则一个团的组成，要么全来自前一半，要么全来自后一半，要么分别来自两半并且互相有连边（这不废话）。
状压 DP / 直接 DFS 求出两半内部有哪些状态可以形成团，顺便求出对于前一半的所有状态，后一半中有哪些点与该状态所有点都相连。
然后枚举前一半的状态，考虑后一半的这些点可以构成多少团。

也就是说现在我们需要对后一半的每个状态求出其有多少个子集是团。
然后 FWT/FMT 一下就完事了。
（当时忘了 FWT 临时去学了一下 FMT）

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 50;
const int M = 25;
int n,m,vis;
int lg2[(1 << M) + 5];
long long a[N + 5],ans;
int s[(1 << M) + 5];
int f[(1 << M) + 5],g[(1 << M) + 5];
int main()
{
    freopen("cows.in","r",stdin),freopen("cows.out","w",stdout);
    for(register int i = 2;i < (1 << M);++i)
        lg2[i] = lg2[i >> 1] + 1;
    scanf("%d",&n),m = n / 2;
    if(n == 1)
    {
        puts("2");
        return 0;
    }
    char ch;
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= n;++j)
            scanf(" %c",&ch),a[i] |= (long long)(ch - '0') << j - 1;
    f[0] = 1,s[0] = (1 << n - m) - 1;
    for(register int i = 1,l,st;i < (1 << m);++i)
        l = lowbit(i),st = i ^ l,
        f[i] = f[st] && ((a[lg2[l] + 1] & st) == st),
        s[i] = s[st] & (a[lg2[l] + 1] >> m);
    g[0] = 1;
    for(register int i = 1;i <= n;++i)
        a[i] >>= m;
    for(register int i = 1,l,st;i < (1 << n - m);++i)
        l = lowbit(i),st = i ^ l,
        g[i] = g[st] && ((a[lg2[l] + m + 1] & st) == st);
    for(register int i = 1;i <= n - m;++i)
        for(register int j = 0;j < (1 << n - m);++j)
            !(j & (1 << i - 1)) && g[j] && (g[j | (1 << i - 1)] += g[j]);
    for(register int i = 0;i < (1 << m);++i)
        f[i] && (ans += g[s[i]]);
    printf("%lld\n",ans);
}