说要统计方案，感觉就是个 Σ
而矩阵中只有 01 ，可以用二进制表示
这样，预处理出每一个每一行所有可能的状态 s
然后初始化第一行所有状态的方案数为 1
f[i][j] = Σf[i - 1][k] (k 和 j 不冲突，j 为第 i 行所有方案，k 为第 i - 1 行所有方案)
——代码
#include <cstdio>
#include <iostream>
#define mod 100000000 int n, m, ans;
int f[][ << ], pos[][ << ], s[][ << ]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void dfs(int k, int i, int num)
{
if(i > pos[k][])
{
s[k][++s[k][]] = num;
return;
}
dfs(k, i + , num);
if((pos[k][i] ^ (pos[k][i - ] + )) || (i == ))
dfs(k, i + , num + ( << pos[k][i] - ));
else if((i ^ ) && (pos[k][i] == pos[k][i - ] + ))
if(((num >> pos[k][i - ] - ) & ) ^ )
dfs(k, i + , num + ( << pos[k][i] - ));
} int main()
{
int i, j, k, x;
n = read();
m = read();
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
{
x = read();
if(x) pos[i][++pos[i][]] = j;
}
for(i = ; i <= n; i++) dfs(i, , );
for(i = ; i <= s[][]; i++) f[][i] = ;
for(i = ; i <= n; i++)
for(j = ; j <= s[i][]; j++)
for(k = ; k <= s[i - ][]; k++)
if(!(s[i][j] & s[i - ][k]))
{
f[i][j] += f[i - ][k];
if(f[i][j] >= mod) f[i][j] -= mod;
}
for(i = ; i <= s[n][]; i++)
{
ans += f[n][i];
if(ans >= mod) ans -= mod;
}
printf("%d\n", ans);
return ;
}