[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

时间限制：2000MS 内存限制：262144KB

难度：$5.2$

• 题目描述

给定一个长度为 $n$ 的非负整数序列 $a$ 和一个正整数 $m$ 。

现在有 $q$ 组询问，每组询问给定两个正整数 $l, r$ ，每次可以选择满足 $l \leq i \leq r$ 的若干个 $a_i$ （也可以一个都不选），使得这些 $a_i$ 的和是 $m$ 的非负整数倍，并输出满足条件的选择方案数对 $10^9+7$ 取模后的余数。

• 输入格式

第一行为两个正整数 $n$ 和 $m$ 。

第二行为序列 $a$ ，共 $n$ 个元素，用一个空格隔开。

第三行为询问数 $q$ 。

接下来的 $q$ 行，每一行都有两个正整数，分别为 $l$ 和 $r$ 。

• 输出格式

共 $q$ 行。

第 $i$ 行为第 $i$ 组询问的答案。

• 样例输入

• 样例输出

• 样例说明

对于第一组询问 $l=1, r=2$ ，有 不选、选择 $5, 1$ ，共 $2$ 种情况。

对于第二组询问 $l=1, r=3$ ，有 不选、选择 $5, 1$ 、选择 $5, 1, 3$ 、选择 $3$ ，共 $4$ 种情况。

对于第三组询问 $l=1, r=4$ ，有 不选、选择 $5, 1$ 、选择 $5, 1, 3$ 、选择 $3$ 、选择 $1, 2$ 、选择 $1, 3, 2$ ，共 $6$ 种情况。

对于第四组询问 $l=2, r=4$ ，有 不选、选择 $3$ 、选择 $1, 2$ 、选择 $1, 3, 2$ ，共 $4$ 种情况。

• 数据范围

对于 $10\%$ 的数据，有 $1 \leq n, q \leq 10$ 。

对于 $40\%$ 的数据，有 $1 \leq n, q \leq 1000$ 。

对于 $100\%$ 的数据，有 $1 \leq n, q \leq 2 \times 10^5$，$1 \leq m \leq 20$，$0 \leq a_i \leq 10^9$ 。

保证每组询问的 $l, r$ 满足 $1 \leq l \leq r \leq n$ 。

 

 

YZOJ P4199

$Source$: [2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest] J. Subsequence Sum Queries

---

 

 

 

（注：以下的取模操作均在非负整数意义下。）

最暴力的做法就是对于每一个询问的区间暴力做一遍背包计数，容量就变成 $\bmod m$ 的余数 $0$ ~ $(m-1)$ 了。转移就是 \(f_{i, j}=f_{i-1, j}+f_{i-1, (j-a_i)\%m}\) ，表示 $a_i$ 不选和选的情况数之和。这样的复杂度可以达到 $O(nmq)$ 是无法承受的。

还可以想到线段树进行背包合并，但是这样的复杂度为 $O((n+q)m^2logn)$ ，会 TLE 。

所以想到进行分治。（以下所有 $mid=\lfloor\frac{l+r}{2}\rfloor$）

首先离线处理询问，然后考虑区间 $[l, r]$ 如何对这个询问产生贡献。首先，如果这个询问区间完全在 $[l, mid-1]$ 中，那么先不用处理它，在递归进 $[l, mid-1]$ 时处理就好了（注意，区间端点 $=mid$ 的会在下面进行处理）。同样如果这个询问区间完全在 $[mid+1, r]$ 中也是同理。

如果这个询问区间跨过了 $mid$ （$l \leq ql \leq mid \leq qr \leq r$），那么这个询问的答案就可以被处理出来。注意因为 $[l, r]$ 被分割成了 $[l, mid]$ 和 $[mid+1, r]$ 这两个子区间，所以询问区间 $[ql, qr]$ 也可以被分割成两个子区间 $[ql, mid]$ 和 $[mid+1, qr]$ 。要快速的合并，所以对 $[mid+1, r]$ 中的元素做一遍正向DP设得到 $f$ 数组，对 $[l, mid]$ 中的元素做一遍反向DP设得到 $g$ 数组，这样 $f$ 和 $g$ 合并就可以得到跨过 $mid$ 的一段区间的完整的答案了。合并的时候就直接把 $f$ 中的方案数和 $g$ 中的方案数相乘即可，即 $[ql, qr]$ 这个询问的答案是 $\sum\limits_{j+k=m}{f_{qr, j} \times g_{ql, k}}$ 。

这样处理下去，时间复杂度只有 $O(m(nlogn+q))$ 足以通过本题。