Submission #2090589
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define MD 1000000007
void *wmem;
template<class T> void walloc1d(T **arr, int x, void **mem = &wmem){
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
struct mint{
static unsigned R, RR, Rinv, W, md, mdninv;
unsigned val;
mint(){
}
mint(int a){
val = mulR(a);
}
mint(unsigned a){
val = mulR(a);
}
mint(long long a){
val = mulR(a);
}
mint(unsigned long long a){
val = mulR(a);
}
int get_inv(long long a, int md){
long long e, s=md, t=a, u=1, v=0;
while(s){
e=t/s;
t-=e*s;
u-=e*v;
swap(t,s);
swap(u,v);
}
if(u<0){
u+=md;
}
return u;
}
void setmod(unsigned m){
int i;
unsigned t;
W = 32;
md = m;
R = (1ULL << W) % md;
RR = (unsigned long long)R*R % md;
switch(m){
case 104857601:
Rinv = 2560000;
mdninv = 104857599;
break;
case 998244353:
Rinv = 232013824;
mdninv = 998244351;
break;
case 1000000007:
Rinv = 518424770;
mdninv = 2226617417U;
break;
case 1000000009:
Rinv = 171601999;
mdninv = 737024967;
break;
case 1004535809:
Rinv = 234947584;
mdninv = 1004535807;
break;
case 1007681537:
Rinv = 236421376;
mdninv = 1007681535;
break;
case 1012924417:
Rinv = 238887936;
mdninv = 1012924415;
break;
case 1045430273:
Rinv = 254466304;
mdninv = 1045430271;
break;
case 1051721729:
Rinv = 257538304;
mdninv = 1051721727;
break;
default:
Rinv = get_inv(R, md);
mdninv = 0;
t = 0;
for(i=0;i<(int)W;i++){
if(t%2==0){
t+=md;
mdninv |= (1U<<i);
}
t /= 2;
}
}
}
unsigned mulR(unsigned a){
return (unsigned long long)a*R%md;
}
unsigned mulR(int a){
if(a < 0){
a = a%md+md;
}
return mulR((unsigned)a);
}
unsigned mulR(unsigned long long a){
return mulR((unsigned)(a%md));
}
unsigned mulR(long long a){
a %= md;
if(a < 0){
a += md;
}
return mulR((unsigned)a);
}
unsigned reduce(unsigned T){
unsigned m=T * mdninv, t=(unsigned)((T + (unsigned long long)m*md) >> W);
if(t >= md){
t -= md;
}
return t;
}
unsigned reduce(unsigned long long T){
unsigned m=(unsigned)T * mdninv, t=(unsigned)((T + (unsigned long long)m*md) >> W);
if(t >= md){
t -= md;
}
return t;
}
unsigned get(){
return reduce(val);
}
mint &operator+=(mint a){
val += a.val;
if(val >= md){
val -= md;
}
return *this;
}
mint &operator-=(mint a){
if(val < a.val){
val = val + md - a.val;
}
else{
val -= a.val;
}
return *this;
}
mint &operator*=(mint a){
val = reduce((unsigned long long)val*a.val);
return *this;
}
mint &operator/=(mint a){
return *this *= a.inverse();
}
mint operator+(mint a){
return mint(*this)+=a;
}
mint operator-(mint a){
return mint(*this)-=a;
}
mint operator*(mint a){
return mint(*this)*=a;
}
mint operator/(mint a){
return mint(*this)/=a;
}
mint operator+(int a){
return mint(*this)+=mint(a);
}
mint operator-(int a){
return mint(*this)-=mint(a);
}
mint operator*(int a){
return mint(*this)*=mint(a);
}
mint operator/(int a){
return mint(*this)/=mint(a);
}
mint operator+(long long a){
return mint(*this)+=mint(a);
}
mint operator-(long long a){
return mint(*this)-=mint(a);
}
mint operator*(long long a){
return mint(*this)*=mint(a);
}
mint operator/(long long a){
return mint(*this)/=mint(a);
}
mint operator-(void){
mint res;
if(val){
res.val=md-val;
}
else{
res.val=0;
}
return res;
}
operator bool(void){
return val!=0;
}
operator int(void){
return get();
}
operator long long(void){
return get();
}
mint inverse(){
int a = val, b = md, u = 1, v = 0, t;
mint res;
while(b){
t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if(u < 0) u += md;
res.val = (unsigned long long)u*RR % md;
return res;
}
mint pw(unsigned long long b){
mint a(*this), res;
res.val = R;
while(b){
if(b&1) res *= a;
b >>= 1;
a *= a;
}
return res;
}
bool operator==(int a){return mulR(a)==val;}
bool operator!=(int a){return mulR(a)!=val;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;
}
mint operator-(int a, mint b){
return mint(a)-=b;
}
mint operator*(int a, mint b){
return mint(a)*=b;
}
mint operator/(int a, mint b){
return mint(a)/=b;
}
mint operator+(long long a, mint b){
return mint(a)+=b;
}
mint operator-(long long a, mint b){
return mint(a)-=b;
}
mint operator*(long long a, mint b){
return mint(a)*=b;
}
mint operator/(long long a, mint b){
return mint(a)/=b;
}
void rd(int &x){
int k, m=0;
x=0;
for(;;){
k = getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
void wt_L(int x){
char f[10];
int m=0, s=0;
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
putchar_unlocked('-');
}
while(s--){
putchar_unlocked(f[s]+'0');
}
}
void wt_L(mint x){
int i;
i = (int)x;
wt_L(i);
}
struct combination_mint{
mint *fac, *ifac;
void init(int n, void **mem = &wmem){
int i;
walloc1d(&fac, n, mem);
walloc1d(&ifac, n, mem);
fac[0] = 1;
for(i=1;i<n;i++){
fac[i] = fac[i-1] * i;
}
ifac[n-1] = 1 / fac[n-1];
for(i=n-2;i>=0;i--){
ifac[i] = ifac[i+1] * (i+1);
}
}
mint C(int a, int b){
if(b < 0 || b > a){
return 0;
}
return fac[a]*ifac[b]*ifac[a-b];
}
mint P(int a, int b){
if(b < 0 || b > a){
return 0;
}
return fac[a]*ifac[a-b];
}
mint H(int a, int b){
if(a==0 && b==0){
return 1;
}
if(a<=0 || b<0){
return 0;
}
return C(a+b-1, b);
}
}
;
char memarr[96000000];
combination_mint comb;
int A[1100][1100], C[2200], K, N, X, Y, cur[2200], ok[2200], sz[2200][2], use[2200];
inline int nrm(int x){
if(x < (x^X)){
return x;
}
return x^X;
}
mint solve(int dep){
int i, j, k, x;
mint res, tmp;
res = 0;
if(dep==K){
res = 1;
for(i=0;i<2048;i++){
use[i] = 0;
}
for(i=0;i<dep;i++){
use[cur[i]]++;
}
for(i=0;i<2048;i++){
if(use[i]){
tmp = 0;
for(j=0;j<use[i]+1;j++){
if(j <= sz[i][0] && use[i]-j <= sz[i][1]){
tmp += comb.C(use[i], j);
}
}
res *= tmp;
}
}
return res;
}
if(dep==0){
for(i=0;i<2048;i++){
if(ok[i]){
ok[i]--;
cur[dep] = i;
res += solve(dep+1);
ok[i]++;
}
}
return res;
}
x = nrm(A[0][dep] ^ cur[0]);
if(ok[x]){
for(i=0;i<dep;i++){
if(x != nrm(A[i][dep] ^ cur[i])){
break;
}
}
if(i==dep){
ok[x]--;
cur[dep] = x;
res += solve(dep+1);
ok[x]++;
}
}
return res;
}
int main(){
int i, j, k;
mint res;
wmem = memarr;
{
mint x;
x.setmod(MD);
}
comb.init(1100);
rd(N);
rd(K);
rd(X);
rd(Y);
{
int Lj4PdHRW;
for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
rd(C[Lj4PdHRW]);
}
}
for(i=0;i<K;i++){
for(j=0;j<K;j++){
rd(A[i][j]);
}
}
for(i=0;i<K;i++){
for(j=0;j<K;j++){
A[i][j] ^= X;
}
}
Y ^= X;
X = Y;
for(i=0;i<K;i++){
for(j=0;j<K;j++){
A[i][j] = nrm(A[i][j]);
}
}
for(i=0;i<K;i++){
if(A[i][i] != 0){
wt_L(0);
putchar_unlocked('\n');
return 0;
}
}
for(i=0;i<K;i++){
for(j=i+1;j<K;j++){
if(A[i][j] != A[j][i]){
wt_L(0);
putchar_unlocked('\n');
return 0;
}
}
}
for(i=0;i<2048;i++){
ok[i] = 0;
}
for(i=0;i<2048;i++){
sz[i][0] = sz[i][1] = 0;
}
for(i=0;i<N;i++){
k = nrm(C[i]);
ok[k]++;
if(k==C[i]){
sz[k][0]++;
}
else{
sz[k][1]++;
}
}
res = solve(0);
wt_L(res);
putchar_unlocked('\n');
return 0;
}
// cLay varsion 20180208-1
// --- original code ---
// int N, K, X, Y, C[2200];
// int A[1100][1100];
//
// int ok[2200];
// int sz[2200][2];
//
// int cur[2200];
// int use[2200];
// combination_mint comb;
//
// inline int nrm(int x){
// if(x < (x^X)) return x;
// return x^X;
// }
//
// mint solve(int dep){
// int i, j, k, x;
// mint res, tmp;
// res = 0;
//
// if(dep==K){
// res = 1;
// rep(i,2048) use[i] = 0;
// rep(i,dep) use[cur[i]]++;
// rep(i,2048) if(use[i]){
// tmp = 0;
// rep(j,use[i]+1){
// if(j <= sz[i][0] && use[i]-j <= sz[i][1]) tmp += comb.C(use[i], j);
// }
// res *= tmp;
// }
// return res;
// }
//
// if(dep==0){
// rep(i,2048) if(ok[i]){
// ok[i]--;
// cur[dep] = i;
// res += solve(dep+1);
// ok[i]++;
// }
// return res;
// }
//
// x = nrm(A[0][dep] ^ cur[0]);
// if(ok[x]){
// rep(i,dep) if(x != nrm(A[i][dep] ^ cur[i])) break;
// if(i==dep){
// ok[x]--;
// cur[dep] = x;
// res += solve(dep+1);
// ok[x]++;
// }
// }
// return res;
// }
//
// {
// int i, j, k;
// mint res;
//
// comb.init(1100);
//
// rd(N,K,X,Y,C(N));
// rep(i,K) rep(j,K) rd(A[i][j]);
// rep(i,K) rep(j,K) A[i][j] ^= X;
// Y ^= X;
// X = Y;
//
// rep(i,K) rep(j,K) A[i][j] = nrm(A[i][j]);
//
// rep(i,K) if(A[i][i] != 0){
// wt(0); return 0;
// }
// rep(i,K) rep(j,i+1,K) if(A[i][j] != A[j][i]){
// wt(0); return 0;
// }
//
// rep(i,2048) ok[i] = 0;
// rep(i,2048) sz[i][0] = sz[i][1] = 0;
// rep(i,N){
// k = nrm(C[i]);
// ok[k]++;
// if(k==C[i]) sz[k][0]++; else sz[k][1]++;
// }
//
// res = solve(0);
// wt(res);
// }
Submission Info
Submission Time |
|
Task |
D - XOR XorY |
User |
LayCurse |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
10851 Byte |
Status |
AC |
Exec Time |
25 ms |
Memory |
6400 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
2304 KB |
00_example_02.txt |
AC |
2 ms |
2304 KB |
00_example_03.txt |
AC |
2 ms |
2304 KB |
01.txt |
AC |
2 ms |
2304 KB |
02.txt |
AC |
2 ms |
2432 KB |
03.txt |
AC |
2 ms |
2432 KB |
04.txt |
AC |
2 ms |
2432 KB |
05.txt |
AC |
2 ms |
2304 KB |
06.txt |
AC |
2 ms |
2432 KB |
07.txt |
AC |
2 ms |
2432 KB |
08.txt |
AC |
2 ms |
2432 KB |
09.txt |
AC |
2 ms |
2560 KB |
10.txt |
AC |
2 ms |
2304 KB |
11.txt |
AC |
6 ms |
4352 KB |
12.txt |
AC |
18 ms |
6400 KB |
13.txt |
AC |
3 ms |
3456 KB |
14.txt |
AC |
4 ms |
3712 KB |
15.txt |
AC |
4 ms |
3584 KB |
16.txt |
AC |
5 ms |
3840 KB |
17.txt |
AC |
10 ms |
6400 KB |
18.txt |
AC |
15 ms |
6400 KB |
19.txt |
AC |
8 ms |
6400 KB |
20.txt |
AC |
9 ms |
6400 KB |
21.txt |
AC |
24 ms |
6400 KB |
22.txt |
AC |
22 ms |
6400 KB |
23.txt |
AC |
17 ms |
6400 KB |
24.txt |
AC |
25 ms |
6400 KB |
25.txt |
AC |
19 ms |
6400 KB |
26.txt |
AC |
6 ms |
4096 KB |
27.txt |
AC |
4 ms |
3840 KB |
28.txt |
AC |
3 ms |
3072 KB |
29.txt |
AC |
3 ms |
3200 KB |
30.txt |
AC |
5 ms |
4096 KB |
31.txt |
AC |
4 ms |
3712 KB |
32.txt |
AC |
2 ms |
3072 KB |
33.txt |
AC |
2 ms |
3200 KB |
34.txt |
AC |
14 ms |
6400 KB |
35.txt |
AC |
19 ms |
6400 KB |