TopCoder SRM620 DIV1 HARD - PerfectSquare

Source

TopCoder SRM620 DIV1 HARD (800pt)
Problem Statement

問題概要

各要素が正整数の $N$ 次正方行列 $A$ が与えられる.
いくつかの要素の以下の条件1~3.をみたすように選ぶ方法は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

  1. 全ての行についてその行から選ばれた要素の数は奇数個
  2. 全ての列についてその列から選ばれた要素の数は奇数個
  3. 選ばれた要素の積は平方数(ある整数の自乗)

解法

各要素を選ぶかどうかを ${\mathbb Z}/2{\mathbb Z}$ 上の連立一次方程式で表す.
条件は,各行から選ばれた要素の和(${\mathbb Z}/2{\mathbb Z}$ での和)が $1$ とか,
各素数について,その素数をちょうど奇数個だけ素因数に持つ要素が選ばれた数が $0$ とか.
後は,Gaussの掃き出し法で,解を持つかを判定して,解を持つなら,連立一次方程式の行列のrankを求めて,いくつ自由度があるかを調べれば良い.
変数の数は $R = N^2$ で,式の数 $C$ は $2N +$ どこかの要素に含まれる素数の数ぐらいで高々 $1000$ 程度.
計算時間量は $O(R^2 C)$ でビットに押し込めると $64$ 倍ぐらい早くなる.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define ull unsigned ll

int binaryGaussJordan(int r, int c, int right, ull **mat){
  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,rank+1,r) if(mat[i][j>>6]&(1ULL<<(j&63))) REP(k,j>>6,b) mat[i][k] ^= mat[rank][k];
    rank++;
  }

  return rank;
}

int getPrime(int N, int res[]){int i,a,b,s=1,f[4780],S=1;const int r=23000;bool B[r],*p=B;N/=2;res[0]=2;b=min(r,N);REP(i,1,b)p[i]=1;REP(i,1,b)if(p[i]){res[s++]=2*i+1;f[S]=2*i*(i+1);if(f[S]<N){for(;f[S]<r;f[S]+=res[S])p[f[S]]=0;S++;}}for(a=r;a<N;a+=r){b=min(a+r,N);p-=r;REP(i,a,b)p[i]=1;REP(i,1,S)for(;f[i]<b;f[i]+=res[i])p[f[i]]=0;REP(i,a,b)if(p[i])res[s++]=2*i+1;}return s;}
int ps, p[40000];

class PerfectSquare {
public:
int ways(vector <int> x) {
  int i, j, k, n, n2;
  int r, c, right, b, rank;
  int res;
  ull *mat[10000];
  void *mem = malloc(40000000);
  
  ps = getPrime(40000, p);

  n2 = x.size();
  for(n=1;;n++) if(n*n==n2) break;

  r = 0; c = n2; right = 1;
  b = (c + right + 63) / 64;

  mat[0] = (ull*)mem;
  REP(i,1,10000) mat[i] = mat[i-1] + b;

  rep(i,n){
    rep(j,b) mat[r][j] = 0;
    rep(j,n){
      k = i*n + j;
      mat[r][k>>6] ^= (1ULL<<(k&63));
    }
    mat[r][n2>>6] ^= (1ULL<<(n2&63));
    r++;

    rep(j,b) mat[r][j] = 0;
    rep(j,n){
      k = j*n + i;
      mat[r][k>>6] ^= (1ULL<<(k&63));
    }
    mat[r][n2>>6] ^= (1ULL<<(n2&63));
    r++;
  }

  while(ps){
    rep(k,ps){
      rep(j,b) mat[r][j] = 0;
      rep(i,n2) while(x[i] % p[k]==0) x[i]/=p[k], mat[r][i>>6] ^= (1ULL<<(i&63));
      rep(j,b) if(mat[r][j]) break;
      if(j<b) r++;
    }

    ps = 0;
    rep(i,n2) if(x[i] > 1) p[ps++] = x[i];
  }

  rank = binaryGaussJordan(r, c, right, mat);

  REP(i,rank,r) if(mat[i][n2>>6]&(1ULL<<(n2&63))) return 0;
  res = 1;
  REP(i,rank,n2) res = (res * 2) % 1000000007;
  
  return res;
}

}

Current time: 2024年03月29日20時46分03秒
Last modified: 2014年05月11日17時44分03秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM620 SRM_Div1_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン: