华师一附中OI组

标题: 波动 [打印本页]

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

欢迎光临华师一附中OI组 (http://hsyit.cn/)