[bzoj 1925] [Sdoi2010]地精部落

求1~n的抖动 (不存在连续三项递增或递减) 排列的数目, 答案对p取模. (3≤n≤4200, p≤10^9) Euler or up/down numbers

排列中去掉一个数, 剩下的仍然两两不同. 这为建立递推关系带来了方便.

考虑一列数:

1 2 3 ... x-1 x x+1 ... n-1 n

把x拿掉, 剩下的部分和1~n-1一一对应, 就像离散化一样:

1 2 3 ... x-1 x+1 x+2 ... n
1 2 3 ... x-1 x x+1 ... n-1

设f[i][j]为先上升且首元素小于等于j的抖动排列的数目, 则第二项起的部分和先下降且首元素大于等于j的抖动排列一一对应, 设为g[i][j].

类似地, 先下降且首元素大于等于j的抖动排列, 跟先上升且首元素小于等于(j-1)的抖动排列一一对应.

递推计算即可. 数组得滚动一下 (如果是考试已经GG了 TAT).

发现f[n][n]=g[n][1], 这是为什么呢? 先上升的抖动排列和先下降的抖动排列可以一一对应: i <-> n-i+1.

看了题解, 发觉这一点可以用来优化DP: g[i][j] = f[i][i-j+1]. 减少了常数, 同时数组可以不用滚动了.

const int N = 4200;

int f[2][N+1], g[2][N+1];

int main()
{
	int n, p;
	scanf("%d%d", &n, &p);
	f[1][1] = g[1][1] = 1 % p;
	rep (i, 2, n+1) {
		rep (j, 1, i+1) f[i&1][j] = (f[i&1][j-1] + g[(i-1)&1][j]) % p;
		per (j, i, 1) g[i&1][j] = (g[i&1][j+1] + f[(i-1)&1][j-1]) % p;
	}
	printf("%d\n", (f[n&1][n] + g[n&1][1]) % p);
	return 0;
}