`
阿尔萨斯
  • 浏览: 4107234 次
社区版块
存档分类
最新评论

hdu 4810 Wall Painting(组合数学)

 
阅读更多

题目链接:hdu 4810 Wall Painting

题目大意:有以为画家,有n种颜料,给出n种颜料的值。然后在1~n天中,他每天都会选择相应天数的颜料数进行混合,形成新的一种颜料。比如说第2天,他会选择任意两种的颜料混合,得到新的一种颜料(所选的颜料的值全部取亦或后的到的数即为新颜料的值)
然后对应输出每一天有可能合成颜料值的总和。

解题思路:因为要考虑到所有情况,所以暴力枚举选中的颜料是不科学的有木有。
于是将每个数拆分成32位(二进制)的情况。这样对于每个位去考虑。然后枚举1的个数为奇数的情况,注意个数不能大于n和天数,以及选0的个数也不能大于天数。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1005;
const ll MOD = 1e6+3;

int n, k[40];
ll c[N][N], r[N];

void init () {
    for (int i = 0; i < N; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
    }
}

void cal () {
    ll u;
    cin >> u;

    for (int i = 0; i < 32; i++)
        if (u & (1<<i))
            k[i]++;
}

ll Count(int t, int d) {
    ll ans = 0;

    for (int i = 1; i <= t && i <= d; i += 2) {

        if (n - t < d - i)
            continue;

        ans += (c[t][i] * c[n-t][d-i])%MOD;
        ans %= MOD;
    }
    return ans;
}

void solve (int d) {

    ll ans = 0;

    for (int i = 0; i < 32; i++) {
        ans += (Count(k[i], d) * (1<<i))%MOD;
        ans %= MOD;
    }

    r[d] = ans;
}

int main () {
    init();
    while (cin >> n) {

        memset(k, 0, sizeof(k));


        for (int i = 0; i < n; i++)
            cal();

        for (int i = 1; i <= n; i++)
            solve (i);

        for (int i = 1; i < n; i++)
            cout << r[i] << " ";
        cout << r[n] << endl;
    }
    return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics