Guest User

Untitled

a guest
Feb 14th, 2021
795
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7. #include <cassert>
  8. #include <numeric>
  9. #include <string>
  10. #include <cstring>
  11. #include <cmath>
  12. using namespace std;
  13.  
  14. #ifdef LOCAL
  15.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  16. #else
  17.     #define eprintf(...) 42
  18. #endif
  19.  
  20. typedef long long int int64;
  21.  
  22. int MOD;
  23.  
  24. void sadd(int &a, int b)
  25. {
  26.     a += b;
  27.     if (a >= MOD)
  28.         a -= MOD;
  29. }
  30. int add(int a, int b)
  31. {
  32.     sadd(a, b);
  33.     return a;
  34. }
  35. void ssub(int &a, int b)
  36. {
  37.     a -= b;
  38.     if (a < 0)
  39.         a += MOD;
  40. }
  41. int mul(int a, int b)
  42. {
  43.     return (a * 1LL * b) % MOD;
  44. }
  45. int fpow(int x, int n)
  46. {
  47.     if (n == 0)
  48.         return 1;
  49.     int a = fpow(x, n >> 1);
  50.     a = mul(a, a);
  51.     if (n & 1)
  52.         a = mul(a, x);
  53.     return a;
  54. }
  55. int rev(int x)
  56. {
  57.     return fpow(x, MOD - 2);
  58. }
  59.  
  60. const int N = 405;
  61. int dpAll[N][N];
  62. long long dpGood[N][N];
  63.  
  64. #ifdef LOCAL
  65. const int K = (int) 1e6 + 10;
  66. #else
  67. const int K = (int) 1e8 + 10; // TODO
  68. #endif
  69. int fact[K];
  70. int C[N][N];
  71.  
  72. void init()
  73. {
  74.     for (int i = 0; i < N; i++)
  75.     {
  76.         C[i][0] = C[i][i] = 1;
  77.         for (int j = 1; j < i; j++)
  78.             C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
  79.     }
  80.     fact[0] = 1;
  81.  
  82.     for (int i = 1; i < K; i++)
  83.     {
  84.         fact[i] = mul(fact[i - 1], i);
  85.     }
  86. }
  87.  
  88. int getC(int n, int k)
  89. {
  90.     return mul(fact[n], rev(mul(fact[k], fact[n - k])));
  91. }
  92.  
  93. int main(int,  char **)
  94. {
  95. #ifdef LOCAL
  96.     freopen("input.txt", "r", stdin);
  97. //  freopen("output.txt", "w", stdout);
  98. #endif
  99.  
  100.  
  101.     int n, k;
  102.     scanf("%d%d%d", &n, &k, &MOD);
  103.    
  104.     init();
  105.  
  106.     for (int i = 1; i <= n; i++)
  107.     {
  108.         //eprintf("i = %d\n", i);
  109.         for (int ui = 1; ui <= i; ui++)
  110.         {
  111.             dpAll[i][ui] = fpow(ui, i);
  112.             for (int x = 1; x < ui; x++)
  113.                 ssub(dpAll[i][ui], mul(dpAll[i][x], C[ui][x]));
  114.             dpGood[i][ui] = dpAll[i][ui];
  115.         }
  116.         for (int a = 1; a < i; a++)
  117.         {
  118.             int b = i - a;
  119.             for (int ua = 1; ua <= a; ua++)
  120.             {
  121.                 for (int ub = 1; ub <= b; ub++)
  122.                 {
  123.                     dpGood[i][ua + ub - 1] -= dpGood[a][ua] * dpAll[b][ub]; // mul(dpGood[a][ua], dpAll[b][ub]));
  124.                     //dpGood[i][ua + ub - 1] %= MOD;
  125.                 }
  126.                 if (ua % 8 == 0)
  127.                     for (int ub = 1; ub <= b; ub++)
  128.                         dpGood[i][ua + ub - 1] %= MOD;
  129.             }
  130.             for (int ui = 1; ui <= i; ui++)
  131.             {
  132.                 dpGood[i][ui] %= MOD;
  133.                 if (dpGood[i][ui] < 0)
  134.                     dpGood[i][ui] += MOD;
  135.             }
  136.         }
  137.         /*
  138.         for (int ui = 1; ui <= i; ui++)
  139.             eprintf("%d ", dpAll[i][ui]);
  140.         eprintf("\n");
  141.         for (int ui = 1; ui <= i; ui++)
  142.             eprintf("%d ", dpGood[i][ui]);
  143.         eprintf("\n");
  144.         */
  145.     }
  146.  
  147.     int ans = 0;
  148.     for (int un = 1; un <= min(n, k); un++)    
  149.         sadd(ans, mul(dpGood[n][un], getC(k, un)));
  150.     printf("%d\n", ans);
  151.  
  152.     return 0;
  153. }
  154.  
  155.  
Advertisement
Add Comment
Please, Sign In to add comment