网站建设html模板,网络推广如何有效,凡科快图官方,破解php网站后台密码解析
关键结论#xff1a; 若 nnn 个数组成的线性基大小为 SSS#xff0c;则其子集异或组成的结果有 2S2^S2S 种#xff0c;且每种结果都有 2n−S2^{n-S}2n−S 种方案。 证明#xff1a;考虑 n−Sn-Sn−S 个没有加入线性基的元素的任意一个子集#xff0c;其异或和为 xxx…解析
关键结论 若 nnn 个数组成的线性基大小为 SSS则其子集异或组成的结果有 2S2^S2S 种且每种结果都有 2n−S2^{n-S}2n−S 种方案。 证明考虑 n−Sn-Sn−S 个没有加入线性基的元素的任意一个子集其异或和为 xxx线性基中的互不相同的 2S2^S2S 种异或和分别与 xxx 异或必然得到 2S2^S2S 种不同结果又由于这 nnn 个数异或的结果只有 2S2^S2S 个所以就是每种结果的方案1。一共有 2n−S2^{n-S}2n−S 个 xxx每种结果也就有 2n−S2^{n-S}2n−S 个方案。
有了这个结论本题也就结束了直接求出排名后乘一个2的幂次即可。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define int ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define OK debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N4e5100;
const int mod1e97;
int n,m,d;ll a[70],mi[70],o30,num;
inline int ins(int x){for(int io;i0;i--){if(!(xmi[i])) continue;if(!a[i]){a[i]x;return true;}x^a[i];}return false;
}
int rnk(int x){int res(0),nownum;for(int io;i0;i--){if(!a[i]) continue;now--;if(xmi[i]){//x^a[i];resmi[now];}}return res;
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmi[0]1;for(int i1;io;i) mi[i]mi[i-1]1;nread();for(int i1;in;i) numins(read());//for(int i0;io;i) if(a[i]) printf(%lld ,a[i]);//puts();int ansrnk(read());for(int i1;in-num;i) ansans*2%10086;printf(%lld\n,(ans1)%10086);
}
/*
*/
