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 |
|
|
|
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 |