保存されている過去のバージョンの一覧

2015年01月16日07時21分41秒

Codeforces Round #285 DIV1 D問題 - Misha and XOR

Source

Codeforces Round #285 DIV1 D問題
Problem description

問題概要

$M$ 個の整数 $A_1,A_2,\ldots,A_M$ が与えられる．
それぞれの $1 \leq k \leq M$ に対して，$A_k$ は $A_1,A_2,\ldots,A_{k-1}$ からいくつか選んでXORすることで得られるかどうかを判定して，得られるならば，選ぶ方法を $1$ つ求める問題．

解法

${\mathbb Z}/2{\mathbb Z}$ 上の行列 $X$ を以下のように作る．
$\quad X_{ij} = A_j$ を $2$ 進数で表した時の $i$ ビット目
そうしてできた行列をガウスの消去法などで階段行列にする．
更に，左から列を見ていって，新しい行を使うようになった最初の要素に関しては，その要素の列はそのビットだけになるように，上にある成分も消去していく．
（階段行列にすると同時に，交代代入する必要がなくなるように，右上の要素も消していく）
すると，連立一次方程式を同時に解いていることになるので，新しい行を使うようになった最初の列は，今までの要素のXORでは書けない．
そうでないなら，その列にある各ビットについて，その行を初めて使った要素を取ってきて，XOR取れば良い．
$10^{600}$ を2進数に直すとだいたい $2000$ 桁なので，行列のサイズは高々 $2000 \times 2000$ 程度で，これをガウスジョルダンすると $2000^3$ 程度の計算時間になる．
定数も軽いし，ビット並列すれば十分間に合う．
また，$10$ 進数を $2$ 進数に変換するのも愚直にやると，結構時間がかかるので注意．

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

ull mat[2100][40];
int binaryGaussJordan(int r, int c, int right){
  int i, j, k, b = (c+right+63)/64, rank = 0;

  rep(j,c){
    REP(i,rank,r) if(mat[i][j>>6]&(1ULL<<(j&63))) break;
    if(i==r) continue;
    if(i!=rank) REP(k,j>>6,b) swap(mat[i][k], mat[rank][k]);
    REP(i,0,r) if(i!=rank) if(mat[i][j>>6]&(1ULL<<(j&63))) REP(k,j>>6,b) mat[i][k] ^= mat[rank][k];
    rank++;
  }

  return rank;
}
int N;
char in[2010][2010];

char buf[2000];
int arr[5000], sz;

int ind[2222];
int ress, res[2222];

int main(){
  int i, j, k, x;

  reader(&N);
  rep(x,N){
    sz = reader(buf);
    rep(i,5*sz+11) arr[i] = 0;
    rep(i,sz) arr[i] = buf[sz-1-i] - '0';
    rep(i,sz) arr[i] = arr[5*i+4] * 10000 + arr[5*i+3] * 1000 + arr[5*i+2] * 100 + arr[5*i+1] * 10 + arr[5*i];
    sz = sz / 5 + 2;
    
    rep(i,2000) in[x][i] = 0;
    rep(i,2000){
      in[x][i] = arr[0] % 2;
      arr[0] /= 2;
      REP(j,1,sz){
        arr[j-1] += 50000 * (arr[j]%2);
        arr[j] /= 2;
      }
      if(arr[sz-1]==0) sz--;
      if(sz==0) break;
    }
  }

  rep(i,N) rep(j,2000){
    if(in[i][j]) mat[j][i/64] |= (1ULL << (i%64));
  }
  binaryGaussJordan(2000, N, 0);

  k = 0;
  rep(i,N){
    if(mat[k][i/64] & (1ULL << (i%64))){
      ind[k++] = i;
      writerLn(0);
    } else {
      ress = 1;
      rep(j,k) if(mat[j][i/64] & (1ULL << (i%64))) res[ress++] = ind[j];
      res[0] = ress-1;
      writerArr(res,ress);
    }
  }

  myed;
  return 0;
}

Current time: 2024年04月20日14時35分53秒
Last modified: 2015年01月16日07時21分41秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF285 CF_Div1_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：