Description：

$n$ 个灯，每个开关会使一些特定的灯改变状态，问最多能使所有灯有几种不同的状态。

$1\leqslant n,m\leqslant 50$

Solution：

发现其实就是给你一些数，询问他们随便异或能异或出多少个数，异或不难想到线性基，那么由整个集合的异或空间等价于线性基的异或空间可以知道我们只要求出线性基能异或多少个数就行了，由于线性基任意两个向量线性无关所以不存在一种方式可以用两种方法异或出同一个数，或者可以理解为一个 $n$ 维空间下线性独立的 $n$ 个向量随意组合不可能有两种方式组合出同一个向量，所以答案就是 $2$ 的线性基内元素个数次方，每次插入时如果插入成功答案乘 $2$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

char getc()

{

	char c = getchar();

	while(c != 'O' && c != 'X')c = getchar();

	return c;

}

typedef long long ll;

struct LinearBase

{

	ll d[50];

	int cnt;

	LinearBase(){cnt = 1;}

	void add(ll x)

	{

		for(int i = 49;i >= 0;--i)

		{

			if((x >> i) & 1)

			{

				if(d[i] == 0)

				{

					cnt = cnt * 2 % 2008;

					d[i] = x;

					break;

				}

				else

				{

					x ^= d[i];

				}

			}

		}

		return;

	}

}s;

int main()

{

	scanf("%d%d",&m,&n);

	for(int i = 1;i <= n;++i)

	{

		ll k = 0;

		for(int j = 0;j < m;++j)

		{

			if(getc() == 'O')

			{

				k ^= (1ll << j);

			}

		}

		s.add(k);

	}

	cout << s.cnt << endl;

	return 0;

}