高斯消元 hdu5833,hdu3364,hihocoder1195

Posted by Cww97 on 2016-08-15

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52212746
hdu5833

刘汝佳训练指南160页原题

题意:给300个数,选任意个数相乘,问多少种方法可以得到完全平方数(每个数LL范围,保证每个数的质因子不超过2000)
一点废话:
从提示可以看出,显然第一步分解质因数,由于每个数只能乘0或1次,所以4和16对于结果是等价的(3和27也是),统计每个数字的质因子个数然后模2,我们只需要最后每个质因子的指数是个偶数就行了,这里既然只有0或1,不如直接用异或来算,
则列出线性方程组:MaxP个方程(MaxP为用到的质因数个数):
每个方程n个未知数,分别代表每个数,每个数的该质因子加起来为偶数
然后可以套个高斯消元的板,或者简单的矩阵变换几次就可以了
我这里参考了刘汝佳训练指南160页的代码
(mdzz,原题,比赛的时候还有人讨论原题复制代码会不会被查重)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
const LL N = 333,PN = 2007;
int P,MaxP,n;
LL p[N];

struct matrix{
LL a[N][N];
int row,col;
matrix():row(N),col(N){
memset(a,0,sizeof(a));
}
matrix(int x,int y):row(x),col(y){
memset(a,0,sizeof(a));
}
LL* operator [] (int x){
return a[x];
}
void print(){
for (int i=0;i<=MaxP;i++){
for (int j=0;j<n;j++)
printf("%I64d ",a[i][j]);
puts("");
}
}
}a;

void getPrime(){
P=0;
bool isPrime[PN];
memset(isPrime,1,sizeof(isPrime));
for (LL i=2;i<PN;i++){
if(isPrime[i]) p[P++] = i;
for (LL j=0;j<P&&p[j]*i<PN;j++){
isPrime[i*p[j]] = 0;
if (i%p[j]==0) break;
}
}
}

void getMatrix() {
MaxP = 0;
LL x;
for (int i=0;i<n;i++) {
scanf("%I64d",&x);
for (int j=0;j<P&&p[j]<=x;j++)if(!(x%p[j])){
MaxP = max(MaxP,j);
while (x % p[j] == 0) {
a[j][i] ^= 1;
x /= p[j];
}
}
}
}

int Rank(int m,int n){
int i=0,j=0;
for (; i<m && j<n ;j++){
int r = i;
for (int k=i;k<m;k++)if(a[k][j]){r=k;break;}
if (a[r][j]){
if (r!=i)for(int k=0;k<=n;k++)swap(a[r][k],a[i][k]);
for (int u=i+1;u<m;u++)if (a[u][j])
for (int k=i;k<=n;k++)a[u][k] ^= a[i][k];
i++;
}
}
return i;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;
LL x;
scanf("%d",&T);
getPrime();
for (int cas=1;cas<=T;cas++){
scanf("%d",&n);
getMatrix();
int r = (n-Rank(P,n));
LL ans = 1;
for (;r--;)ans=(ans<<1)%MOD;
ans = (ans + MOD - 1) % MOD;
printf("Case #%d:\n%I64d\n", cas, ans);
}
return 0;
}

比赛当场用的高斯消元的板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LL Gauss(LL a[][N], const LL& n) {
LL res = 0, r = 0;
for (LL i = 0; i < n; i++) {
for(LL j = r; j <= P; j++) {
if (a[j][i] != 0) {
for (LL k = i; k < n; ++k)
swap(a[j][k], a[r][k]);
break;
}
}
if (a[r][i] == 0) {++res;continue;}
for (LL j = 0; j <= P; j++) {
if (j != r && a[j][i] != 0) {
LL tmp = a[j][i] / a[r][i];
for (LL k = i; k < n; k++) {
a[j][k] -= tmp * a[r][k];
}
}
}
++r;
}
return res;
}

后续会补一点高斯消元的简单题在这里

hdu3364
这次换了WY给的板
本题消元方式还是比较简单的,直接异或就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const double EPS=1e-6;
const int N=55;

struct matrix{
int a[N][N];
int row,col;
matrix():row(N),col(N){memset(a,0,sizeof(a));}
matrix(int x,int y):row(x),col(y){
memset(a,0,sizeof(a));
}
int* operator [](int x){return a[x];}
void print(){
for (int i=0;i<row;i++){
for (int j=0;j<col;j++)
printf("%d ",a[i][j]);
puts("");
}
puts("");
}
};

int Gauss(matrix a,int m,int n){
int x_cnt = 0;
int col, k; //col为列号,k为行号
for (k=0,col=0;k<m&&col<n; ++k, ++col){
int r = k; //r为第col列的一个1
for (int i=k;i<m;++i) if (a[i][col])r=i;
if (!a[r][col]){ k--; continue;}
if (r!=k)for (int i=col;i<=n;++i)
swap( a[r][i], a[k][i]);
for (int i=k+1;i<m; ++i)if (a[i][col])//消元
for (int j=col;j<=n;++j)a[i][j]^=a[k][j];
}
for (int i=k;i<m;++i) if (a[i][n])return -1;
if (k<=n)return n-k; //返回自由元个数
}

int main(){
//freopen("fuck.in","r",stdin);
int T,n,m,k,x,q;
scanf("%d", &T);
for (int cas=1;cas<=T;cas++){
printf("Case %d:\n",cas);
scanf("%d%d",&n,&m);
matrix mat(n,m+1);
for (int i=0;i<m;i++){
scanf("%d",&k);
for (;k--;){
scanf("%d",&x);
mat[x-1][i] = 1;
}
}
for (scanf("%d",&q);q--;){
matrix a = mat;
for (int i=0;i<n;i++){
scanf("%d",&x);
if (x)a[i][m]=1;
}
int k = Gauss(a,n,m);
if (k==-1)puts("0");
else printf("%I64d\n",1LL<<k);
}
}
return 0;
}

hilocoder1195,这个是少有的裸题,
http://hihocoder.com/problemset/problem/1195?sid=853427

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1010;
const double EPS=1e-7;
int m,n;
double a[N][N],x[N];

void print(){
for (int i=0;i<m;i++){
for (int j=0;j<=n;j++)
printf("%d ",a[i][j]);
puts("");
}
puts("");
}

int Gauss(int m,int n){
int col=0, k=0;//col为列号,k为行号
for (;k<m&&col<n;++k,++col){
int r = k;
for (int i=k+1;i<m;++i)
if(fabs(a[i][col])>fabs(a[r][col]))r=i;
if (fabs(a[r][col])<EPS){k--;continue;}//列全为0
if (r!=k)for(int i=col;i<=n;++i)
swap(a[k][i],a[r][i]);
for (int i=k+1;i<m;++i)//消元
if(fabs(a[i][col])>EPS){
double t = a[i][col]/a[k][col];
for (int j=col;j<=n;j++)a[i][j]-=a[k][j]*t;
a[i][col] = 0;
}
}
for(int i=k ;i<m ;++i)//无解
if (fabs(a[i][n])>EPS) return -1;
if (k < n) return n - k; //自由元个数
for (int i =n-1; i>=0; i--){//回带求解
double temp = a[i][n];
for (int j=i+1; j<n; ++j)
temp -= x[j] * a[i][j];
x[i] = (temp / a[i][i]);
}
return 0;
}

int main(){
//freopen("fuck.in","r",stdin);
for (;~scanf("%d%d",&n,&m);){
for (int i=0;i<m;i++)
for(int j=0;j<=n;j++)scanf("%lf",&a[i][j]);
int k = Gauss(m,n);
if (k<0) puts("No solutions");
else if (k>0) puts("Many solutions");
else for (int i=0;i<n;i++)
printf("%d\n",(int)(x[i]+0.5));
}
return 0;
}