一、题目
二、解法
张成线性空间的维数是 (m) 等价于线性不相关的向量有 (m) 个，把向量写成 (n imes m) 的矩阵的秩是 (m)
这里普及一下比内(-)柯西公式，对于 (s imes n) 的矩阵 (A) 和 (n imes s) 的矩阵 (B)，若 (sleq n)，设矩阵 (A_s) 是任意取出 (A) 的 (s) 列构成的 (s imes s) 的矩阵，(B_s) 是取出 (B) 中与 (A_s) 编号相对应的 (s) 行构成的 (s imes s) 的矩阵：
[|AB|=sum |A_s|cdot |B_s| ]
对于子问题 (1)，我们构造出 (m imes n) 的矩阵 (A) 为给定向量竖着排列的结果，答案是：
[sum |A_m|cdot |A^T_m|=|AA^T|
]
因为如果选出来的 (m) 个向量不满秩的话，算出来的行列式是 (0)；如果满秩算出来的行列式是 (1/2)，因为把相同的向量构成矩阵的行列式乘了上去（只不过转置了一下），所以模 (3) 的结果一定是 (1)，那么对总方案有 (1) 的贡献。
对于子问题 (2)，我们再构造 (n imes m) 的矩阵 (C) 表示第 (i) 个向量是否有颜色 (j)，答案是：
[sum |A_m|cdot|C_m|=|AC|
]
因为首先要求选出来的 (m) 个向量满秩，前一个行列式就是 (1)；再要求选出来的向量包含了所有颜色，也就是 (C_m) 满秩那么后一个行列式是 (1)，当两个条件同时成立的时候产生 (1) 的贡献。
那么简单矩乘 (+) 高斯消元求行列式即可。
三、总结
主要是比内柯西公式的运用，这道题主要是选出的向量一定是 (m) 个，正好契合了此公式。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 505;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int tp,n,m,a[M][M],b[M][M],c[M][M];
int gauss(int n,int p)
{
int ans=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
if(!c[i][i] && c[j][i])
{
ans=ans*(p-1)%p;
swap(c[i],c[j]);
break;
}
ans=ans*c[i][i]%p;
for(int j=1;j<=n;j++)
{
if(i==j || !c[j][i]) continue;
int t=c[j][i]*c[i][i]%p;
for(int k=1;k<=n;k++)
c[j][k]=(c[j][k]-t*c[i][k]%p+p)%p;
}
}
return ans;
}
void work1()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[j][i]=b[i][j]=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
c[i][k]=(c[i][k]+a[i][j]*b[j][k])%3;
printf("%d
",gauss(m,3));
}
void work2()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
a[j][i]=read();
b[i][read()]=1;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
c[i][k]=(c[i][k]+a[i][j]*b[j][k])%2;
printf("%d
",gauss(m,2));
}
signed main()
{
tp=read();n=read();m=read();
if(tp==1) work1();
else work2();
}