GMOJ J2480 【好序列】

Description

问你有多少个长度为 $n$ 的整数序列，满足每个数在 $0$ 到 $n$ 之间，且其任一长度的前缀和大于等于其相同长度的后缀和。

$$1 \leq n \leq 100$$

Solution

考虑设 $f_{i, j}$ 表示当前确定了首尾 $i$ 位，且当前的前缀和比后缀和多 $j$ 的序列的方案数。

然后你考虑当 $n$ 是奇数的情况，那就把 $n$ 先减一，然后再把算出来的答案乘个 $(n + 1)$ 就好了，因为中间的那一位填啥都行。

如果你的转移写的不好看的话那么是 $O(n^5)$ 的，打个表也能过。

写的好看的话就是枚举当前的两个数的差，这样就是 $O(n^4)$ 的啦。

由于我比较菜，所以我选择直接打表。还挺快，一百多秒后表出来了。

其实这个题可以用前缀和优化 DP 可以将其优化至 $O(n^3)$。

Code

#include <cstdio>
int Ans[110] = {0, 2, 6, 40, 290, 3486, 43246, 755616, 13408452, 307487950, 127190630, 344174518, 737806111, 598547111, 84861666, 600841977, 859818824, 995583605, 447205830, 510213804, 718971337, 980895796, 486718666, 887058925, 91801289, 792774646, 48881882, 535088132, 499788903, 412557256, 241482037, 485793783, 900854629, 595628402, 619228279, 190026404, 664155715, 607267617, 275647528, 891974277, 923140092, 74701752, 472302467, 597286332, 549513641, 979861011, 30168574, 388375848, 994336080, 992981349, 433660335, 757041922, 671041214, 748478731, 854334582, 259977065, 333747051, 712109593, 939736254, 723515420, 361927586, 296747311, 217466295, 385808178, 976646435, 837183419, 343441064, 643434731, 528583747, 764921683, 951459111, 12267105, 463197309, 754140426, 696112600, 608621579, 768559754, 75512116, 877279933, 110424636, 795702436, 222122860, 647387539, 483228718, 428782274, 47135023, 391680856, 195888837, 925613007, 666378996, 388886740, 884518820, 857910798, 979779993, 163561272, 388591041, 425964062, 523897739, 648164552, 502643920, 698163860};
int main ()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", Ans[n]);
	return 0;
}