Description

校慶志愿者小Z在休息時間和同學(xué)們玩卡牌游戲。一共有n張卡牌，每張卡牌上有一個數(shù)Ai，每次可以從中選出k張卡牌。一種選取方案的幸運值為這k張卡牌上數(shù)的異或和。小Z想知道所有選取方案的幸運值之和除以998244353的余數(shù)。

Input

輸入的第一行有兩個整數(shù)n和k。
第二行有n個整數(shù)，表示序列A。

Output

一個整數(shù)表示答案。

Sample Input

輸入1：

3 2
1 2 3

輸入2：

10 5
123 456 789 987 654 321 101 202 303 404

Sample Output

輸出1：

6

輸出2：

130776

Data Constraint

對于30%的數(shù)據(jù)滿足，1<=n<=20
對于另30%的數(shù)據(jù)滿足，1<=n<=100,0

Hint

樣例1幸運值之和為(1 ⊕ 2) + (1 ⊕ 3) + (2 ⊕ 3) = 6

Solution

• 我們發(fā)現(xiàn)每一位的答案與選了哪些數(shù)無關(guān)，而與哪一位的0、1數(shù)量有關(guān)。

• 于是我們統(tǒng)計出這 N 個數(shù)的每一位的0、1數(shù)。

• 對于每一位，我們設(shè)有 x 個 1 ，那么則有 n?x 個 0 。

• 要在其中選 k 個數(shù)，又發(fā)現(xiàn)其異或和只與 1 的個數(shù)的奇偶性有關(guān)。

• 那么這一位的答案即為：∑j=1,j≡1(mod 2)xCjx?Ck?jn?x

• 即選一些數(shù)作為1、另一些數(shù)作為0的組合數(shù)。

• 注意特判 Cyx 中當(dāng) x<y 時返回 0 。

• 時間復(fù)雜度為 N log Ai 。

Code

#include<cstdio> #include<cmath> using namespace std; const int N=1e5+1,mo=998244353; int mx; long long ans; int f[31]; long long g[N],h[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline long long ksm(long long x,int y) {long long s=1;while(y){if(y&1) s=s*x%mo;x=x*x%mo;y>>=1;}return s; } inline long long C(int x,int y) {if(x<y) return 0;return g[x]*h[x-y]%mo*h[y]%mo; } int main() {int n=read(),k=read();for(int i=1;i<=n;i++){int x=read(),y=log2(x);if(y>mx) mx=y;for(int j=0;j<=y;j++) f[j]+=x&1,x>>=1;}long long p=g[0]=h[0]=1;for(int i=1;i<=n;i++) g[i]=g[i-1]*i%mo;h[n]=ksm(g[n],mo-2);for(int i=n-1;i;i--) h[i]=h[i+1]*(i+1)%mo;for(int i=0;i<=mx;i++,p<<=1)for(int j=1,q=f[i]<k?f[i]:k;j<=q;j+=2)ans=(ans+C(n-f[i],k-j)*C(f[i],j)%mo*p%mo)%mo;printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5414. 【NOIP2017提高A组集训10.22】幸运值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。