#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) int MOD; ll modPow(ll a, ll e, ll m) { ll t = 1 % m; while (e) { if (e % 2) t = t*a % m; e /= 2; a = a*a % m; } return t; } struct Zp { ll x; Zp() : x(0) {} Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; } #define OP(c,d) Zp& operator c##=(Zp r) { x = x d; return *this; } Zp operator c(Zp r) const { Zp t = *this; return t c##= r; } OP(+, +r.x - MOD*(x+r.x >= MOD)); OP(-, -r.x + MOD*(x-r.x < 0)); OP(*, *r.x % MOD); OP(/, *r.inv().x % MOD); Zp inv() const { return pow(MOD-2); } Zp pow(ll e) const{ return modPow(x,e,MOD); } void print() { cerr << x; } }; int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n, m; cin >> n >> m >> MOD; vector<Zp> f0(m, 0), g0(m, 1); vector<Zp> f1(m), g1(m); f0[0] = 1; g0[0] = 0; rep(t, 0, n) { Zp pref = 0, suf = 0; rep(k, 0, m) { f1[k] = g0[k]*(m-k); g1[k] = pref*(m-k); pref += g0[k] + f0[k]*(k+1); } for (int k = m-1; k >= 0; k--) { suf += f0[k]*(m-k); f1[k] += suf; g1[k] += suf*k; } f0.swap(f1); g0.swap(g1); } Zp ans = 0; each(e, f0) ans += e; cout << ans.x << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) int MOD; ll modPow(ll a, ll e, ll m) { ll t = 1 % m; while (e) { if (e % 2) t = t*a % m; e /= 2; a = a*a % m; } return t; } struct Zp { ll x; Zp() : x(0) {} Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; } #define OP(c,d) Zp& operator c##=(Zp r) { x = x d; return *this; } Zp operator c(Zp r) const { Zp t = *this; return t c##= r; } OP(+, +r.x - MOD*(x+r.x >= MOD)); OP(-, -r.x + MOD*(x-r.x < 0)); OP(*, *r.x % MOD); OP(/, *r.inv().x % MOD); Zp inv() const { return pow(MOD-2); } Zp pow(ll e) const{ return modPow(x,e,MOD); } void print() { cerr << x; } }; int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n, m; cin >> n >> m >> MOD; vector<Zp> f0(m, 0), g0(m, 1); vector<Zp> f1(m), g1(m); f0[0] = 1; g0[0] = 0; rep(t, 0, n) { Zp pref = 0, suf = 0; rep(k, 0, m) { f1[k] = g0[k]*(m-k); g1[k] = pref*(m-k); pref += g0[k] + f0[k]*(k+1); } for (int k = m-1; k >= 0; k--) { suf += f0[k]*(m-k); f1[k] += suf; g1[k] += suf*k; } f0.swap(f1); g0.swap(g1); } Zp ans = 0; each(e, f0) ans += e; cout << ans.x << '\n'; return 0; } |