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