Submission #3025208


Source Code Expand

#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


const int MX = 3100;

int n;
ll MOD;
ll cnk[MX][MX];
ll dp[MX][MX];

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> MOD;
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j) {
			if (i == j || j == 0)
				cnk[i][j] = 1;
			else if (j > i)
				cnk[i][j] = 0;
			else
				cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % MOD;
		}
	dp[0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (j + 1)) % MOD;
			dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD;
		}
	}
	ll ans = 0;
	for (int k = 0; k <= n; ++k) {
		ll now = 0;
		ll cur = 1;
		--MOD;
		ll av = pw(2, n - k);
		++MOD;
		ll p = pw(2, av) * cnk[n][k] % MOD;
		av = pw(2, n - k);
		for (int j = 0; j <= k; ++j) {
			now = (now + cur * dp[k][j]) % MOD;
			cur = (cur * av) % MOD;
		}
		now = (now * p) % MOD;
		if (k % 2 == 0)
			ans = (ans + now) % MOD;
		else
			ans = (ans - now + MOD) % MOD;
	}
	cout << ans << "\n";
	return 0;
}


Submission Info

Submission Time
Task E - Everything on It
User LHiC
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1598 Byte
Status AC
Exec Time 381 ms
Memory 149760 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 600 / 600 300 / 300
Status
AC × 4
AC × 23
AC × 44
Set Name Test Cases
Sample a01, a02, a03, a04
Subtask1 a01, a02, a03, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24
Subtask2 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34, c35, c36, c37, c38, c39, c40, c41, c42, c43, c44
Case Name Status Exec Time Memory
a01 AC 2 ms 2304 KB
a02 AC 2 ms 2304 KB
a03 AC 2 ms 4608 KB
a04 AC 380 ms 149760 KB
b05 AC 2 ms 2304 KB
b06 AC 2 ms 2304 KB
b07 AC 2 ms 2304 KB
b08 AC 2 ms 2304 KB
b09 AC 2 ms 2304 KB
b10 AC 2 ms 2304 KB
b11 AC 2 ms 2432 KB
b12 AC 2 ms 2432 KB
b13 AC 2 ms 4480 KB
b14 AC 2 ms 4480 KB
b15 AC 2 ms 4480 KB
b16 AC 2 ms 4608 KB
b17 AC 2 ms 4608 KB
b18 AC 2 ms 4608 KB
b19 AC 2 ms 4608 KB
b20 AC 2 ms 4608 KB
b21 AC 2 ms 4608 KB
b22 AC 2 ms 4608 KB
b23 AC 2 ms 4608 KB
b24 AC 2 ms 4608 KB
c25 AC 2 ms 4608 KB
c26 AC 3 ms 6784 KB
c27 AC 4 ms 8832 KB
c28 AC 6 ms 13056 KB
c29 AC 13 ms 21376 KB
c30 AC 24 ms 31744 KB
c31 AC 40 ms 44160 KB
c32 AC 79 ms 62848 KB
c33 AC 160 ms 93952 KB
c34 AC 277 ms 125184 KB
c35 AC 362 ms 145664 KB
c36 AC 370 ms 145664 KB
c37 AC 375 ms 147712 KB
c38 AC 377 ms 147712 KB
c39 AC 380 ms 149760 KB
c40 AC 380 ms 149760 KB
c41 AC 380 ms 149760 KB
c42 AC 381 ms 149760 KB
c43 AC 381 ms 149760 KB
c44 AC 380 ms 149760 KB