C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 416K, 提交时间: 2023-08-05 17:48:54

#include<bits/stdc++.h>
const int N = 2009, P = 20000311;
int a[N], fac[N], f[N];
int main() {
	int n, m;
	std::cin >> n >> m;
	for (int i = 1; i <= m; ++i) std::cin >> a[i];
	std::sort(a + 1, a + m + 1);
	if (a[m] == n) --m;
	a[++m] = n;
	*fac = 1;
	for (int i = 1; i <= n; ++i) fac[i] = 1ll * i * fac[i - 1] % P;;
	*f = 1;
	for (int i = 1; i <= m; ++i) {
		for (int j = 0; j < i; ++j) {
			f[i] = (f[i] + 1ll * f[j] * (P - fac[a[i] - a[j]])) % P;
		}
	}
	std::cout << (P - f[m]) % P << '\n';
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-10-10 22:14:59

#include <bits/stdc++.h>
using namespace std;
const int N = 2010, P = 20000311;
int n, m, fac[N], a[N], f[N];
int main() {
	scanf("%d%d", &n, &m);
	fac[1] = 1;
	for (int i=2; i<=n; ++i) fac[i] = (long long)fac[i-1]*i%P;
	for (int i=1; i<=m; ++i) scanf("%d", &a[i]);
	sort(a+1,a+1+m);
	if (a[m]!=n) a[++m] = n;
	for (int i=1; i<=m; ++i) {
		f[i] = fac[a[i]];
		for (int j=1; j<i; ++j) f[i] = (f[i]-(long long)f[j]*fac[a[i]-a[j]])%P;
	}
	if (f[m]<0) f[m] += P;
	printf("%d\n", f[m]);
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 376K, 提交时间: 2020-10-10 13:03:01

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
const int mod=20000311;
int dp[maxn],s[maxn],p[maxn];
int main()
{
	s[0]=1;for(int i=1;i<=2e3;i++)	s[i]=1LL*s[i-1]*i%mod;
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&p[i]);
	}sort(p+1,p+1+m);p[m+1]=n;
	for(int i=1;i<=m+1;i++){
		dp[i]=s[p[i]];
		for(int j=1;j<i;j++)
			dp[i]=(dp[i]-1LL*dp[j]*s[p[i]-p[j]]%mod+mod)%mod;
	}
	printf("%d\n",dp[m+1]);
}

Python3(3.5.2) 解法, 执行用时: 1307ms, 内存消耗: 5832K, 提交时间: 2020-10-10 09:38:54

f = [0] * 2010
f[0] = 1
for i in range(1,2001):
    f[i] = f[i-1] * i

a = [0] * 2010
n, m = map(int, input().split())
a = list(map(int,input().split()))
a.insert(0, 0)
a.append(n)
a.sort()
dp = [0] * 2010
mod = 20000311 
for i in range(1, len(a)):
    tmp = f[a[i]]
    
    for j in range(1,i):
        tmp = (tmp - f[a[i]-a[j]] * dp[j] % mod + mod) % mod
    
    dp[i] = tmp
print(dp[len(a)-1])