Submission #2857758

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
constexpr lint MOD = 1000000007;

#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)

lint power(lint x, lint n, lint MOD)
{
    lint ans = 1;
    while (n>0)
    {
        if (n & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return ans;
}

vector<lint> factorial;
vector<lint> facInv;
void factorialPre(int nmax)
{
    factorial = facInv = vector<lint>(nmax + 1, 1);
    for (int i = 1; i <= nmax; i++)
    {
        factorial[i] = factorial[i-1] * i % MOD;
    }
    facInv[nmax] = power(factorial[nmax], MOD-2, MOD);
    for (int i = nmax - 1; i > 0; i--)
    {
        facInv[i] = facInv[i + 1] * (i + 1) % MOD;
    }
}

lint nCr(int n, int r)
{
    if (n<r || r<0) return 0;
    return (factorial[n] * facInv[r] % MOD) * facInv[n-r] % MOD;
}

lint nPr(int n, int r)
{
    if (n<r || r<0) return 0;
    return factorial[n] * facInv[n-r] % MOD;
}

int N, M;
vector<int> A;

int main()
{
    cin >> N >> M;
    A.resize(M+1, 1);
    REP(i, M) cin >> A[i+1];
    factorialPre(1 << N);

    vector<lint> dp(1 << N);
    dp[0] = 1;
    
    REP(m, M) {

        // 初手ゼータ変換
        REP(i, N) REP(b, 1<<N) if (b & (1 << i)) (dp[b] += dp[b ^ (1 << i)]) %= MOD;
        // 場合の数をかける
        REP(b, 1<<N) dp[b] = (b + 1 >= A[m + 1] - 1) ? (dp[b] * nPr(b + 1 - A[m], A[m+1] - A[m]-1)) % MOD : 0;
        // メビウス変換で戻す
        REP(i, N) REP(b, 1<<N) if (b & (1 << i)) (dp[b] += MOD - dp[b ^ (1 << i)]) %= MOD;
        // A[m+1] を入れる
        REP(b, 1<<N) dp[b] = (b+1 >= A[m+1]) ? (dp[b] * (b+2-A[m+1]) % MOD) : 0;
    }
    lint ans = 0;
    for (auto v : dp) (ans += v) %= MOD;
    cout << (ans * factorial[(1 << N) - A.back()] % MOD) * (1 << N) % MOD << endl;
}

Submission Info

Judge Result