当前位置：首页 > news >正文

F - Not Adjacent

news 2026/5/12 0:56:56

F - Not Adjacent

Problem Statement

You are given a length-$N$ integer sequence $A=(A _ 1,A _ 2,\ldots,A _ N)$.

There are $2 ^ N$ (not necessarily contiguous) subsequences of $A$. Find how many subsequences $(A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N)$ satisfy both of the following two conditions:

The selected elements are not adjacent in $A$. That is, $1+i _ j\ne i _ {j+1}$ holds for all $1\le j\lt k$.
The sum is a multiple of $M$. That is, $\displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M$.

Even if two subsequences are equal as integer sequences, they are counted separately if the positions from which they are taken are different.

Constraints

$1\le N\le60$
$1\le M\le10 ^ 9$
$0\le A _ i\lt M$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$

Output

Print the answer.

Sample Input 1

7 6
3 1 4 1 5 3 2

Sample Output 1

The following six subsequences satisfy the conditions:

$()=()$
$(A _ 1,A _ 3,A _ 5)=(3,4,5)$
$(A _ 1,A _ 4,A _ 7)=(3,1,2)$
$(A _ 1,A _ 6)=(3,3)$
$(A _ 2,A _ 5)=(1,5)$
$(A _ 3,A _ 7)=(4,2)$

Thus, print 6.

Sample Input 2

15 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

Sample Output 2

Sample Input 3

20 998244353
778718481 719092922 676292280 713825156 0 434453766 620370916 67922064 0 577696866 21516423 955580612 955580612 0 332156721 0 0 0 632133714 500614291

Sample Output 3

解题思路

首先 $m$ 非常大，意味着常规的 dp 做法是行不通的。而 $n$ 却很小，因此本题做法大概率是需要暴力枚举的，但我们不可能直接把所有的子序列枚举出来。因为我们只关心子序列的和，实际上可以将问题转化为求子序列和的和（子序列可以拆开多个部分分别求和）。可以考虑 meet-in-the-middle 这一方法，将子序列看作由数组左半部分的子序列与右半部分的子序列组合而成。我们首先计算左半部分和右半部分所有合法子序列的和，然后枚举左半部分的所有子序列，并在右半部分中寻找符合条件的子序列，即组合得到的子序列的和是 $m$ 的倍数。

下面考虑如何求解原数组左半部分所有子序列的和（右半部分同理）。由于只需考虑数组的一半，此时元素数量最多为 $30$，因此子序列数量的上限为 $2^{30}$，但具体数量多少呢？我们可以用 dp 的方法来解决这个问题，假设 $f_i$ 表示从前 $i$ 个元素中选出不相邻元素所构成的子序列数量，根据是否选择第 $i$ 个元素进行状态划分，有转移方程 $f_i = f_{i-1} + f_{i-2}$，且有初始状态 $f_{0}=1, f_{1}=2$。值得注意的是，这个转移方程实际上就是斐波那契数列的递推关系（这也是官方题解中提到斐波那契的原因）。根据递推公式，$f_{30} = 2178309$，这意味着合法的子序列数量大约为 $10^6$ 级别，完全可以通过暴力搜索找到。

还有一些细节需要处理。我们将原数组的左半部分（$a_{1} \sim a_{\left\lfloor n/2 \right\rfloor}$）的所有子序列，按照是否以 $a_{\left\lfloor n/2 \right\rfloor}$ 为最后一个元素，分成两类，同理，原数组的右半部分（$a_{\left\lfloor n/2 \right\rfloor + 1} \sim a_{n}$）的所有子序列，也可以根据是否以 $a_{\left\lfloor n/2 \right\rfloor + 1}$ 为第一个元素，分成两类。为什么要这么做呢？这是因为如果我们选择左半部分中以 $a_{\left\lfloor n/2 \right\rfloor}$ 为最后一个元素的子序列，那么右半部分就不能选择以 $a_{\left\lfloor n/2 \right\rfloor + 1}$ 为第一个元素的子序列（同理，对于另一种情况亦然）。

具体做法是，首先暴搜 $a_{1} \sim a_{\left\lfloor n/2 \right\rfloor}$ 中的所有子序列和，并用一个哈希表记录每个和的出现次数。同时，我们根据是否以 $a_{\left\lfloor n/2 \right\rfloor}$ 为最后一个元素，将子序列分成两类。然后，暴搜 $a_{\left\lfloor n/2 \right\rfloor + 1} \sim a_{n}$ 中所有子序列的和，对于每个和 $s$（同样需要区分子序列是否以 $a_{\left\lfloor n/2 \right\rfloor + 1}$ 为第一个元素），在哈希表中查找 $(m-x) \bmod m$ 的出现次数。这个次数表示左半部分有多少个子序列与右半部分某个子序列组合，能够得到总和为 $m$ 的倍数的子序列。

最后需要注意的是，哈希表应选择 std::unordered_map，如果选择 std::map 会超时。

另外 F - Path to Integer 也用到了本题的思想，且代码也非常类似。

AC 代码如下，时间复杂度为 $O\left(n \left(\frac{1 + \sqrt{5}}{2}\right)^n \right)$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 65;int n, m;
int a[N];
unordered_map<int, int> mp[2];void dfs1(int u, int s, int bnd, int is_bnd) {if (u > bnd) {mp[is_bnd][s]++;return;}dfs1(u + 1, s, bnd, is_bnd);dfs1(u + 2, (s + a[u]) % m, bnd, u == bnd);
}LL dfs2(int u, int s, int bnd, int is_bnd) {if (u < bnd) {s = (m - s) % m;if (is_bnd) return mp[0][s];return mp[0][s] + mp[1][s];}return dfs2(u - 1, s, bnd, is_bnd) + dfs2(u - 2, (s + a[u]) % m, bnd, u == bnd);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i];}dfs1(0, 0, n / 2, 0);cout << dfs2(n - 1, 0, n / 2 + 1, 0);return 0;
}