Submission #2519620
Source Code Expand
/** * File : E.cpp * Author : Kazune Takahashi * Created : 2018-5-16 21:22:53 * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <random> // random_device rd; mt19937 mt(rd()); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; const int MAX_SIZE = 1000010; long long MOD; long long inv[MAX_SIZE]; long long fact[MAX_SIZE]; long long factinv[MAX_SIZE]; void init() { inv[1] = 1; for (int i = 2; i < MAX_SIZE; i++) { inv[i] = ((MOD - inv[MOD % i]) * (MOD / i)) % MOD; } fact[0] = factinv[0] = 1; for (int i = 1; i < MAX_SIZE; i++) { fact[i] = (i * fact[i - 1]) % MOD; factinv[i] = (inv[i] * factinv[i - 1]) % MOD; } } long long C(int n, int k) { if (n >= 0 && k >= 0 && n - k >= 0) { return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD; } return 0; } long long power(long long x, long long n) { if (n == 0) { return 1; } else if (n % 2 == 1) { return (x * power(x, n - 1)) % MOD; } else { long long half = power(x, n / 2); return (half * half) % MOD; } } long long power_2_power(ll n) { if (n == 0) { return 2 % MOD; } ll half = power_2_power(n - 1); return (half * half) % MOD; } long long gcm(long long a, long long b) { if (a < b) { return gcm(b, a); } if (b == 0) return a; return gcm(b, a % b); } ll N; ll DP[3010][3010]; ll calc(ll n, ll k) { if (DP[n][k] != -1) { return DP[n][k]; } if (k == 0) { return DP[n][k] = 1; } else if (k == n) { return DP[n][k] = calc(n - 1, k - 1); } else { ll ans = calc(n - 1, k - 1); ans += ((k + 1) * calc(n - 1, k)) % MOD; ans %= MOD; return DP[n][k] = ans; } } ll f(ll k) { ll ans = power_2_power(N - k); ll sum = 0; for (auto x = 0; x <= k; x++) { sum += (calc(k, x) * power(2, x * (N - k))) % MOD; sum %= MOD; } return (ans * sum) % MOD; } int main() { cin >> N >> MOD; init(); fill(&DP[0][0], &DP[0][0] + 3010 * 3010, -1); ll X = 0; for (auto k = 0; k <= N; k++) { ll t = (C(N, k) * f(k)) % MOD; if (N < 100) { cerr << "k = " << k << ", t = " << t << endl; cerr << "f(" << k << ") = " << f(k) << endl; } if (k % 2 == 0) { X += t; } else { X += MOD - t; } X %= MOD; } cout << X << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Everything on It |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 3341 Byte |
Status | AC |
Exec Time | 2659 ms |
Memory | 94464 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 | 71 ms | 94464 KB |
a02 | AC | 71 ms | 94464 KB |
a03 | AC | 70 ms | 94464 KB |
a04 | AC | 2650 ms | 94464 KB |
b05 | AC | 72 ms | 94464 KB |
b06 | AC | 71 ms | 94464 KB |
b07 | AC | 70 ms | 94464 KB |
b08 | AC | 72 ms | 94464 KB |
b09 | AC | 72 ms | 94464 KB |
b10 | AC | 73 ms | 94464 KB |
b11 | AC | 71 ms | 94464 KB |
b12 | AC | 71 ms | 94464 KB |
b13 | AC | 71 ms | 94464 KB |
b14 | AC | 71 ms | 94464 KB |
b15 | AC | 71 ms | 94464 KB |
b16 | AC | 71 ms | 94464 KB |
b17 | AC | 71 ms | 94464 KB |
b18 | AC | 72 ms | 94464 KB |
b19 | AC | 71 ms | 94464 KB |
b20 | AC | 72 ms | 94464 KB |
b21 | AC | 71 ms | 94464 KB |
b22 | AC | 72 ms | 94464 KB |
b23 | AC | 72 ms | 94464 KB |
b24 | AC | 72 ms | 94464 KB |
c25 | AC | 72 ms | 94464 KB |
c26 | AC | 73 ms | 94464 KB |
c27 | AC | 74 ms | 94464 KB |
c28 | AC | 81 ms | 94464 KB |
c29 | AC | 102 ms | 94464 KB |
c30 | AC | 153 ms | 94464 KB |
c31 | AC | 242 ms | 94464 KB |
c32 | AC | 476 ms | 94464 KB |
c33 | AC | 1011 ms | 94464 KB |
c34 | AC | 1871 ms | 94464 KB |
c35 | AC | 2507 ms | 94464 KB |
c36 | AC | 2579 ms | 94464 KB |
c37 | AC | 2615 ms | 94464 KB |
c38 | AC | 2624 ms | 94464 KB |
c39 | AC | 2640 ms | 94464 KB |
c40 | AC | 2639 ms | 94464 KB |
c41 | AC | 2657 ms | 94464 KB |
c42 | AC | 2659 ms | 94464 KB |
c43 | AC | 2654 ms | 94464 KB |
c44 | AC | 2652 ms | 94464 KB |