效率
时间复杂度：\(O(Tn\times 3^9\times 9)\)。
没有任何卡常，能在 \(1.08\)s 内过 hack.txt，而 CHJ 的代码在同样情况下跑了 \(39\)s，LZY 要用 \(34\)s，PWX 要用 \(75\)s。
但是在 GMOJ 上要用 \(770\)ms，是目前比较劣的解。
思路
以下关于数字的第几位都是从 \(0\) 开始，从最低位到最高位编号，例如数据中 \(a_i\) 的最大值最高位是第 \(8\) 位。用 & 表示位运算中的与。
极小正交子集中，所有数的 & 是 \(0\)，每一个数都至少有一个二进制位是集合中唯一一个该位是 \(0\) 的。
比如 3 5 6 中，\(3\) 的第 \(2\) 位是 \(0\)，\(5\) 的第 \(1\) 位是 \(0\)，\(6\) 的第 \(0\) 位是 \(0\)。
这是因为，如果有一个数，它没有这样的一位，那么把它去掉其余数的 & 仍然是 \(0\)。
那么钦定一些数没有这样的一位，也就相当于钦定 & 的某一位有至少一个数这一位是 \(0\)。
设钦定的数集合为 \(X\)，那么它的容斥系数是 \((-1)^{|X|}\)。
设 \(f_{i,S}\) 表示现在处理了前 \(i\) 个数，现在的状态是 \(S\)，的结果，其中 \(S\) 的第 \(j\) 位对应选了的数的 & 在二进制下的第 \(j\) 位，意义如下：
- 0：当前
&的第 \(j\) 位是 \(1\)。 - 1：当前
&的第 \(j\) 位是 \(0\)，钦定有至少两个数这一位是 \(0\)，但现在只有一个数这一位是 \(0\)，这意味着，还要再加多一个这一位是 \(0\) 的数才满足钦定。 - 2：当前
&的第 \(j\) 位是 \(0\)，且满足约束条件，这有两种情况：钦定有至少两个数这一位是 \(0\)，且已经满足条件；不钦定有几个数这一位是 \(0\)。
把 \(f_{i-1,S}\) 转移给 \(f_{i}\)，还是分三种情况：
- 不选 \(a_{i}\)：转移到 \(f_{i,S}\)。
- 选 \(a_{i}\)，且钦定它在集合 \(X\) 里：枚举 \(a_i\) 的每一位，如果是 \(0\)，就可以用来改变 \(S\) 的对应位：如果 \(S\) 的这一位是 \(0\)，就改为 \(1\)，因为没满足钦定条件；如果 \(S\) 的这一位是 \(1\) 或者 \(2\)，就改为 \(2\)，因为已经满足了钦定条件。转移的时候要乘 \(-1\) 的容斥系数。
- 选 \(a_{i}\)，且不钦定它在集合 \(X\) 里：同样地枚举 \(a_{i}\) 的每一位，如果是 \(0\)，就可以改变 \(S\) 的对应位：把这一位改成 \(2\)，因为这一位已经满足了条件。容斥系数为 \(1\)。
这样子，状态数是 \(3^9\) 个，因为 \(a_{i}\) 最多有 \(9\) 位，总的时间复杂度是 \(O(Tn\times 3^9 \times 9)\)。
代码
点击开 D
const int N=105,A=512,L=12,TOT=19683,moder=998244353;
int T,n,a[N]={},pow3[L]={1},f[N][TOT]={};
int main()
{
usefile("ov");
int i,S,j,nS;
for(i=1;i<L;++i) pow3[i]=pow3[i-1]*3;
read(T);
loop : --T;
read(n);
for(i=0;i<n;++i)
read(a[i]);
memset(f,0,(n+2)*sizeof(f[0]));
f[0][0]=1;
for(i=0;i<n;++i)
for(S=0;S<pow3[9];++S)
if(f[i][S]) {
// 不选
Add(f[i+1][S],f[i][S]);
// 钦定为 X
for(j=0,nS=S;j<9;++j)
if(a[i]>>j&1) ;
else if(S/pow3[j]%3==2) ;
else nS+=pow3[j];
Sub(f[i+1][nS],f[i][S]);
// 钦定不为 X
for(j=0,nS=S;j<9;++j)
if(a[i]>>j&1) ;
else nS=nS+(2-S/pow3[j]%3)*pow3[j];
Add(f[i+1][nS],f[i][S]);
}
printf("%lld\n",f[n][pow3[9]-1]);
if(T) goto loop;
return 0;
}