pypy3 解法, 执行用时: 211ms, 内存消耗: 29384K, 提交时间: 2021-06-01 22:05:21

while True:
	try:
		n, m = map(int, input().split())
		if n <= 3:
			print(0 if n <= 1 else 1)
			continue
		f = [0] * (n + 1)
		f[2] = f[3] = 1
		for i in range(4, n + 1):
			f[i] = ((i - 1) * f[i - 1] + (i - 1) * f[i - 2] - (i - 1) * (i - 2) // 2 * f[i - 3]) % m
		print(f[n] % m)
	except:
		break

C++11(clang++ 3.9) 解法, 执行用时: 97ms, 内存消耗: 1144K, 提交时间: 2020-08-18 21:15:46

#include<stdio.h>
long long f[100010]={0,0,1,1},n,p;
int main(){
    while(~scanf("%d%d",&n,&p)){
        for(long long i=4;i<=n;++i) f[i]=((i-1)*(f[i-1]+f[i-2])-((i-1)*(i-2))/2*f[i-3])%p;
        printf("%lld\n",(f[n]+p)%p);
    }
}