Advertisement
Guest User

Untitled

a guest
Sep 29th, 2019
400
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24.  
  25. const int MOD = 1e9 + 7;
  26. const int MAXN = 253;
  27.  
  28. int add(int a, int b) {
  29.     ll res = (ll)a + b;
  30.     return res % MOD;
  31. }
  32.  
  33. int sub(int a, int b) {
  34.     ll res = (ll)a - b;
  35.     res %= MOD;
  36.     res += MOD;
  37.     return res % MOD;
  38. }
  39.  
  40. int mul(int a, int b) {
  41.     ll res = (ll)a * b;
  42.     return res % MOD;
  43. }
  44.  
  45. int binpow(int a, int b) {
  46.     int res = 1;
  47.     while (b > 0) {
  48.         if (b & 1) {
  49.             res = mul(res, a);
  50.         }
  51.         a = mul(a, a);
  52.         b /= 2;
  53.     }
  54.     return res;
  55. }
  56.  
  57. int C[MAXN][MAXN + 1];
  58.  
  59. void init() {
  60.     C[0][0] = 1;
  61.     for (int i = 1; i < MAXN; i++) {
  62.         C[i][0] = 1;
  63.         for (int j = 1; j < i; j++) {
  64.             C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
  65.         }
  66.         C[i][i] = 1;
  67.     }
  68. }
  69.  
  70. signed main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(0);
  73.  
  74.     init();
  75.     int n, cnt;
  76.     cin >> n >> cnt;
  77.     vector<int> cnt_binpows(n + 1);
  78.     vector<int> cnt_mn_binpows(n + 1);
  79.     for (int i = 0; i <= n; i++) {
  80.         cnt_binpows[i] = binpow(cnt, i);
  81.         cnt_mn_binpows[i] = binpow(cnt - 1, i);
  82.     }
  83.     int cnt_ok_columns = sub(binpow(cnt, n), binpow(cnt - 1, n));
  84.     vector<vector<int>> dp(n + 1, vector<int> (n + 1));
  85.     dp[0][n] = 1;
  86.     for (int i = 0; i < n; i++) {
  87.         for (int j = 1; j <= n; j++) {
  88.             for (int k = 1; k <= j; k++) {
  89.                 int ml = mul(C[j][k], cnt_binpows[n - j]);
  90.                 ml = mul(ml, cnt_mn_binpows[j - k]);
  91.                 dp[i + 1][j - k] = add(dp[i + 1][j - k], mul(ml, dp[i][j]));
  92.             }
  93.             {
  94.                 int ml = sub(cnt_binpows[n - j], cnt_mn_binpows[n - j]);
  95.                 ml = mul(ml, cnt_mn_binpows[j]);
  96.                 dp[i + 1][j] = add(dp[i + 1][j], mul(ml, dp[i][j]));
  97.             }
  98.         }
  99.         dp[i + 1][0] = add(dp[i + 1][0], mul(cnt_ok_columns, dp[i][0]));
  100.     }
  101.     cout << dp[n][0] << endl;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement