题意简化

布尔函数 $f: \{0,1\}^n \rightarrow \{0,1\}$。

定义四个集合：

• $Z$: $f(0,\dots,0)=0$
• $P$: $f(1,\dots,1)=1$
• $D$: $f(\neg x_1,\dots,\neg x_n) = \neg f(x_1,\dots,x_n)$
• $A$: 仿射函数（线性函数+常数）

给定表达式（包含 ZPDA^v!()\），求对应集合中的布尔函数数量，模 $1000003$。

$n, L \le 100$。

核心思想：位掩码表示 + 容斥

1. 布尔函数的分类

对于 $n$ 个变量的布尔函数，共有 $2^{2^n}$ 个。

四个集合 $Z,P,D,A$ 及其组合可以用16种等价类表示。

2. 等价类表示

设 $f$ 在四个性质上的取值：

• 是否满足 $Z$（$f(0)=0$）
• 是否满足 $P$（$f(1)=1$）
• 是否满足 $D$（自对偶）
• 是否满足 $A$（仿射）

共 $2^4=16$ 种组合，每种对应一个等价类。

3. 代码实现

预处理 f[] 数组

f[i] 表示第 $i$ 个等价类中的布尔函数数量。

计算公式：

• 总函数数：$2^{2^n}$
• 满足单个条件的函数数：$2^{2^{n-1}}$ 等
• 使用容斥原理计算交集大小

具体值：

• f[0]: $2^{2^n}$
• f[1], f[2]: $2^{2^{n}-1}$
• f[3]: $2^{2^{n}-2}$
• f[4]: $2^{2^{n-1}}$
• f[5], f[6], f[7]: $2^{2^{n-1}-1}$
• f[8]: $2^{n+1}$
• f[9], f[10], f[12]: $2^n$
• f[11], f[13], f[14], f[15]: $2^{n-1}$

id[] 数组

id[0]：$Z$ 集合对应的等价类掩码（哪些等价类满足 $Z$） id[1]：$P$ 集合对应的掩码 id[2]：$D$ 集合对应的掩码
id[3]：$A$ 集合对应的掩码

4. 表达式解析

递归解析表达式：

• ( ... )：括号内表达式
• !：补集，对应位掩码取反（all ^ x）
• Z,P,D,A：基础集合
• ^：交集，位与（&）
• v：并集，位或（|）
• \：差集，x ^ (x & y)

5. 最终计算

解析得到结果掩码 x，表示哪些等价类在集合中。 答案 = $\sum_{i \in x} f[i]$。

数学推导

1. 布尔函数计数公式

总函数数：$2^{2^n}$

单条件计数：

• $Z$（$f(0)=0$）：固定一个值，$2^{2^n-1}$
• $P$（$f(1)=1$）：同样 $2^{2^n-1}$
• $D$（自对偶）：$f(x) = \neg f(\neg x)$，$2^{2^{n-1}}$
• $A$（仿射）：$f(x)=a_0 \oplus \sum a_i x_i$，共 $2^{n+1}$ 个

多条件交集：

使用容斥原理计算。

2. 模数处理

模数 $M=10^6+3$ 是质数，可用费马小定理求逆。

注意指数要对 $M-1$ 取模（欧拉定理）。

样例解释

$n=2$，表达式 Z

• $Z$ 集合：$f(0,0)=0$
• 总函数数：$2^{2^2}=16$
• 满足 $f(0,0)=0$ 的函数数：$2^{16-1}=8$

输出：8

算法步骤

1. 预处理：

   • 计算16个等价类的函数数量 f[]
   • 计算四个基础集合的位掩码 id[]

2. 表达式解析：

   • 递归解析表达式
   • 用位掩码表示集合

3. 计算答案：

   • 根据结果掩码求和 f[i]

复杂度

• 预处理：$O(16^2)$
• 表达式解析：$O(L)$
• 可过 $n,L \le 100$

关键点

1. 将集合运算转化为位运算
2. 16种等价类完全分类
3. 容斥计算函数数量
4. 模运算处理大指数

代码特点

• 位掩码技巧
• 递归下降解析器
• 模运算优化
• 快速幂处理大指数