4. 工作順序問題 [97全國賽]

DP.                                                                                                          .


不依啦zerojudge會MLE

算了

#include<stdio.h>
long long dp[10000010],n,m;
main(){
	freopen("4.in","r",stdin);
	freopen("4.out","w",stdout);
	scanf("%I64d%I64d",&n,&m);
	dp[1]=1;dp[0]=0;
	for(int i=2;i<=n;i++)
		dp[i]=((dp[i-1]*(i-1))%m+(dp[i-2])*(i-2))%m;
	printf("%I64d\n",dp[n]);
}

遞推式子不會很難想

就前一個*(n-1)個位置插入

+

前一個剛好有一組不合法的(即兩個相鄰->結合成一個點

大概這樣XD