题解：P1329 数列

设

dp_{i,j}

表示

\sum_{k=1}^i a_k=j

的方案数。转移是平凡的，与背包问题类似。

暴力的做法：假设所有数都是前一个数加一，即构造

a_i=i-1

，总和就是

n(n-1)/2

。将

a_i

减

2

会使所有数总和减少

2(n-i+1)

，所以目标就是用不同的

(n-i+1)

凑出

goal=s-n(n-1)/2

。这么做时间复杂度是

O(2^n)

的，但可以用来输出方案（所以就出现了一道题正解中同时使用正解和暴力做法的情况）。

CPP

const ll N = 2000, S = 6000;
const lll mod = (lll)(1) << 64;
lll dp[N][S];
ll n, s, goal, cnt, ch[N];

void dfs(ll p, ll cur) {
	if (cur > goal)
		return;
	elif(p > n) {
		if (cur == goal) {
			cnt++;
			ll sum = 0;

			rep(i, 1, n) {
				sum += ch[i];
				cout << sum << ' ';
			}

			endl;

			if (cnt >= 100)
				exit(0);
		}
	} else {
		ch[p] = -1;
		dfs(p + 1, cur + (n - p + 1));
		ch[p] = 1;
		dfs(p + 1, cur);
	}
}

int main() {
	cin >> n >> s;

	if (abs(s) > n * (n - 1) / 2 or (n * (n - 1) / 2 - s) % 2) {
		cout << 0;
		return 0;
	}

	goal = (n * (n - 1) / 2 - s) / 2;
	dp[1][0] = 1;

	rep(i, 2, n) {
		ll dis = n - i + 1;
		cpy(dp[i], dp[i - 1]);

		rep(j, dis, S - 1) (dp[i][j] += dp[i - 1][j - dis]) %= mod;
	}

	cout << (ull)(dp[n][goal]) << '\n';
	dfs(2, 0);
}

代码宏定义在我个人空间自取。

文章操作

相关推荐

评论

题解：P1329 数列