HDU 5833 (2016大学生网络预选赛) Zhu and 772002(高斯消元求齐次方程的秩)

  网络预选赛的题目……比赛的时候没有做上,确实是没啥思路,只知道肯定是整数分解,然后乘起来素数的幂肯定是偶数,然后就不知道该怎么办了…

  最后题目要求输出方案数,首先根据题目应该能写出如下齐次方程(从别人那里盗的……):

  a11*x1  ^  a12*x2  ^  ...  ^  a1n*xn=0

  a21*x1  ^  a22*x2  ^  ...  ^  a2n*xn=0

  ...

  an1*x1  ^  an2*x2  ^  ...  ^  ann*xn=0,Aij表示选的第j个数的第i个质数(可能有些人跟我有一样的疑问,为什么不是第i个数的第j个质数呢,这是为了方便消元计算),xi为1或者0,代表数选和不选。

  所以这个问题就化成了该方程有几个解的问题,该方程的特征矩阵有303行,n列,因为1-2000之间一共有303个素数,实际可以省略用不到的那些。

  然后,学过线性代数的童鞋都知道,当它的特征矩阵的秩是n的时候,该方程有唯一解,就是0解,所以当时我们求出秩来以后,如果秩是r且r < n,也就意味着有n-r个0行,同时意味着,它与其它行线性相关,也就是这一行不影响答案,有选和不选两种情况,一共就有2的(n-r)次方 种情况,求秩的方法用高斯消元的模板,类比成异或就可以了,当时我还自己写了一个消元的函数,发现不对……还是贴的人家的模板。

  代码及注释如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define N 305
#define mod 1000000007
LL a[N];
int prime[N],tot,n,m;
int fenjie[N][N],zhuan[N][N];
bool yes(int x)
{
for(int i = ; i*i <= x; i++)
{
if(x%i == ) return false;
}
return true;
}
void Make_P()///暴力版素数表,实在懒得改……
{
tot = ;
for(int i = ; i <= ; i++)
{
if(yes(i)) prime[tot++] = i;
}
}
void FenJie()///质因数分解
{
memset(fenjie,,sizeof(fenjie));
m = -;
for(int i = ; i < n; i++)
{
LL tmp = a[i];
for(int j = ; j < tot; j++)
{
while(tmp % prime[j]==)
{
fenjie[j][i]++;
tmp /= prime[j];
m = max(m,j);///取一个最大的j值即可
}
fenjie[j][i] %= ;
if(tmp == ) break;
}
}
m++;
}
int Rank()///高斯消元求秩[j][i]的形式派上了用场
{
int i=,j=,k,r,u;
while(i < m && j < n)
{
r = i;
for(k=i; k<m; k++)
{
if(fenjie[k][j])
{
r=k;
break;
}
}
if(fenjie[r][j])
{
if(r != i)
for(k=; k <= n; k++)swap(fenjie[r][k],fenjie[i][k]);
for(u=i+; u<m; u++)
if(fenjie[u][j])
for(k=i; k<=n; k++)
fenjie[u][k]^=fenjie[i][k];
i++;
}
j++;
}
return i;
} int mypow(int x,int y)
{
int res = ;
for(int i = ; i <= y; i++)
{
res = ((x%mod)*(res%mod)) % mod;
}
return res;
}
int Slove()
{
int mi = n-Rank();
return (mypow(,mi) - ) % mod;
}
int main()
{
// freopen("in1.cpp","r",stdin);
int t,ca=;
Make_P();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = ; i < n; i++)
{
cin>>a[i];
}
FenJie();
printf("Case #%d:\n",++ca);
cout<<Slove()<<endl;
}
return ;
}
上一篇:利用PHP脚本辅助MySQL数据库管理5-检查异常数据


下一篇:总结Spring、Hibernate、Struts2官网下载jar文件