题目链接：bzoj点我:-) 洛谷点我:-)
题目描述 给你n，p，请你求出满足这个条件的由1至n这n个数组成的排列有多少种，答案对p取模：即任意的连续上升或下降的一段数字区间长度不超过2（也称震荡序列）
数据范围： 对于20%的数据，满足N≤10； 对于40%的数据，满足N≤18； 对于70%的数据，满足N≤550； 对于100%的数据，满足3≤N≤4200，P≤ 109 。
思路： 定义 f[i][j][k] 为取 1 至i的数字，它们在最终序列中被分成j块，并且两头的块加新的大数字不合法的个数为k（0至2） 转移方程： 1.把原来两块的连起来： f[i+1][j−1][k]+=f[i][j][k]∗(j−1) 2.和其中一块连起来： f[i+1][j][k+1]+=f[i][j][k]∗(2−k) 3.自己单独创块： f[i+1][j+1][k]+=f[i][j][k]∗(j+1−k)
答案： f[n][1][0]+f[n][1][1]+f[n][1][2] 再把数组滚一滚就可以了
感想： 也是打算练基础的一道题，这么好的一道题，可惜我太菜了做不出来，网上大部分题解不是我这个东西，但是。。还是找个时间写写那等玄学方法好。这种DP，以前碰到过，那个浙江的波浪，还没打代码的，啊赶紧要写了。 另外，这个方法很神奇啊，可能有人问那个我的数字在与任意一个块连接起来的时候，为啥只管两边的，你想想如果加在中间，肯定不合法啊是吧，我以后加的数越来越大了啊，这个数一边比它小一边比它大啊。。 我觉得这种方法最最重要的，一是它的块的位置是灵活的，只有一个相对的位置，你不用管太多譬如它到底在原序列什么地方啊，你根本不用想这些，你想让它中间有多少空就有多少空，二是它加数字的时候是从小到大的，所以啊，很多神奇的性质就满足了，自己慢慢领会吧
代码：
//miaomiao 2017.2.1 #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define LL long long #define Set(a, v) memset(a, v, sizeof(a)) #define For(i, a, b) for(int i = (a); i <= (int)(b); i++) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--) #define N (4200+5) LL f[2][N][3]; int main(){ int n, P; scanf("%d%d", &n, &P); int a = 1; f[1][1][0] = 1; For(i, 1, n-1){ Set(f[a^1], 0); For(j, 1, min(i, n-i+1)) For(o, 0, 2) if(f[a][j][o]){ if(j > 1) f[a^1][j-1][o] = (f[a^1][j-1][o]+f[a][j][o]*(j-1)%P)%P; if(o < 2) f[a^1][j][o+1] = (f[a^1][j][o+1]+f[a][j][o]*(2-o)%P)%P; f[a^1][j+1][o] = (f[a^1][j+1][o]+f[a][j][o]*(j+1-o)%P)%P; } a^=1; } printf("%lld\n", (f[a][1][0]+f[a][1][1]+f[a][1][2])%P); return 0; }