题解

水题，可惜要写高精度有点烦

一看障碍物的摆放方式和最后的答案没有关系，于是干脆不读了，直接二项式反演可以得到

设\(g_k\)为一种摆放方式恰好占了k个障碍物

\(f_k = \sum_{i = k}^{n} \binom{i}{k} g_{i}\)

可以得到

\(g_0 = \sum_{k = 0}^{n} (-1)^{k} \binom{k}{0} f_{i}\)

\(g_0 = \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} (n - k)!\)

拆开可以发现后面就是 \(\frac{n!}{k!}\)一个阶乘的后缀乘积

所以高精度只要实现高精乘低精，高精加，高精减就可以了

代码

#include 
    
     #define enter putchar('\n')#define space putchar(' ')#define pii pair
     
      #define fi first#define se second#define MAXN 200005#define pb push_back#define mp make_pair//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 + c - '0';        c = getchar();    }}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}const int BASE = 100000000;const int LEN = 8;struct Bignum {    vector
        
          v;    Bignum(int64 x = 0) {        *this = x;    }    Bignum operator = (int64 x) {        v.clear();        do {            v.pb(x % BASE);            x /= BASE;        }while(x > 0);        return *this;    }    friend Bignum operator + (const Bignum &a,const Bignum &b) {        Bignum c;c.v.clear();        int p = 0,g = 0,x;        while(1) {            x = g;            if(p < a.v.size()) x += a.v[p];            if(p < b.v.size()) x += b.v[p];            if(!x && p >= a.v.size() && p >= b.v.size()) break;            c.v.pb(x % BASE);            g = x / BASE;            ++p;        }        return c;    }    friend Bignum operator - (const Bignum &a,const Bignum &b) {        Bignum c;c.v.clear();        int p = 0,g = 0,x;        while(1) {            x = -g;g = 0;            if(p < a.v.size()) x += a.v[p];            if(p < b.v.size()) x -= b.v[p];            if(!x && p >= a.v.size() && p >= b.v.size()) break;            if(x < 0) {g = 1;x += BASE;}            c.v.pb(x);            ++p;        }        return c;    }    friend Bignum operator * (const Bignum &a,int64 b) {        Bignum c;c.v.clear();        int s = a.v.size();        int64 g = 0;        for(int i = 0 ; i < s ; ++i) {            int64 x = 1LL * a.v[i] * b + g;            c.v.pb(x % BASE);            g = x / BASE;        }        while(g) {            c.v.pb(g % BASE);            g /= BASE;        }        return c;    }    void print() {        int s = v.size() - 1;        printf("%d",v[s]);        for(int i = s - 1 ; i >= 0 ; --i) {            printf("%08d",v[i]);        }    }}fac[205],ans;int N;int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    read(N);    if(N == 1) {puts("0");return 0;}    fac[N + 1] = 1;    for(int i = N ; i >= 1 ; --i) {        fac[i] = fac[i + 1] * i;    }    for(int i = 0 ; i <= N ; i += 2) {        ans = ans + fac[i + 1];    }    for(int i = 1 ; i <= N ; i += 2) {        ans = ans - fac[i + 1];    }    ans.print();    putchar('\n');    return 0;}