[P1329] 数列

设f[i,j]为长度为i是，前缀和为j的方案数。

【转移】
f[i,j] => f[i+1,j+i]
f[i,j] => f[i+1,j-i]
【原理】
由于a[0]=0，所以有a[1]=-1或a[1]=1 。又要满足|a[i]-a[i-1]|=1，所以 这样思考：
从f[i,*]转移到f[i+1,*]时，假象在长度为i的a序列后添一个a[i]+1 或a[i]-1。我们惊奇地发现，这样是做不出来的。

怎么办呢？？？

看过题解后我们发现，上述方法不适用的原因是a[n]情况太多了。不方便。 与之相反的是，a[0]={0}，a[1]={1,-1}的情况就很少 。我们何不在a[0]和a[1]中插入一个数构成新序列呢 ？？

举个栗子：当a[1]为1时，在其中插入一个1，为了满足 |a[i]-a[i-1]|=1 的性质，不得不当原来的a[1~i]都加上一个1或-1，即转移到了f[i+1,j+i-1+1] 和 f[i+1,j-i+1-1] 。

还有三种情况，道理相同就不再赘述了。

【输出答案】搜索，利用f数组剪纸就好。
我是真菜啊 。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int n=110;
const int m=20000;

int n,sum,a[n];
long long tot,f[n][m+1];

void print(int x) {
    if(x==1 && !sum) {
        printf("0");
        for(int k=0,i=n; i>1; --i) {
            k+=a[i]; printf(" %d",k);
        }
        printf("\n");
        if(--tot==0) exit(0);
    }
    if(f[x][sum<0?sum+m:sum]==0) return;
    a[x]=-1;
    sum+=(x-1);
    print(x-1);
    sum-=(x-1);
    a[x]= 1;
    sum-=(x-1);
    print(x-1);
    sum+=(x-1);
}

int main() {
    f[1][0]=1;
    scanf("%d%d",&n,&sum);
    for(int i=1,j,k; i<n; ++i) {
        for(int s=-9999; s<=9999; ++s) {
            j=s;
            if(j<0) j+=m;
            if(!f[i][j]) continue;
            k=s+i;
            if(k<0) k+=m;
            f[i+1][k]+=f[i][j];
            k=s-i;
            if(k<0) k+=m;
            f[i+1][k]+=f[i][j];
        }
    }
    if(sum<0) tot=f[n][sum+m];
    else tot=f[n][sum];
    printf("%lld\n",tot);
    if(tot>100) tot=100; 
    print(n);
    return 0;
}