思路

题解区的题解都多多少少有些错误。

我想写一写我的做法，是将题解区各大佬的做法综合起来的做法。

首先，假如每一个数字都比前面的一个数字大 $1$，即数列为 $0, 1, 2, 3, 4, 5, \dots, n - 1$，那么这个数列的和为 $sum = \frac{n(n - 1)}{2}$，我们发现 $n \le 100$，那么 $sum \le 4950$，所以如果题目要求的 $s > sum$，那么一定无解，因为这个数列再大也大不过 $sum$，更不可能到达 $s$ 了。

反过来，如果一个数字比前面一个数字小 $1$，即数列为 $0, -1, -2, -3, -4, -5, \dots, -(n - 1)$，那么这个数列的和为 $sum = -\frac{n(n - 1)}{2}$，我们发现 $n \le 100$，那么 $sum \ge -4950$。

所以 $-2^{63} \le s \le 2^{63}$ 是吓你的，真正有用的 $-4950 \le s \le 4950$。

接下来，我们来探究一个位子 $u$ 上的数字变化对数组的和 $sum$ 的影响。

如果 $a_u = a_{u - 1} + 1$，现在改成 $a_{u} = a_{u - 1} - 1$，那么从 $u$ 开始的每一个数字都会减去 $2$。

那么数组的和 $sum$ 就会减去 $2(n - u + 1)$。

那么，我们可以想到让每一个数字都等于前面一个数字 $+1$，那么和就是 $\frac{n(n - 1)}{2}$。

但是我们想让其变为题目要求的 $s$，那么要减去的数字就是 $k = \frac{n(n - 1)}{2} - s$。

那么我们只能将有些数字间的 $+1$，换成 $-1$ 才能达到减去 $k$ 的目的。

那么根据前面对数字间关系的讨论，我们知道，我们要凑出很多个 $i$，使这些 $i$ 对应的 $2(n - i + 1)$ 加起来等于 $k$ 就行了，即让所有的 $n - i + 1$ 加起来等于 $\frac{k}{2}$ 即可。

当然了，如果 $k$ 是奇数，那么一定无解。

我们考虑 DP，设 $f_{i, j}$ 表示已经凑到第 $i$ 个数字，和为 $j$ 的方案数。

开始时：$f_{1, 0} = 1$，

目标：$f_{n, \frac{k}{2}}$。

我们可以不选择第 $i$ 个数字，$f_{i, j} = f_{i - 1, j}$。

我们可以选择第 $i$ 个数字，即在原有基础上加上 $(n - i + 1)$，$f_{i, j} = f_{i - 1, j - (n - i + 1)}$。

然后爆搜 + 剪枝输出方案就可以了，因为最多输出 $100$ 项，所以不用担心会不会超时，当然不剪枝是过不了的。

（相信大家都会）

代码

注意取模！！！

我用了 __int128。

// Problem: P1329 数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1329
// Memory Limit: 128 MB
// Time Limit: 1000 ms


#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using ull = unsigned long long;

const int N = 1010, M = 5010;
const __int128 mod = ((__int128)1 << 64);

ull f[N][M];

int n, k;
i64 s;
int cnt;
int m[N];

void dfs(int u, int sum) {
    if (sum > (k >> 1)) return;
	if (u > n) {
		if (sum == (k >> 1)) {
			cnt++;
			i64 tmp = 0;
			for (int i = 1; i <= n; i++) {
				tmp += m[i];
				cout << tmp << ' ';
			}
			cout << '\n';
		}
		if (cnt >= 100) {
			exit(0);
		}
		return;
	}
	m[u] = -1;
	dfs(u + 1, sum + (n - u + 1));
	m[u] = 1;
	dfs(u + 1, sum);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> s;
	if (s > n * (n - 1) / 2) {
		cout << 0 << '\n';
		return 0;
	}
	k = n * (n - 1) / 2 - s;
	if (k & 1) {
	    cout << 0 << '\n';
	    return 0;
	}
	f[1][0] = 1;
	for (i64 i = 2; i <= n; i++) {
		i64 x = (n - i + 1);
		memcpy(f[i], f[i - 1], sizeof(f[i]));
		for (int j = x; j < M; j++) {
			f[i][j] = ((__int128)f[i][j] + f[i - 1][j - x]) % mod;
		}
	}
	cout << f[n][k >> 1] << '\n';
	dfs(2, 0);
	return 0;
}