Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cassert>
- #include <numeric>
- #include <string>
- #include <cstring>
- #include <cmath>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...) 42
- #endif
- typedef long long int int64;
- int MOD;
- void sadd(int &a, int b)
- {
- a += b;
- if (a >= MOD)
- a -= MOD;
- }
- int add(int a, int b)
- {
- sadd(a, b);
- return a;
- }
- void ssub(int &a, int b)
- {
- a -= b;
- if (a < 0)
- a += MOD;
- }
- int mul(int a, int b)
- {
- return (a * 1LL * b) % MOD;
- }
- int fpow(int x, int n)
- {
- if (n == 0)
- return 1;
- int a = fpow(x, n >> 1);
- a = mul(a, a);
- if (n & 1)
- a = mul(a, x);
- return a;
- }
- int rev(int x)
- {
- return fpow(x, MOD - 2);
- }
- const int N = 405;
- int dpAll[N][N];
- long long dpGood[N][N];
- #ifdef LOCAL
- const int K = (int) 1e6 + 10;
- #else
- const int K = (int) 1e8 + 10; // TODO
- #endif
- int fact[K];
- int C[N][N];
- void init()
- {
- for (int i = 0; i < N; i++)
- {
- C[i][0] = C[i][i] = 1;
- for (int j = 1; j < i; j++)
- C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
- }
- fact[0] = 1;
- for (int i = 1; i < K; i++)
- {
- fact[i] = mul(fact[i - 1], i);
- }
- }
- int getC(int n, int k)
- {
- return mul(fact[n], rev(mul(fact[k], fact[n - k])));
- }
- int main(int, char **)
- {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- int n, k;
- scanf("%d%d%d", &n, &k, &MOD);
- init();
- for (int i = 1; i <= n; i++)
- {
- //eprintf("i = %d\n", i);
- for (int ui = 1; ui <= i; ui++)
- {
- dpAll[i][ui] = fpow(ui, i);
- for (int x = 1; x < ui; x++)
- ssub(dpAll[i][ui], mul(dpAll[i][x], C[ui][x]));
- dpGood[i][ui] = dpAll[i][ui];
- }
- for (int a = 1; a < i; a++)
- {
- int b = i - a;
- for (int ua = 1; ua <= a; ua++)
- {
- for (int ub = 1; ub <= b; ub++)
- {
- dpGood[i][ua + ub - 1] -= dpGood[a][ua] * dpAll[b][ub]; // mul(dpGood[a][ua], dpAll[b][ub]));
- //dpGood[i][ua + ub - 1] %= MOD;
- }
- if (ua % 8 == 0)
- for (int ub = 1; ub <= b; ub++)
- dpGood[i][ua + ub - 1] %= MOD;
- }
- for (int ui = 1; ui <= i; ui++)
- {
- dpGood[i][ui] %= MOD;
- if (dpGood[i][ui] < 0)
- dpGood[i][ui] += MOD;
- }
- }
- /*
- for (int ui = 1; ui <= i; ui++)
- eprintf("%d ", dpAll[i][ui]);
- eprintf("\n");
- for (int ui = 1; ui <= i; ui++)
- eprintf("%d ", dpGood[i][ui]);
- eprintf("\n");
- */
- }
- int ans = 0;
- for (int un = 1; un <= min(n, k); un++)
- sadd(ans, mul(dpGood[n][un], getC(k, un)));
- printf("%d\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment