#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define SIZE 10'000'002 LL X, M, MOD; LL gora_le[SIZE], dol_ge[SIZE], dol_na[SIZE], gora_na[SIZE]; void sumuj() { FOR(b, 1, M) gora_le[b] = (gora_le[b - 1] + gora_na[b]) % MOD; FORD(a, M, 1) dol_ge[a] = (dol_ge[a + 1] + dol_na[a]) % MOD; } int main() { cin >> X >> M >> MOD; FOR(a, 1, M) { gora_na[a] = a; dol_na[a] = M + 1 - a; } sumuj(); REP(x, X - 1) { LL s_gora_le = 0; FOR(b, 1, M) { gora_na[b] = (b * (dol_ge[1] + MOD - dol_ge[b + 1]) + MOD - s_gora_le) % MOD; s_gora_le = (s_gora_le + gora_le[b]) % MOD; } LL s_dol_ge = 0; FORD(a, M, 1) { dol_na[a] = ((M + 1 - a) * (dol_ge[1] + MOD - gora_le[a - 1]) + MOD - s_dol_ge) % MOD; s_dol_ge = (s_dol_ge + dol_ge[a]) % MOD; } sumuj(); } cout << dol_ge[1] << endl; }
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 | #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define SIZE 10'000'002 LL X, M, MOD; LL gora_le[SIZE], dol_ge[SIZE], dol_na[SIZE], gora_na[SIZE]; void sumuj() { FOR(b, 1, M) gora_le[b] = (gora_le[b - 1] + gora_na[b]) % MOD; FORD(a, M, 1) dol_ge[a] = (dol_ge[a + 1] + dol_na[a]) % MOD; } int main() { cin >> X >> M >> MOD; FOR(a, 1, M) { gora_na[a] = a; dol_na[a] = M + 1 - a; } sumuj(); REP(x, X - 1) { LL s_gora_le = 0; FOR(b, 1, M) { gora_na[b] = (b * (dol_ge[1] + MOD - dol_ge[b + 1]) + MOD - s_gora_le) % MOD; s_gora_le = (s_gora_le + gora_le[b]) % MOD; } LL s_dol_ge = 0; FORD(a, M, 1) { dol_na[a] = ((M + 1 - a) * (dol_ge[1] + MOD - gora_le[a - 1]) + MOD - s_dol_ge) % MOD; s_dol_ge = (s_dol_ge + dol_ge[a]) % MOD; } sumuj(); } cout << dol_ge[1] << endl; } |