BZOJ 3198 - [Sdoi2013]spring

#容斥原理 #Hash

Published on 2016-06-12

描述

济南，中国环渤海地区南翼和黄河中下游地区中心城市，山东省省会，山东省第一大城市，山东省政治、文化、教育中心，华东五大城市之一，区域性金融中心，副省级城市。济南位于山东省中西部，北临黄河，南依泰山。济南分别与西南部的聊城、北部的德州和滨州、东部的淄博、南部的莱芜和泰安交界。济南有着 2700 余年的历史，是龙山文化的发祥地。因境内有“七十二名泉”故被称为“泉城”，并素有“四面荷花三面柳，一城山色半城湖”的美誉。济南历史上涌现了很多文人墨客，著名有李清照、辛弃疾等。济南是国家创新型城市、中国软件名城、全国重要的交通枢纽和物流中心。继济南全运会取得圆满成功后，2013 年济南将举办第十届中国艺术节，并成为 2015 年“第二十二届国际历史科学大会”的主办城市，为济南建设国际大都市注入了新的活力。
济南市“泉历史研究小组”依据济南特有的泉脉关系将济南的泉水分为六个区域，分别是市中区、历下区、天桥区、槐荫区、历城区、长清区。
作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上 $n$ 个不同年份时不同泉区的泉水流量指数，这个指数是一个小于 $2^{30}$ 的非负整数。第 $i$ 个年份时六个泉区的泉水流量指数分别为 $A(i,1), A(i,2), A(i,3), A(i,4),A(i,5), A(i,6)$ 。

现在铭铭希望知道有多少对不同的年份： $i$ 和 $j$ ，满足这两年恰好有 $K$ 个泉区的泉水流量指数对应相同。

分析

不妨设 $f_k$ 为正好有 $k$ 个位置的相同的年份对数量。
则 $f_6$ 可以通过对 6 元组哈希，用排序／哈希表来计算相同的年份对数量。不难发现， $f_6$ 算出来是不重不漏的。
那 $f_5$ 怎么算呢？我们先枚举 $s$ 且 $\vert s\vert = 5$ 表示枚举哪 5 个位置相等，然后在分别对 $s$ 用排序／哈希表来计算相同的年份对数量，累加进 $f_5$ 。可以发现，如果一个年份对只有 5 个位置相等，它只会被算 1 次，否则有 6 个位置相等，会被算 $\binom 6 5 = 6$ 次，所以我们需要在 $f_5$ 中减去 $f_6 * \binom 6 5$ 以得到正确的答案。

不难推算出一般的形式，在枚举累加完之后，有：

f_i = f_i - \sum_{i + 1\le j \le 6}f_j\binom j i

表示减去多余 $i$ 个位置相等的年份对对 $f_i$ 的影响。

如果采用快速排序实现，复杂度为： $O(2^6n\log n)$ ，如果采用哈希表实现，复杂度为： $O(2^6n)$ 。
实测采用哈希表比采用快速排序快一倍左右。

对于网上 $ans = \sum_{k\le i \le n}f_i\times \binom i k \times (-1)^{(i-k)}$ ，实际上就是在一口气一起算 $f_k$ ，跟我的解法思路还是一致的。

总结：
为什么想不到：光想着集合容斥去了，没想到这样递推着计数。
出题人的出题意图：想考这样带组合的容斥。
收获：对计数问题的考虑不能太死板，要多种途径一起考虑。

代码

//  Created by Sengxian on 6/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3198 容斥原理 + Hash
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int C[7][7] = {
    {1, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0}, {1, 2, 1, 0, 0, 0, 0},
    {1, 3, 3, 1, 0, 0, 0}, {1, 4, 6, 4, 1, 0, 0}, {1, 5, 10, 10, 5, 1, 0},
    {1, 6, 15, 20, 15, 6, 1},
};

const int maxn = 100000 + 3, hashBase = 666667, maxk = 6;
int val[maxn][maxk], n, k;
ll f[maxk + 1];

namespace hash_table {
    static const int modu = 100007;
    struct list *pit;
    struct list {
        list *next;
        ull hashVal;
        int cnt;
        void* operator new(size_t) {return pit++;}
        list(list *next = NULL, ull hashVal = 0, int cnt = 0): next(next), hashVal(hashVal), cnt(cnt) {}
    }*first[modu], pool[maxn];
    int timestamp = 0, times[modu];
    inline void init() {
        timestamp++, pit = pool;
    }
    inline int& insert(ull hashVal) {
        int pos = hashVal % modu;
        if (times[pos] != timestamp) first[pos] = NULL, times[pos] = timestamp;
        for (list *cur = first[pos]; cur != NULL; cur = cur->next)
            if (cur->hashVal == hashVal) return cur->cnt;
        first[pos] = new list(first[pos], hashVal, 0);
        return first[pos]->cnt;
    }
}

using namespace std;

ll solve(int s) {
    using namespace hash_table;
    init();
    ll now = 0;
    for (int j = 0; j < n; ++j) {
        ll hashVal = 0;
        for (int i = 0; i < maxk; ++i) if ((s >> i) & 1)
            hashVal = hashVal * hashBase + val[j][i] + 1;
        int &cur = insert(hashVal);
        now += cur++;
    }
    return now;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    memset(hash_table::first, 0, sizeof hash_table::first);
    n = ReadInt(), k = ReadInt();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < maxk; ++j)
            val[i][j] = ReadInt();
    ll ans = 0;
    for (int i = 0, d; i < (1 << maxk); ++i) if ((d = __builtin_popcount(i)) >= k) f[d] += solve(i);
    for (int i = maxk - 1; i >= k; --i)
        for (int j = i + 1; j <= maxk; ++j)
            f[i] -= f[j] * C[j][i];
    printf("%lld\n", f[k]);
    return 0;
}

BZOJ 2669 - [cqoi2012]局部极小值 BZOJ 1853 - [Scoi2010]幸运数字

Sengxian's Blog

BZOJ 3198 - [Sdoi2013]spring

描述

分析

代码