程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bestcoders

bestcoders

編輯:C++入門知識

bestcoders


ZYB loves Xor I

Accepts: 142 Submissions: 696 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 問題描述
ZYB喜歡研究Xor,現在他得到了一個長度為n的數組A。於是他想知道:對於所有數對(i,j)(i∈[1,n],j∈[1,n])lowbit(AixorAj)之和為多少.由於答案可能過大,你需要輸出答案對998244353取模後的值
定義lowbit(x)=2k,其中k是最小的滿足(x and 2k)>0的數
特別地:lowbit(0)=0
輸入描述
一共T(T≤10)組數據,對於每組數據:
第一行一個正整數n,表示數組長度
第二行n個非負整數,第i個整數為Ai
n∈[1,5∗104]Ai∈[0,229]
輸出描述
每組數據輸出一行Case #x: ans。x表示組數編號,從1開始。ans為所求值。
輸入樣例
2
5
4 0 2 7 0
5
2 6 5 4 0
輸出樣例
Case #1: 36

Case #2: 40

 

#include 
#include 
#include 
#include 

using namespace std;

const long long MOD = 998244353;
const int maxn = 30;
const int M = 2;
long long  ans;

struct Node
{
    int v;
    Node *next[M];
};

struct Tree
{
    Node *root;
    int v;

    Tree()//constructor
    {
        root = new Node;
        root->v = 0;
        for(int i=0; inext[i] = NULL;
    }

    void insert(int t)
    {
        Node *p = root, *q;

        for(int i=0; inext[tmp] == NULL)
            {
                q = new Node;
                q->v = 1;
                for(int i=0; inext[i] = NULL;
                p->next[tmp] = q;
                p = q;
            }
            else
            {
                p = p->next[tmp];
                p->v++;
            }
        }
    }

    void find(int t)
    {
        Node *p = root;
        for(int i=0; inext[tmp^1] != NULL)
                ans = (ans + (p->next[tmp^1]->v)*(long long)(1<next[tmp];
        }
    }
};

const int N = 50005;
int a[N];
int kase = 0;

int main()
{
    int T, n;
    scanf(%d, &T);
    while(T--)
    {
        ans = 0;
        Tree tree;
        scanf(%d, &n);
        for(int i=0; i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved