大家安安 o'_'o

小弟不才，最近在學 DFS，所以看到什麼體木都想 DFS 看看，就像 c440. Bert Love QQ ! 我也先用 DFS 找子序列，當然是 NA 惹，結果發現可以用乘法原理來解。

但是這題真的 hen 像 a981. 求和問題 ，只是條件改成 !(sum % k)，而且找到一個就停。

C++:

#include <iostream>
#include <vector>
using namespace std;
using ivec = vector<long>;
long n, k;
ivec v, w;
bool dfs(long i, long sum)
{
	if (!(sum % k) && sum)
	{
		cout << w.size() << endl;
		for (int i : w)
			cout << i << ' ';
		cout << '\n';
		return true;
	}
	if (i >= n)
		return false;
	if (dfs(i + 1, sum))
		return true;
	w.push_back(i + 1);
	if (dfs(i + 1, sum + v[i]))
		return true;
	w.pop_back();
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	v = ivec(n);
	for (long &i : v)
		cin >> i;
	if (!dfs(0, 0))
		cout << "0";
	return 0;
}

但是 #6 測資點一直過不了。感覺題目如果要玩應該會出在 7, 8, 9, 10 欸

可以請大家幫我看看是遞迴哪裡有誤，或有什麼比較好的解法，感謝！

我的做法是先將每隻鴿子的分數取k的餘數，然後排序。

再用dfs去找總合為k的編號(記得減枝)。

不過這不是最佳解。(19 ms, 8.7 MB)

首先感謝回答

請問該如何減枝？和的話就在 sum > k 時即終止。但是取餘數不知道什麼情況下一定不可能？

再次感謝

我照著討論區的刻可以通過，所以剪枝沒有問題。

主要差異是在你的DFS 選取，你可以看一下 code 是枚舉每隻鴿子選或不選，一隻一隻決定要不要選取 <- TLE 的主因

那該怎麼選取呢？選取方式應該是用 for() 迴圈從現在的範圍內選一個之後呼叫下一次的遞迴時縮小範圍。

比如說一開始全部都可以選(0,N-1) 現在選取第一隻鴿子時下一次可以選取範圍則是(2,N-1)

令 $\color{black}{S_i}$ 為前 $\color{black}{i}$ 個數字之和，能定義出 $\color{black}{S_0 \sim S_n}$ 這 $\color{black}{n + 1}$ 個前綴。依據鴿籠原理，在模 $\color{black}{k \le n}$ 時至少有兩前綴同餘。而 $\color{black}{S_a \equiv S_b \pmod k (a < b)}$ 自然代表 $\color{black}{(a, b]}$ 是一組解了。整體能在線性時間下解決。