您當前位置：首頁 > php開源 > php教程 > HDU 4810 Wall Painting（組合數學 + 位運算）——2013ACM/ICPC亞洲區南京站現場賽

HDU 4810 Wall Painting（組合數學 + 位運算）——2013ACM/ICPC亞洲區南京站現場賽

來源：程序員人生發布時間：2016-11-17 09:26:56 閱讀次數：3157次

傳送門

Wall Painting

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2627 Accepted Submission(s): 839

Problem Description

Ms.Fang loves painting very much. She paints GFW(Great Funny Wall) every day. Every day before painting, she produces a wonderful color of pigments by mixing water and some bags of pigments. On the K-th day, she will select K specific bags of pigments and mix them to get a color of pigments which she will use that day. When she mixes a bag of pigments with color A and a bag of pigments with color B, she will get pigments with color A xor B.
When she mixes two bags of pigments with the same color, she will get color zero for some strange reasons. Now, her husband Mr.Fang has no idea about which K bags of pigments Ms.Fang will select on the K-th day. He wonders the sum of the colors Ms.Fang will get with

different plans.

For example, assume n = 3, K = 2 and three bags of pigments with color 2, 1, 2. She can get color 3, 3, 0 with 3 different plans. In this instance, the answer Mr.Fang wants to get on the second day is 3 + 3 + 0 = 6.
Mr.Fang is so busy that he doesn’t want to spend too much time on it. Can you help him?
You should tell Mr.Fang the answer from the first day to the n-th day.

Input

There are several test cases, please process till EOF.
For each test case, the first line contains a single integer N(1 <= N <= 10³).The second line contains N integers. The i-th integer represents the color of the pigments in the i-th bag.

Output

For each test case, output N integers in a line representing the answers(mod 10⁶ +3) from the first day to the n-th day.

Sample Input

4 

1 2 10 1

Sample Output

14 36 30 8

題目大意：

給定 n 個數，求任意 ∑ni=1C(n,i) 個數的異或和。

解題思路：

首先將每個數的2進制求出來，在每位2進制數中求出 1 的個數，拿樣例來講吧。

1  =  0   0   0   1
2  =  0   0   1   0
10=  1   0   1   0
1  =  0   0   0   1

每次選奇數個 1 和剩余的選的個數⑴ 個 0，比如說求任意兩個數的異或和，那末我們選 1 個 1 ，選 2?1 個 0，我們肯定選

奇數個 1，由于偶數個 1 異或還是 0 沒成心義，然后就是組合數了，從當前的 1 的總個數里面選擇奇數個 1 ,在乘以相應的 2x

次冪，(c[cnt[j]][k]?c[(n?cnt[j])][i?k])?(2j)其中 cnt[j] 表示的是第 j 位 1 的總個數， k 表示的是要選擇的 1 的個數。i 表示的

是任意 i 個數異或。。。大體上看看代碼就好懂了。

My Code：

/**
2016 - 09 - 20 晚上
Author: ITAK
Motto:

本日的我要超出昨日的我，明日的我要勝過本日的我，
以創作出更好的代碼為目標，不斷地超出自己。
**/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9+5;
const int MAXN = 1e3+5;
const int MOD = 1e6+3;
const double eps = 1e⑺;
const double PI = acos(-1);
using namespace std;

int Scan_Int()///輸入外掛
{
    int res = 0, ch, flag = 0;
    if((ch=getchar()) == '-')
        flag = 1;
    else if(ch >= '0' && ch<='9')
        res = ch-'0';
    while((ch=getchar())>='0' && ch<='9')
        res = res*10+ch-'0';
    return flag?-res:res;
}
LL Scan_LL()///輸入外掛
{
    LL res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}

void Out(int a)///輸出外掛
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
LL c[MAXN][MAXN];
void Init()
{
    c[0][0] = 1;
    for(int i=1; i<MAXN; i++)
        c[i][0] = 1;
    for(int i=1; i<MAXN; i++)
        for(int j=1; j<MAXN; j++)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
LL a[MAXN];
int cnt[70];
int main()
{
    Init();
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%I64d",&a[i]);
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<n; i++)
        {
            LL tp = a[i];
            for(int j=0; j<63; j++)
            {
                if(tp & 1)
                    cnt[j]++;
                tp>>=1;
            }
        }
        for(int i=1; i<=n; i++)
        {
            LL sum = 0;
            for(int j=0; j<63; j++)
            {
                if(cnt[j])
                {
                    for(int k=1; k<=i; k+=2)
                    {
                        if(cnt[j]>=k && (n-cnt[j]>=i-k))
                        {
                            sum += ((c[cnt[j]][k]*c[(n-cnt[j])][i-k]%MOD)*(1LL<<j)%MOD);
                            sum %= MOD;
                        }
                    }
                }
            }
            if(i != n)
                cout<<sum<<" ";
            else
                cout<<sum<<endl;
        }
    }
    return 0;
}

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 javascript實現頁面中回到頂部功能

下一篇 Spring學習總結（19）——Spring概念詳解

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

HDU 4810 Wall Painting（組合數學 + 位運算）——2013ACM/ICPC亞洲區南京站現場賽

Wall Painting