Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <cstdio>
- #include <iomanip>
- #include <fstream>
- #include <cassert>
- #include <cstring>
- #include <unordered_set>
- #include <unordered_map>
- #include <numeric>
- #include <ctime>
- #include <bitset>
- #include <complex>
- using namespace std;
- typedef long long ll;
- const int MOD = 1e9 + 7;
- const int MAXN = 253;
- int add(int a, int b) {
- ll res = (ll)a + b;
- return res % MOD;
- }
- int sub(int a, int b) {
- ll res = (ll)a - b;
- res %= MOD;
- res += MOD;
- return res % MOD;
- }
- int mul(int a, int b) {
- ll res = (ll)a * b;
- return res % MOD;
- }
- int binpow(int a, int b) {
- int res = 1;
- while (b > 0) {
- if (b & 1) {
- res = mul(res, a);
- }
- a = mul(a, a);
- b /= 2;
- }
- return res;
- }
- int C[MAXN][MAXN + 1];
- void init() {
- C[0][0] = 1;
- for (int i = 1; i < MAXN; i++) {
- C[i][0] = 1;
- for (int j = 1; j < i; j++) {
- C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
- }
- C[i][i] = 1;
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- init();
- int n, cnt;
- cin >> n >> cnt;
- vector<int> cnt_binpows(n + 1);
- vector<int> cnt_mn_binpows(n + 1);
- for (int i = 0; i <= n; i++) {
- cnt_binpows[i] = binpow(cnt, i);
- cnt_mn_binpows[i] = binpow(cnt - 1, i);
- }
- int cnt_ok_columns = sub(binpow(cnt, n), binpow(cnt - 1, n));
- vector<vector<int>> dp(n + 1, vector<int> (n + 1));
- dp[0][n] = 1;
- for (int i = 0; i < n; i++) {
- for (int j = 1; j <= n; j++) {
- for (int k = 1; k <= j; k++) {
- int ml = mul(C[j][k], cnt_binpows[n - j]);
- ml = mul(ml, cnt_mn_binpows[j - k]);
- dp[i + 1][j - k] = add(dp[i + 1][j - k], mul(ml, dp[i][j]));
- }
- {
- int ml = sub(cnt_binpows[n - j], cnt_mn_binpows[n - j]);
- ml = mul(ml, cnt_mn_binpows[j]);
- dp[i + 1][j] = add(dp[i + 1][j], mul(ml, dp[i][j]));
- }
- }
- dp[i + 1][0] = add(dp[i + 1][0], mul(cnt_ok_columns, dp[i][0]));
- }
- cout << dp[n][0] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement