题解 | #Fluorescent 2#

C - Fluorescent 2

首先将三次方转化一下，设进行操作后，第 $i$ 个位置的开关情况为 $x_i$ （ $x_i = 0$ 表示关， $x_i = 1$ 表示开），那么三次方就变成了：

\sum_S\left(\sum\limits_{i = 1} ^ n x_i\right) ^ 3 = \sum_S\sum_{1\le i, j, k\le n} x_ix_jx_k

再转化一下：

\sum_S\sum_{1\le i, j, k\le n} x_i x_j x_k = \sum_S\left(\left(\sum\limits_{1\le i\le n} x_i\right) + 6\left(\sum\limits_{1\le i< j\le n} x_i x_j\right) + 6\sum\limits_{1\le i<j<k\le n} x_i x_j x_k\right)

对三项分别计算即可。

先计算第一项，枚举每一项 $i$ ，发现这时只和字符串第 $i$ 列有关，如果该列全为 $0$ ，则方案数为 $2 ^ n$ 。

接下来考虑存在至少一个 $1$ 的情况，可以先选一个 $1$ ，设其在第 $t$ 行，那么另外 $n - 1$ 个位置任意选或不选，选择完毕后如果开关开了，那么就可以不选第 $t$ 行，反之就选，所以方案数为 $2 ^ {n - 1}$ 。

接下来计算第二项，这里可以枚举 $i$ 和 $j$ ，接下来为了方便，设第 $i$ 列形成的二进制数为 ${bit}_i$ ，并且由于后面的方案数计算和计算第一项时类似，就不展开了，只给结论。

${bit}_i = {bit}_j = 0$ ，方案数为 $2 ^ n$ .
${bit}_i \neq 0, {bit}_j = 0$ ，方案数为 $2 ^ {n - 1}$ .
${bit}_i = {bit}_j \neq 0$ ，方案数为 $2 ^ {n - 1}$ .
${bit}_i \neq 0, {bit}_j \neq 0, {bit}_i \neq {bit}_j$ ，方案数为 $2 ^ {n - 2}$ .

然后是第三项，继续分类讨论，实现（计算每种情况的个数）见代码：

${bit}_i = {bit}_j = {bit}_k = 0$ ， $2 ^ n$ .
${bit}_i \neq 0, {bit}_j = {bit}_k = 0$ ， $2 ^ {n - 1}$ .
${bit}_i = {bit}_j \neq 0, {bit}_k = 0$ ， $2 ^ {n - 1}$ .
${bit}_i, {bit}_j\neq 0, {bit}_k = 0, {bit}_i \neq {bit}_j$ ， $2 ^ {n - 2}$ .
${bit}_i = {bit}_j = {bit}_k \neq 0$ ， $2 ^ {n - 1}$ .
${bit}_i, {bit}_j, {bit}_k$ 互不相等，都不为 $0$ ， ${bit}_i \oplus {bit}_j = {bit}_k$ ， $2 ^ {n - 2}$ .
${bit}_i = {bit}_j \neq 0, {bit}_k \neq 0$ ， $2 ^ {n - 2}$ .
${bit}_i, {bit}_j, {bit}_k$ 互不相等，都不为 $0$ ， ${bit}_i \oplus {bit}_j \neq {bit}_k$ ， $2 ^ {n - 3}$ .

int n, m; char s[N][M]; ll bit[M]; bool F[M];
map<ll, int> mp; mint pw[N], C[M][M];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int lim = 51;
	pw[0] = 1;
	forn (i, 1, lim) pw[i] = pw[i - 1] * mint(2);
	lim = 1000;
	C[0][0] = 1;
	forn (i, 1, lim) {
		C[i][0] = 1;
		forn (j, 1, lim) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}
	while (cin >> n >> m) {
		mp.clear();
		rep (i, 0, n) cin >> s[i];
		rep (j, 0, m) {
			bit[j] = 0;
			rep (i, 0, n) bit[j] = bit[j] << 1 | ((int)s[i][j] - int('0'));
			if (mp.count(bit[j])) F[j] = 0;
			else F[j] = 1;
			mp[bit[j]] ++ ;
		}
		mint ans = 0;
		// case 1 单个数字
		rep (i, 0, m) 
			if (bit[i]) ans += pw[n - 1];
			else ans += pw[n];
		// case 2 两个数字
		rep (i, 0, m) rep (j, i + 1, m) 
			if (!bit[i] && !bit[j]) 
				ans += mint(6) * pw[n];
			else if (!bit[i] || !bit[j] || (bit[i] == bit[j])) 
				ans += mint(6) * pw[n - 1];
			else 
				ans += mint(n >= 2) * mint(6) * pw[n - 2];
		// case 3 三个数字
		mint cnt = C[m][3]; int n0 = 0;
		// case 3.1 bit[i] = bit[j] = bit[k] = 0
		if (mp.count(0ll)) {
			n0 = mp[0];
			cnt -= C[n0][3];
			ans += mint(6) * C[n0][3] * pw[n];
		}
		// case 3.2 bit[i] != 0, bit[j] = bit[k] = 0
		rep (i, 0, m) if (bit[i] && F[i]) //#
			ans += mint(6) * C[n0][2] * mint(mp[bit[i]]) * pw[n - 1],
			cnt -= C[n0][2] * mint(mp[bit[i]]);
		// case 3.3 bit[i] != 0, bit[j] != 0, bit[k] = 0 \and bit[i] = bit[j]
		rep (i, 0, m) if (bit[i] && F[i]) //#
			ans += mint(6) * C[mp[bit[i]]][2] * mint(n0) * pw[n - 1],
			cnt -= C[mp[bit[i]]][2] * mint(n0);
		// case 3.4 bit[i] != 0, bit[j] != 0, bit[k] = 0 \and bit[i] != bit[j]
		rep (i, 0, m) rep (j, i + 1, m) //#
			if (bit[i] && bit[j] && bit[i] != bit[j])
				ans += mint(n >= 2) * mint(6) * mint(n0) * pw[n - 2],
				cnt -= mint(n0);
		// case 3.5 bit[i] = bit[j] = bit[k] != 0;
		rep (i, 0, m) if (bit[i] && F[i]) //#
			ans += mint(6) * C[mp[bit[i]]][3] * pw[n - 1],
			cnt -= C[mp[bit[i]]][3];
		// case 3.6 bit[i], bit[j], bit[k] 互不相等，都不为零 bit[i] ^ bit[j] == bit[k]
		int cur = 0;
		rep (i, 0, m) rep (j, i + 1, m) // # 
			if (bit[i] && bit[j] && mp.count(bit[i] ^ bit[j]) && (bit[i] ^ bit[j]))
				ans += mint(2) * mint(n >= 2) * mp[bit[i] ^ bit[j]] * pw[n - 2], 
				cur += mp[bit[i] ^ bit[j]];
		cur /= 3, cnt -= mint(cur);
		// case 3.7 bit[i] = bit[j] != 0, bit[k] != 0
		rep (i, 0, m) if (bit[i] && F[i])
			ans += mint(6) * mint(n >= 2) * C[mp[bit[i]]][2] * mint(m - n0 - mp[bit[i]]) * pw[n - 2],
			cnt -= C[mp[bit[i]]][2] * mint(m - n0 - mp[bit[i]]);
		// case 3.8 bit[i], bit[j], bit[k] 互不相等，都不为零 bit[i] ^ bit[j] != bit[k]
		if (n >= 3) ans += mint(6) * cnt * pw[n - 3];
		cout << ans.r << '\n';
	}
	return 0;
}