#include <bits/stdc++.h> #define ll long long #define nizej 0 #define wyzej 1 #define rowno 2 #define zwykla 0 #define mnozona 1 using namespace std; int n, m, p; int dp[2][5000005][3], sum[3][5000005][2][2]; int getsum(int pref, int l, int r, int kejs, int ktora) { int result = sum[pref][r][kejs][ktora] - sum[pref][l - 1][kejs][ktora]; if(result < 0) result += p; return result; } int32_t main() { cin >> n >> m >> p; if(n == 1) { cout << (1LL * m * (m + 1) / 2) % p; return 0; } for(int i = 1; i <= m; i++) { dp[1][i][wyzej] = 1; sum[1][i][wyzej][zwykla] = i; } int pref = 1; for(int kek = 2; kek <= n; kek++) { pref = !pref; for(int wys3 = 1; wys3 <= m; wys3++) { dp[pref][wys3][wyzej] = 1LL * (getsum(1 - pref, wys3 + 1, m, wyzej, zwykla) + getsum(1 - pref, wys3 + 1, m, wyzej, mnozona)) * wys3 % p; /*for(int wys2 = wys3 + 1; wys2 <= m; wys2++) { // wys1 > wys2 > wys3 dp[pref][wys3][wyzej] += dp[pref - 1][wys2][wyzej] * wys3; dp[pref][wys3][wyzej] %= p; // wys1 = wys2 > wys3 dp[pref][wys3][wyzej] += (dp[pref - 1][wys2][rowno] * (m - wys2 + 1) % p) * wys3; dp[pref][wys3][wyzej] %= p; }*/ dp[pref][wys3][nizej] = 1LL * (getsum(1 - pref, 1, wys3 - 1, nizej, zwykla) + getsum(1 - pref, 1, wys3 - 1, nizej, mnozona)) * (m - wys3 + 1) % p; /* for(int wys2 = 1; wys2 < wys3; wys2++) { // wys1 < wys2 < wys3 dp[pref][wys3][nizej] += dp[pref - 1][wys2][nizej] * (m - wys3 + 1); dp[pref][wys3][nizej] %= p; // wys1 = wys2 < wys3 dp[pref][wys3][nizej] += (dp[pref - 1][wys2][rowno] * wys2 % p) * (m - wys3 + 1); dp[pref][wys3][nizej] %= p; } */ // wys1 = wys2 = wys3 dp[pref][wys3][rowno] = 1LL * (1LL * dp[1 - pref][wys3][rowno] * wys3 % p) * (m - wys3 + 1) % p; // wys1 > wys2 = wys3 dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][wyzej] * wys3 % p; if(dp[pref][wys3][rowno] >= p) dp[pref][wys3][rowno] -= p; //wys1 < wys2 = wys3 dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][nizej] * (m - wys3 + 1) % p; if(dp[pref][wys3][rowno] >= p) dp[pref][wys3][rowno] -= p; sum[pref][wys3][wyzej][zwykla] = (dp[pref][wys3][wyzej] + sum[pref][wys3 - 1][wyzej][zwykla]) % p; sum[pref][wys3][wyzej][mnozona] = (1LL * dp[pref][wys3][rowno] * (m - wys3 + 1) + sum[pref][wys3 - 1][wyzej][mnozona]) % p; sum[pref][wys3][nizej][zwykla] = (dp[pref][wys3][nizej] + sum[pref][wys3 - 1][nizej][zwykla]) % p; sum[pref][wys3][nizej][mnozona] = (1LL * dp[pref][wys3][rowno] * wys3 + sum[pref][wys3 - 1][nizej][mnozona]) % p; // for(int i = 0; i < 3; i++) cout << dp[pref][wys3][i] << " "; // for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) cout << sum[pref][wys3][i][j] << " "; // cout << "\n"; } } int res = 0; for(int wys = 1; wys <= m; wys++) { res += 1LL * (1LL * dp[pref][wys][rowno] * wys % p) * (m - wys + 1) % p; if(res >= p) res -= p; res += 1LL * wys * dp[pref][wys][wyzej] % p; if(res >= p) res -= p; res += 1LL * (m - wys + 1) * dp[pref][wys][nizej] % p; if(res >= p) res -= p; } cout << res; }
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 80 81 82 83 84 85 86 87 88 89 | #include <bits/stdc++.h> #define ll long long #define nizej 0 #define wyzej 1 #define rowno 2 #define zwykla 0 #define mnozona 1 using namespace std; int n, m, p; int dp[2][5000005][3], sum[3][5000005][2][2]; int getsum(int pref, int l, int r, int kejs, int ktora) { int result = sum[pref][r][kejs][ktora] - sum[pref][l - 1][kejs][ktora]; if(result < 0) result += p; return result; } int32_t main() { cin >> n >> m >> p; if(n == 1) { cout << (1LL * m * (m + 1) / 2) % p; return 0; } for(int i = 1; i <= m; i++) { dp[1][i][wyzej] = 1; sum[1][i][wyzej][zwykla] = i; } int pref = 1; for(int kek = 2; kek <= n; kek++) { pref = !pref; for(int wys3 = 1; wys3 <= m; wys3++) { dp[pref][wys3][wyzej] = 1LL * (getsum(1 - pref, wys3 + 1, m, wyzej, zwykla) + getsum(1 - pref, wys3 + 1, m, wyzej, mnozona)) * wys3 % p; /*for(int wys2 = wys3 + 1; wys2 <= m; wys2++) { // wys1 > wys2 > wys3 dp[pref][wys3][wyzej] += dp[pref - 1][wys2][wyzej] * wys3; dp[pref][wys3][wyzej] %= p; // wys1 = wys2 > wys3 dp[pref][wys3][wyzej] += (dp[pref - 1][wys2][rowno] * (m - wys2 + 1) % p) * wys3; dp[pref][wys3][wyzej] %= p; }*/ dp[pref][wys3][nizej] = 1LL * (getsum(1 - pref, 1, wys3 - 1, nizej, zwykla) + getsum(1 - pref, 1, wys3 - 1, nizej, mnozona)) * (m - wys3 + 1) % p; /* for(int wys2 = 1; wys2 < wys3; wys2++) { // wys1 < wys2 < wys3 dp[pref][wys3][nizej] += dp[pref - 1][wys2][nizej] * (m - wys3 + 1); dp[pref][wys3][nizej] %= p; // wys1 = wys2 < wys3 dp[pref][wys3][nizej] += (dp[pref - 1][wys2][rowno] * wys2 % p) * (m - wys3 + 1); dp[pref][wys3][nizej] %= p; } */ // wys1 = wys2 = wys3 dp[pref][wys3][rowno] = 1LL * (1LL * dp[1 - pref][wys3][rowno] * wys3 % p) * (m - wys3 + 1) % p; // wys1 > wys2 = wys3 dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][wyzej] * wys3 % p; if(dp[pref][wys3][rowno] >= p) dp[pref][wys3][rowno] -= p; //wys1 < wys2 = wys3 dp[pref][wys3][rowno] += 1LL * dp[1 - pref][wys3][nizej] * (m - wys3 + 1) % p; if(dp[pref][wys3][rowno] >= p) dp[pref][wys3][rowno] -= p; sum[pref][wys3][wyzej][zwykla] = (dp[pref][wys3][wyzej] + sum[pref][wys3 - 1][wyzej][zwykla]) % p; sum[pref][wys3][wyzej][mnozona] = (1LL * dp[pref][wys3][rowno] * (m - wys3 + 1) + sum[pref][wys3 - 1][wyzej][mnozona]) % p; sum[pref][wys3][nizej][zwykla] = (dp[pref][wys3][nizej] + sum[pref][wys3 - 1][nizej][zwykla]) % p; sum[pref][wys3][nizej][mnozona] = (1LL * dp[pref][wys3][rowno] * wys3 + sum[pref][wys3 - 1][nizej][mnozona]) % p; // for(int i = 0; i < 3; i++) cout << dp[pref][wys3][i] << " "; // for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) cout << sum[pref][wys3][i][j] << " "; // cout << "\n"; } } int res = 0; for(int wys = 1; wys <= m; wys++) { res += 1LL * (1LL * dp[pref][wys][rowno] * wys % p) * (m - wys + 1) % p; if(res >= p) res -= p; res += 1LL * wys * dp[pref][wys][wyzej] % p; if(res >= p) res -= p; res += 1LL * (m - wys + 1) * dp[pref][wys][nizej] % p; if(res >= p) res -= p; } cout << res; } |