P11891 [XRCOI Round 1] B. 稻花香里说丰年

**增加形式化题意。** > 稻花香里说丰年，听取蛙声一片。

稻田里有 $0$, $1$ 两种类型的青蛙。他们排成了 $a,b$ 两列。 Genius_Star 发现了这些青蛙，所以他决定将这两个青蛙队列分别划分为**起止点相同的**任意段，定义某一段的整齐度 $T$ 为： $$ T(l,r) = \sum_{i=l}^r [a_i \ne b_i] $$ 其中 ：$[A]$ 表示若 $A$ 命题为真则为 $1$，否则为 $0$。 则对于段 $[l,r]$ 的带给 Genius_Star 的开心值为 $$ W(l,r) = T(l,r) \times \Big(A(l,r) + B(l,r) \Big) $$ 其中： $A(l,r)$ 表示在 $a$ 序列的 $[l,r]$ 区间中包含的 $01$ 类型的子序列数量。 $B(l,r)$ 表示在 $b$ 序列的 $[l,r]$ 区间中包含的 $10$ 类型的子序列数量。 一个分段方案带给 Genius_Star 的开心值是所有小段带给他的开心值之和，你需要求出所有的分段方案带给他的开心值之和 $s$。 设分为了 $k$ 段，第 $i$ 段为 $[l_i, r_i](l_i \le r_i)$，需要满足： - $l_1 = 1, r_k = n$。 - $\forall i \in[1, k), r_i + 1 = l_{i + 1}$。 则若两个分段的方案不同，当且仅当两个方案分的段数不同或者存在一个 $i$ 使得 $[l_i, r_i] \ne[l'_i, r'_i]$。 由于 Genius_Star 不能过于开心，你还需要将答案对 $10^9+7$ 取模。 ### 形式化题意 给定一个两个序列 $a,b$ 。定义 - $T(l,r)$ 为在区间 $[l,r]$ 中 $a_i\neq b_i$ 的个数。 - $A(l,r)$ 表示 $a$ 序列在 $[l,r]$ 区间中的 $01$ 类型子序列个数。 - $B(l,r)$ 表示 $b$ 序列在 $[l,r]$ 区间中的 $10$ 类型子序列个数。 - $ W(l,r) = T(l,r) \times \Big(A(l,r) + B(l,r) \Big) $。 其中：$xy$ 类型子序列表示从区间左端点开始向右顺次选择两个元素（**不要求连续**），其中，第一个数是 $x$ ，第二个数是 $y$。两个子序列不同当且仅当 $x$ 或 $y$ 所在位置不同。 现在你需要将两个序列划分成**起止点相同的**任意段，求所有划分方式的每段的 $W$ 之和。 由于答案可能很大，你需要将答案对 $10^9+7$ 取模。

无

无

### 样例解释 #1： 只有按照 $[1,3]$ 分段时，$W(1,3)=1$。 ### 样例解释 #4： 可以得到： $$f_1=1,f_2=1,f_3=2$$ $$g_1=1,g_2=1,g_3=3$$ 得到： $$(f_3)_2 = (00010)_2$$ $$(g_3)_2 = (00011)_2$$ 则： $$a = \{0,1,0,0,0\}$$ $$b = \{1,1,0,0,0\}$$ 故答案为 $22$。 ### 数据范围： **本题采用捆绑测试。** 其中子任务 $0$ 为样例，记 $0$ 分。 | Subtask 编号 | $n$ | $op$ | 特殊性质 | 得分 | | :----------: | :-----------------: | :--: | :------: | :--: | | $1$ | $\leq 100$ | $=0$ | 无 | $5$ | | $2$ | $\leq 10^4$ | $=0$ | 无 | $10$ | | $3$ | $\leq 10^6$ | $=0$ | $A$ | $10$ | | $4$ | $\leq 10^6$ | $=0$ | $B$ | $10$ | | $5$ | $\leq 10^6$ | $=1$ | 无 | $25$ | | $6$ | $\leq 5\times 10^7$ | $=1$ | 无 | $40$ | 特殊性质 $A$： $T(l,r) = r-l+1$。 特殊性质 $B$：有且仅有一个 $x$ 满足 $a_x \ne b_x$。 对于 $100 \%$ 的数据，保证 $1 \le n \le 5\times 10^7,1 \le x_1,x_2,y_1,y_2,z_1,z_2,f_1,f_2,g_1,g_2 \le 10^{18}$。