GitHub 源文件 Markdown English

动态二进制约束计数

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事

计数终端保存五个二进制上界。操作员每次翻转其中一位，终端就统计符合基础要求的数对分别满足几个额外条件。

(本故事由GPT-6重写)

形式化问题描述

五个长度均为 \(n\) 的二进制串按从高位到低位的顺序表示非负整数 \(A,B,C,D,E\) ，允许前导零。

考虑所有非负整数有序对 \((a,b)\) ，要求始终满足 \(a\le A\) 且 \(b\le B\) .另有三个条件：

\[ a\mathbin{\&}b\le C,\qquad a\mathbin{\oplus}b\le D,\qquad a\mathbin{|}b\le E. \]

其中 \(\&\) 、\(\oplus\) 、\(|\) 分别表示逐位与、异或、或。

每次操作翻转指定串的一位。初始时及每次操作后，分别输出恰好满足三个额外条件中的零、一、二、三条的有序对数目，对 \(998244353\) 取模。

输入格式

第一行两个整数 \(n,m\) .接下来五行依次给出 \(A,B,C,D,E\) 的二进制串。接下来 \(m\) 行，每行两个整数 \(x,y\) ，将第 \(x\) 个串从低位到高位、即从右向左数的第 \(y\) 位翻转。串编号为一到五，位编号从一开始。

输出格式

输出 \(m+1\) 行，每行四个整数，依次为恰好满足零、一、二、三条额外条件的数对数目模 \(998244353\) .第一行对应初始状态，随后各行对应每次修改后的状态。

样例

样例 1

输入

2 3
11
10
00
01
10
3 1
1 2
5 2

输出

1 4 4 3
0 5 3 4
0 1 1 4
0 2 3 1

样例 2

输入

1 0
0
0
0
0
0

输出

0 0 0 1

样例 3

输入

3 2
111
111
111
111
111
4 3
4 3

输出

0 0 0 64
0 0 32 32
0 0 0 64

样例解释

样例一初始有 \((3+1)(2+1)=12\) 个可选数对，四类计数之和为十二。样例二只有 \((0,0)\) ，满足全部额外条件。样例三初始六十四个数对均满足三条；将 \(D\) 从七改成三后，三十二个满足两条，三十二个满足三条，再次翻转后恢复。

数据范围与保证

\(1\le n\le10000\) ，\(0\le m\le10000\) ，\(1\le x\le5\) ，\(1\le y\le n\) .字符串只含零和一。

分值比例	额外条件
100%	无额外条件