[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;
}