分析

我们可以假象一个假的限制 记录前 个条件都满足，但第 个条件不满足的方案数，考虑 之间的数随便排列， ，然后第 个条件不满足，前 个条件都满足，乘 ；对于不同的 ，方案是不相交的，且 计算了所有不应该在 中计数到的方案数所以 。思路来源与不知名的大佬。我这里只是分享一下做法。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 2100,mod = 20000311;
int f[N],p[N],n,m,fac[N];
int main() {
    n = read();m = read();
    fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = 1LL * fac[i-1] * i % mod;
    for(int i = 1;i <= m;i++) p[i] = read();
    p[++m] = n;sort(p+1,p+1+m);
    for(int i = 1;i <= m;i++) {
        f[i] = fac[p[i]];
        int res = 0;
        for(int j = 1;j < i;j++) {
            res = (res + 1LL * fac[p[i] - p[j]] * f[j]) % mod;
        }
        f[i] = ((f[i] - res) % mod + mod) % mod;
    }
    cout << f[m] << endl;
    return 0;
}