TopCoder SRM620 DIV1 HARD (800pt)
Problem Statement
各要素が正整数の $N$ 次正方行列 $A$ が与えられる.
いくつかの要素の以下の条件1~3.をみたすように選ぶ方法は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
各要素を選ぶかどうかを ${\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$ 倍ぐらい早くなる.
// #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)