C++ 解法, 执行用时: 1282ms, 内存消耗: 276256K, 提交时间: 2023-08-12 10:16:31

#include <bits/stdc++.h>
using namespace std;

constexpr int P = 1e9 + 7;

template <class T> T qp(T a, int b) {
    T c{1};
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            c *= a;
        }
    }
    return c;
}

struct mint {
    int x;
    mint(int _x = 0) : x(_x % P) { x < 0 ? x += P : 0; }
    int val() const { return x; }

    mint operator - () const {
        return -x;
    }
    mint inv() const {
        assert(x != 0);
        return qp(*this, P - 2);
    }
    mint &operator += (const mint &rhs) {
        x += rhs.x - P, x += x >> 31 & P;
        return *this;
    }
    mint &operator -= (const mint &rhs) {
        x -= rhs.x, x += x >> 31 & P;
        return *this;
    }
    mint &operator *= (const mint &rhs) {
        x = (long long)x * rhs.x % P;
        return *this;
    }
    mint &operator /= (const mint &rhs) {
        return *this *= rhs.inv();
    }
    friend mint operator + (mint lhs, const mint &rhs) {
        return lhs += rhs;
    }
    friend mint operator - (mint lhs, const mint &rhs) {
        return lhs -= rhs;
    }
    friend mint operator * (mint lhs, const mint &rhs) {
        return lhs *= rhs;
    }
    friend mint operator / (mint lhs, const mint &rhs) {
        return lhs /= rhs;
    }

    friend ostream &operator << (ostream &os, const mint &a) {
        return os << a.val();
    }
};

struct _comb {
    int n;
    vector<mint> _fact, _finv, _inv;

    _comb() : n{0}, _fact{1}, _finv{1}, _inv{0} {}
    _comb(int n) : _comb() { initt(n); }

    void initt(int m) {
        if (m <= n) return;
        _fact.resize(m + 1);
        _finv.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fact[i] = _fact[i - 1] * i;
        }
        _finv[m] = _fact[m].inv();
        for (int i = m; i > n; i--) {
            _finv[i - 1] = _finv[i] * i;
            _inv[i] = _finv[i] * _fact[i - 1];
        }
        n = m;
    }

    mint fact(int m) {
        if (m > n) initt(2 * m);
        return _fact[m];
    }
    mint finv(int m) {
        if (m > n) initt(2 * m);
        return _finv[m];
    }
    mint inv(int m) {
        if (m > n) initt(2 * m);
        return _inv[m];
    }
    mint binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fact(n) * finv(m) * finv(n - m);
    }
} comb;

auto find_rec(const vector<mint> &a, int deg) {
    const int n = a.size();
    const int B = (n + 2) / (deg + 2), C = B * (deg + 1), R = n - (B - 1);
    assert(B >= 2 && R >= C - 1);
    vector mat(R, vector<mint>(C));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < B; j++) {
            mint x = a[i + j];
            for (int k = 0; k <= deg; k++) {
                mat[i][j * (deg + 1) + k] = x;
                x *= i + j;
            }
        }
    }
    int c = 0;
    for (int i = 0; i < C; i++) {
        int p = -1;
        for (int j = c; j < R; j++) {
            if (mat[j][i].val()) {
                p = j;
                break;
            }
        }
        if (p == -1) {
            break;
        }
        swap(mat[p], mat[c]);
        mint w = mat[c][c].inv();
        for (int j = i; j < C; j++) {
            mat[c][j] *= w;
        }
        for (int j = c + 1; j < R; j++) {
            if (mat[j][i].val()) {
                mint t = mat[j][i];
                for (int k = i; k < C; k++) {
                    mat[j][k] -= t * mat[i][k];
                }
            }
        }
        c++;
    }
    assert(c != C);
    for (int i = c - 1; i >= 0; i--) {
        if (mat[i][c].val()) {
            for (int j = i - 1; j >= 0; j--) {
                mat[j][c] -= mat[i][c] * mat[j][i];
            }
        }
    }
    int od = c / (deg + 1);
    vector res(od + 1, vector<mint>(deg + 1));
    res[0][c % (deg + 1)] = 1;
    for (int i = c - 1; i >= 0; i--) {
        res[od - i / (deg + 1)][i % (deg + 1)] = -mat[i][c];
    }
    for (int i = 0; i <= od; i++) {
        vector<mint> tmp(deg + 1);
        for (int k = 0; k <= deg; k++) {
            mint s = 1;
            for (int j = k; j <= deg; j++) {
                tmp[k] += s * res[i][j];
                s = s * -i * (j + 1) / (j + 1 - k);
            }
        }
        res[i] = tmp;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<mint> f(20);
    for (int i = 0; i < f.size(); i++) {
        for (int j = 0; j <= i; j++) {
            f[i] += (j % 2 ? -1 : 1) * comb.fact(i + j) * comb.binom(i, j) * comb.binom(n, i + j);
        }
    }
    auto rec = find_rec(f, 2);
    while (f.size() <= n) {
        int i = f.size();
        mint lhs;
        for (int k = 1; k < rec.size(); k++) {
            mint pw = 1;
            for (int j = 0; j < rec[k].size(); j++) {
                lhs -= pw * f[i - k] * rec[k][j];
                pw *= i;
            }
        }
        mint rhs, pw = 1;
        for (int j = 0; j < rec[0].size(); j++) {
            rhs += pw * rec[0][j];
            pw *= i;
        }
        assert(rhs.val() == 1);
        f.push_back(lhs);
    }
    int xors = 0;
    for (int i = 0; i <= n; i++) {
        xors ^= f[i].val();
    }
    cout << xors << "\n";
    return 0;
}