提出 #61346087

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()

#include <atcoder/modint>
using mint = atcoder::modint1000000007;

namespace po167{
    template<class T>
    struct Binomial{
        std::vector<T> fact_vec, fact_inv_vec;
        void extend(int m = -1){
            int n = fact_vec.size();
            if (m == -1) m = n * 2;
            if (n >= m) return;
            fact_vec.resize(m);
            fact_inv_vec.resize(m);
            for (int i = n; i < m; i++){
                fact_vec[i] = fact_vec[i - 1] * T(i);
            }
            fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
            for (int i = m - 1; i > n; i--){
                fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
            }
        }
        Binomial(int MAX = 0){
            fact_vec.resize(1, T(1));
            fact_inv_vec.resize(1, T(1));
            extend(MAX + 1);
        }
        T fact(int i){
            if (i < 0) return 0;
            return fact_vec[i];
        }
        T invfact(int i){
            if (i < 0) return 0;
            return fact_inv_vec[i];
        }
        T C(int a, int b){
            if (a < b || b < 0) return 0;
            return fact(a) * invfact(b) * invfact(a - b);
        }
    };
}
// CITRUS CURIO CITY / FREDERIC
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    rep(i, 0, M) cin >> A[i];
    vector<mint> dp(1 << N);
    dp[0] = 1;
    po167::Binomial<mint> table(1 << N);
    reverse(all(A));
    for (auto x : A){
        auto n_dp = dp;
        rep(i, 0, 1 << N) rep(j, 0, N){
            if (i & (1 << j)) continue;
            mint tmp = dp[i];
            tmp *= table.C((1 << N) - x - i, (1 << j) - 1);
            tmp *= table.fact(1 << j);
            n_dp[i + (1 << j)] -= tmp;
        }
        swap(n_dp, dp);
    }
    mint ans = 0;
    rep(i, 0, 1 << N) ans += dp[i] * table.fact((1 << N) - 1 - i);
    ans *= (1 << N);
    cout << ans.val() << "\n";
}

提出情報

ジャッジ結果