• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

CF 662C Binary Table

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

用FWT优化计算。

首先发现行数很小,想到一个暴力的方法,就是以一个二进制位$0$表示这一行不翻转而二进制位$1$表示这一行翻转,然后$2^n$枚举出所有行的翻转情况,再$O(m)$计算所有的结果。

用$a_i$表示第$i$列的原来的情况,有计算式:

$$ans_s = \sum_{i = 1}^{m}(a_i \oplus s) * min(bit_{a_i \oplus  s}, n - bit_{a_i \oplus s})$$

这里的$bit_i$表示$i$的二进制表示中$1$的个数。

记$f_i = min(bit_i, n - bit_i)$,

稍微变形一下

$$ans_s = \sum_{i = 0}^{2^n - 1}cnt_i * f_{i \oplus s}$$

这里$cnt_i$表示原来的序列中状态为$i$的方案数。

因为$i \oplus (i \oplus s) = i$

所以有$$ans_ s = \sum_{i \oplus j == s} cnt_i * f_j$$

然后就变成$FWT$的模板题了。

时间复杂度$O(2^nlog(2^n)) = O(n2^n)$。

Code

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = (1 << 20) + 5;
const ll inf = 1LL << 60;

int n, m, a[N];
ll cnt[N], f[N];

template <typename T>
inline void chkMin(T &x, T y) {
    if (y < x) x = y;
}

void fwt(ll *c, int len) {
    if (len == 1) return;
    int mid = len >> 1;
    fwt(c, mid), fwt(c + mid, mid);
    for (int i = 0; i < mid; i++) {
        ll x = c[i], y = c[i + mid];
        c[i] = x + y, c[i + mid] = x - y;
    }
}

void ifwt(ll *c, int len) {
    if (len == 1) return;
    int mid = len >> 1;
    for (int i = 0; i < mid; i++) {
        ll x = c[i], y = c[i + mid];
        c[i] = (x + y) / 2, c[i + mid] = (x - y) / 2;
    }
    ifwt(c, mid), ifwt(c + mid, mid);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        char s[N];
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++) a[j] |= ((s[j] - '0') << (i - 1));
    }
    for (int i = 1; i <= m; i++) ++cnt[a[i]];
    for (int i = 0; i < (1 << n); i++) f[i] = f[i >> 1] + (i & 1);
    for (int i = 0; i < (1 << n); i++) chkMin(f[i], n - f[i]);
    
    fwt(cnt, (1 << n)), fwt(f, (1 << n));
    for (int i = 0; i < (1 << n); i++) f[i] = f[i] * cnt[i];
    ifwt(f, (1 << n));
    
    ll ans = inf;
    for (int i = 0; i < (1 << n); i++) chkMin(ans, f[i]);
    printf("%lld\n", ans);
    
    return 0;
}
View Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#中的Dictionary字典类介绍发布时间:2022-07-13
下一篇:
C#Winform动态添加菜单(转)发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap