题目大意：求长度为$n$的数列的数目，使得，且，且数列前$n$项和为$S$。同时要求输出字典序最小的至多100个方案。
题解
对于给定的这个条件，需要考虑差分数列。显然，根据条件，差分数列中每一个数只能是$1$或者$-1$。
设$f(i, j)$为到第$i$项为止，为数列贡献的和为$j$的方案数目。转移时考虑第$i$项和第$i-1$项的差分是$1$还是$-1$，可以计算得到这一项的差分对数列总和的贡献为$n-i+1$或者$i-n-1$。从而得到转移方程:
打印方案时先反过来，确定哪些状态是合法的，然后从头开始，一路沿着合法的转移行动即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std;
typedef long long ll;
int n, S, cnt = 0;
ll f[105][10005] = {0};
bool able[105][10005] = {0};
int ans[105] = {0}, aans[105];
void dfs(int cur, int SS){
if(cnt == 100) return ;
if(cur == n + 1){
if(SS == S && cnt < 100){
aans[1] = 0;
for(int i = 1; i < n; ++i)
printf("%d ", aans[i]), aans[i + 1] = aans[i] + ans[i + 1];
printf("%d\n", aans[n]);
cnt++;
}
return ;
}
if(able[cur][SS - (n - cur + 1) + offset])
ans[cur] = -1, dfs(cur + 1, SS - (n - cur + 1));
if(able[cur][SS + n - cur + 1 + offset])
ans[cur] = 1, dfs(cur + 1, SS + n - cur + 1);
}
int main(){
cin >> n >> S;
f[1][0 + offset] = 1;
for(int i = 2; i <= n; ++i){
int lim = (n - 1 + n - i + 1) * (i - 1) / 2;
for(int j = -lim + offset; j <= lim + offset; ++j){
f[i][j] = f[i - 1][j - (n - i + 1)] + f[i - 1][j + (n - i + 1)];
}
}
able[n][S + offset] = true;
for(int i = n; i >= 2; --i){
int lim = (n - 1 + n - i + 1) * (i - 1) / 2;
for(int j = -lim + offset; j <= lim + offset; ++j){
if(able[i][j])
able[i - 1][j + (n - i + 1)] = able[i - 1][j - (n - i + 1)] = true;
}
}
cout << f[n][S + offset] << endl;
dfs(2, 0);
return 0;
}