首页 > 代码库 > uva11542
uva11542
https://vjudge.net/problem/UVA-11542
xor高斯消元。。。
答案为2^f-1
其实书上有一个问题
样例有3种情况,其中4,6,15是绑在一起的,也就是他们必须满足一定的选或不选的关系。当一个变量是自由的,当且仅当他的所有的幂%2==0,也就是说这个数是一个完全平方数,否则这个数的选择肯定会影响到其他数。
那么我们可以吧所有数分为有界变量和自由变量,就是确定选或不选和可选可不选,确定选或不选看做一个大的元素,因为他们选或不选组成的集合也是一个完全平方数,也就是一个自由变量。那么我们得答案就是1<<(自由变量+1)-1 ,-1是空集。+1是有界变量的组合体。
书上的样例解释应该是错的,自由变量只有x1,而为什么程序能对大概是因为下标是从0开始,正好规避了那个加一,不知道对不对,求打脸。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 510; int n, lim; int a[N][N], p[N], mark[N]; void Init() { for(int i = 2; i <= 500; ++i) { if(!mark[i]) p[++p[0]] = i; for(int j = 1; j <= p[0] && i * p[j] <= 500; ++j) { mark[i * p[j]] = 1; if(i % p[j] == 0) break; } } } int gauss_jordan(int lim) { int row = 1, col = 1; //col 列 for(; row <= lim && col <= n; ++col) { int x = 0; for(int i = row; i <= lim; ++i) if(a[i][col] == 1) { x = i; break; } if(!x) continue; for(int i = 1; i <= n + 1; ++i) swap(a[row][i], a[x][i]); for(int i = 1; i <= lim; ++i) if(a[i][col] && i != row) for(int j = 1; j <= n + 1; ++j) a[i][j] ^= a[row][j]; ++row; } return row; } int main() { Init(); int T; scanf("%d", &T); while(T--) { lim = 0; memset(a, 0, sizeof(a)); scanf("%d", &n); for(int i = 1; i <= n; ++i) { ll x; scanf("%lld", &x); for(int j = 1; j <= p[0]; ++j) { if(p[j] > x) break; lim = max(lim, j); while(x % p[j] == 0) { x /= p[j]; a[j][i] ^= 1; } } } int x = gauss_jordan(lim) - 1; printf("%lld\n", (1ll << (ll)(n - x)) - 1); } return 0; }
uva11542
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。