1 solutions
-
0
本题预估难度Div. 2 A,但由于选手们都非常擅长乱搞导致反而让它有了一点区分度。
发现本质上对于每一个,是的位最终有的概率为。由于是把整个区间按位或,所以对于每一位来说,只要有一个的该位是即可。因此对每一位统计一下的个数,用概率算一下再把结果乘起来就好了。
#include<bits/stdc++.h> using namespace std; const int mod=998244353; const int inv2=(mod+1)>>1; int st[32]; int ksm(int ba,int p){ int ret=1; while(p){ if(p&1) ret=1ll*ret*ba%mod; ba=1ll*ba*ba%mod; p>>=1; } return ret; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,x; cin>>n>>x; for(int t=1;t<=n;++t){ int a; cin>>a; for(int i=0;i<32;++i) if(a>>i&1) ++st[i]; } int ans=1; for(int i=0;i<32;++i){ if(x>>i&1){ ans=1ll*ans*(1-ksm(inv2,st[i])+mod)%mod; }else{ ans=1ll*ans*ksm(inv2,st[i])%mod; } } printf("%d\n",ans); return 0; }
Information
- ID
- 156
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 228
- Accepted
- 23
- Uploaded By