[ARC117E]Zero-Sum Ranges 2

令$sum_{i}=sum_{j=1}^{i}a_{j}$，即要求其满足：

1.$sum_{0}=sum_{2n}=0$且$forall 1le ile 2n,|sum_{i}-sum_{i-1}|=1$

2.$sum_{0le i<jle 2n}[sum_{i}=sum_{j}]=k$

问题即询问有多少个这样的$sum_{i}$

换一个角度来看待此问题，将所有$sum_{t}ge i$的位置取出，并构成一个子序列，显然剩下的位置即在其中若干个数之间插入一些小于$j$的数字

不难发现，只有在相邻两个$i$之间或在$i>0$时的开头和结尾才能插入（且必须要插入），其余相邻两数必然在原序列中也是相邻的

由此，即可以dp，令$f_{i,j,k,l}$表示有多少个长为$sum_{t}ge i$、长为$j$、相等的对数为$k$、有$l$对相邻的$i$的序列数，转移枚举加入的$i-1$的个数$x$，即$f_{i-1,j+x,k+{xchoose 2},x-(l+2[i>0])}=sum {x-1choose l+2[i>0]-1}f_{i,j,k,l}$

（其中关于$x-(l+2[i>0])$，首先$i-1$至少要在每一个能插入的位置都插入，即$l+2[i>0]$个位置，接下来每一个多出来的$x$都可使得相邻对数加1，即此式，组合数类似）

关于初始状态，需要枚举最大值$maxge 0$以及其个数$tot$，即$f_{max,tot,{totchoose 2},tot-1}=1$

关于最终答案，同样枚举最小值$minle 0$，即$sum f_{min,2n+1,k,0}$

时间复杂度即为$o(n^{6})$，空间上对其第一维滚动，可以优化到$o(n^{4})$

这一做法在常数较为优秀时（大概）可以通过，但并不足够好

考虑其中第一维，事实上后面的转移与第一维的关系并不大（仅仅是$i>0$与$ile 0$分类），且$i$的枚举范围如果增大并没有实际意义，其可以看作完全背包关于数量的枚举

换言之，可以通过顺序枚举其余位置，来代替$i$的枚举，复杂度降为$o(n^{5})$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 65
#define ll long long
int n,m;
ll ans,c[N][N],f[N][N*N][N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<N;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    for(int i=1;i<=n+1;i++)f[i][c[i][2]][i-1]=1;
    for(int i=1;i<=2*n+1;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<i;k++)
                for(int x=k+2;x<=2*n+1-i;x++)
                    if (j+c[x][2]<=m)f[i+x][j+c[x][2]][x-(k+2)]+=c[x-1][k+1]*f[i][j][k];
    for(int i=1;i<=2*n+1;i++)
        for(int j=0;j<=m;j++)
            for(int k=1;k<i;k++)
                for(int x=k;x<=2*n+1-i;x++)
                    if (j+c[x][2]<=m)f[i+x][j+c[x][2]][x-k]+=c[x-1][k-1]*f[i][j][k];
    printf("%lld",ans+f[2*n+1][m][0]);
}