波动

admin

【问题描述】
        一个长度为n的序列{a_i}的波动值定义为∑_(i=1)^(n-1)▒〖|a_(i-1)-a_i |〗。
        你需要求出波动值为m的1-n的排列个数模〖10〗^9+7的余数。
【输入】
输入文件wave.in。
        第一行两个数n,m。
【输出】
输出文件wave.out。
一行一个数表示答案。
【输入输出样例】
wave.in        wave.out
4 5        12
【数据说明】
30%:n≤10,m≤40
100%:n≤50

admin

(zjoi2012)
        考虑一种排列的生成方式，每次加入一个数然后和前面的数交换或插入一个位置，再计算权值。
        因为是绝对值，所以考虑从小往大加，但是发现在交换或插入后与前面序列的状态有关，不好转移，而n又较小，考虑添加状态方便转移。
        在加入一个元素后我们决策其相邻的两个元素与其的大小关系，此时就加上它对答案的影响，这样一来，我们相当于将当前的序列割成了几段，后面的数只能插入段与段的间隙里，又考虑到两端间隙的特殊性，令fi,j,k，s表示考虑完前面i个数、有j个间隔、两端的间隔有k个、波动值为s的方案数，转移参(zi)见(xing)标(nao)称(bu)。
        时间复杂度O(N4)。
        空间复杂度O(N3),用滚动数组。