Submission #5033613

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
ll mod_pow(ll a, ll n) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		ll tmp = mod_pow(a, n / 2);
		return (tmp * tmp) % MOD;
	}
	return (a * mod_pow(a, n - 1)) % MOD;
}

vector<ll> fact;
vector<ll> inv_fact;

void comb_init(int n) {
	fact.resize(n + 1);
	inv_fact.resize(n + 1);
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
}
ll dp1[17][1 << 16];
ll dp3[17][1 << 16];
int A[17];
int main() {
	int N, M;
	cin >> N >> M;
	comb_init(1 << N);
	A[0] = 1;
	for (int i = 1; i <= M; i++) cin >> A[i];
	dp1[0][0] = 1;
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < N; j++) for (int b = 0; b < (1 << N); b++) if (b&(1 << j)) (dp1[i - 1][b] += dp1[i - 1][b ^ (1 << j)]) %= MOD;
		for (int U = 0; U < (1 << N); U++) {
			int t = U - (A[i - 1] - 1);
			int d = A[i] - 1 - A[i - 1];
			if (t >= d) {
				dp3[i][U] = (fact[t] * inv_fact[t - d]) % MOD;
				(dp3[i][U] *= dp1[i - 1][U]) %= MOD;
			}
		}
		for (int j = 0; j < N; j++) for (int b = 0; b < (1 << N); b++) if (b&(1 << j)) (dp3[i][b] += MOD - dp3[i][b ^ (1 << j)]) %= MOD;
		for (int U = 0; U < (1 << N); U++) if (U >= A[i] - 2) dp1[i][U] = dp3[i][U] * (U - (A[i] - 2)) % MOD;
	}
	ll ret = 0;
	for (int U = 0; U < (1 << N); U++) (ret += dp1[M][U]) %= MOD;
	(ret *= fact[(1 << N) - A[M]]) %= MOD;
	(ret *= 1 << N) %= MOD;
	cout << ret << endl;
}

Submission Info

Judge Result