LG2467 地精部落

2024-09-05 07:40:30

题意

给出\(n\),求有几个\(W\)形的\(n\)的全排列（震荡）

思路

可以变求出第二个数比第一个数大的，再翻倍就好

设\(f[i][j]\)表示\(i\)个数中\(j\)个数不符合序列

转移时\(f[i][j]\)时，有三种情况

1.不变到\(f[i+1][j]\)，只有一种插入方法:\(i\)为偶数时，插入到倒数第二个；\(i\)为奇数时，插入到最后
2.减少一个不符合的到\(f[i+1][j-1]\)：将\(i+1\)插入到不符合序列的数前，共有\(j\)种
3.增加一个不符合的：将\(i+1\)插入到已经符合的数前,共有\(i-j\)种（\(i+1-(j-1)\)）

所以就可以写一份极简的代码

#include <bits/stdc++.h>

int n,p;

int f[4205][4205];

int main(){

	scanf("%d%d",&n,&p);

	f[1][0]=1;

	for (int i=1;i<n;i++)

		for (int j=0;j<=i;j++){

			f[i+1][j]=(f[i+1][j]+f[i][j])%p;

			f[i+1][j+1]=(f[i+1][j+1]+1ll*f[i][j]*(i-j))%p;

			if (j) f[i+1][j-1]=(f[i+1][j-1]+1ll*f[i][j]*j)%p;

		}

	printf("%d",(1ll*f[n][0]<<1)%p);

}

对了结果要模\(p\)

最新文章

热门文章