QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#828755 | #4283. Power of XOR | lsxhyyds | TL | 0ms | 0kb | C++14 | 5.3kb | 2024-12-23 20:11:56 | 2024-12-23 20:11:58 |
answer
// #ifndef fio
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse3","sse2","sse")
// #pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
// #pragma GCC target("f16c")
// #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
// #pragma GCC diagnostic error "-fwhole-program"
// #pragma GCC diagnostic error "-fcse-skip-blocks"
// #pragma GCC diagnostic error "-funsafe-loop-optimizations"
// #pragma GCC diagnostic error "-std=c++20"
// #endif
#include <bits/stdc++.h>
#define N 1000005
#define M 3000005
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define i128 __int128
#define mk make_pair
#define x first
#define y second
//#define bas 20200721
//#define bas 1000000007
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define VI vector<int>
#define VL vector<ll>
#define lowbit(x) (x&(-x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIL pair<int,ll>
#define PLI pair<ll,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define PVL pair<VI,ll>
#define eps (1e-9)
#define mod 1000000007
//#define double long double
//#define int long long
using namespace std;
//int mod=998244353;
const double Pi=acos(-1);
struct mint {
int x;
mint() : x(0) {}
mint(long long y, bool flag = 0) {
if (flag) x = (int)(y);
else x = (int)((y % mod + mod) % mod);
}
friend const mint ksm(mint a, long long b);
const mint inv() {return ksm(*this, mod - 2);}
};
bool operator == (const mint a, const mint b) {return a.x == b.x;}
bool operator != (const mint a, const mint b) {return a.x != b.x;}
bool operator <(const mint a,const mint b){return a.x<b.x;}
bool operator >(const mint a,const mint b){return a.x>b.x;}
int operator ! (const mint a) {return !a.x;}
const mint operator + (const mint a, const mint b) {
mint res(a.x + b.x, 1);
if (res.x >= mod) res.x -= mod;
return res;
}
mint& operator += (mint &a, const mint b) {
a.x += b.x;
if (a.x >= mod) a.x -= mod;
return a;
}
const mint operator - (const mint a, const mint b) {
mint res(a.x - b.x, 1);
if (res.x < 0) res.x += mod;
return res;
}
mint& operator -= (mint &a, const mint b) {
a.x -= b.x;
if (a.x < 0) a.x += mod;
return a;
}
const mint operator * (const mint a, const mint b) {
return mint((long long)a.x * b.x % mod, 1);
}
mint& operator *= (mint &a, const mint b) {
a.x = (int)((long long)a.x * b.x % mod);
return a;
}
const mint ksm(mint a, long long b) {
mint res(1, 1);
for (; b; a *= a, b >>= 1)
if (b & 1) res *= a;
return res;
}
const mint operator / (const mint a, const mint b) {
return a * ksm(b, mod - 2);
}
mint& operator /= (mint &a, const mint b) {
a = a * ksm(b, mod - 2);
return a;
}
ostream& operator << (ostream &out, const mint a) {
return out << a.x;
}
istream& operator >> (istream &in, mint &a) {
long long y;
in >> y, a = mint(y);
return in;
}
PLL operator +(PLL a,PLL b){
return mk(a.x+b.x,a.y+b.y);
}
PLL operator +=(PLL &a,const PLL b){
a=a+b;
return a;
}
PLL operator *(PLL a,int b){
a=mk(a.x*b,a.y*b);
return a;
}
void chkmx(ll &x,ll y){
x=max(x,y);
}
void chkmn(ll &x,ll y){
x=min(x,y);
}
int tt;
int n,m,q,k;
string s;
ll a[N],f[45];
void ins(ll a){
for(int i=43;i>=0;--i){
if((a>>i)&1){
if(!f[i]){
f[i]=a;return ;
}
a^=f[i];
}
}
}
mint dp[1<<21][45],dp2[1<<21][45];
int fen=20;
void dfs(int u,ll msk){
if(u==fen){
int shu=__builtin_popcount(msk)-__builtin_popcount(msk&((1<<(fen+1))-1));
dp[msk&((1<<(fen+1))-1)][shu]+=1;
return ;
}
if(!f[u]){
dfs(u-1,msk);return ;
}
dfs(u-1,msk^f[u]);
dfs(u-1,msk);
}
mint kk[50];
void solve(){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
ins(a[i]);
}
int sum=0;
for(int i=0;i<44;++i){
if(f[i])++sum;
}
mint xi=ksm(2,n-sum);
dfs(43,0);
// cout<<"[[dsa\n";
for(int i=fen;i>=0;--i){
swap(dp2,dp);
// cout<<i<<"dasss\n";
for(int j=0;j<=44-fen;++j)
for(int msk=0;msk<(1<<(i+1));++msk)
dp[msk][j]=0;
for(int j=0;j<=44-fen;++j){
for(int msk=0;msk<(1<<(i+1));++msk){
// cout<<msk<<"opdas\n";
dp[msk][j]+=dp2[msk][j];
if(f[i])
dp[msk^f[i]][j]+=dp2[msk][j];
}
}
for(int j=0;j<=44-fen;++j)
for(int msk=0;msk<(1<<(i+1));++msk){
if((msk>>i)&1)
dp[msk^(1<<i)][j+1]+=dp[msk][j],dp[msk][j]=0;
}
}
for(int i=0;i<50;++i){
kk[i]=ksm(i,k);
}
// cout<<"ww\n";
mint ans=0;
for(int j=0;j<=44;++j){
for(int msk=0;msk<(1<<(fen+1));++msk){
ans+=xi*dp[msk][j]*kk[j+__builtin_popcount(msk)];
}
}
cout<<ans<<'\n';
}
signed main(){
// freopen("line.in","r",stdin);
// freopen("line.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// cin>>tt;
// while(tt--){
solve();
// }
return 0;
}
/*
2^2k=2^n*n^2
*/
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 1 2 3