General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
61507994 Contestant:
lckcode
1228E - 48 GNU C++11 Time limit exceeded on pretest 3 1000 ms 516 KB 2019-09-29 18:04:36 2019-09-29 18:04:42
 
 
→ Source
    #pragma GCC optimize(2)
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define ld long double
    #define SET(x, a) memset(x, a, sizeof x);
    #define mp make_pair
    #define pb push_back
    #define pii pair<int, int>
    #define pll pair<ll, ll>
    #define fi first
    #define se second
    #define pld pair<ld, ld>
    const ll MOD = 1000000007;
    const ll INF = 10000000000000000;
    template <class T> T read(T &x) {
      char c;
      int flag = 1;
      while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
          flag *= -1;
      x = c - '0';
      while ((c = getchar()) >= '0' && c <= '9')
        x = x * 10 + c - '0';
      x *= flag;
      return x;
    }
    template <class T> T pw (T a, T b) {
      T res = 1;
      while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
      }
      return res;
    }
    template <class T> T gcd(T a, T b) {
      return b == 0 ? a : gcd(b, a % b);
    }
int n;
ll K;
ll dp[255][255], fact[255], inv[255];
ll nCr (ll n, ll k) {
	return ((fact[n] * inv[k]) % MOD * (inv[n-k])) % MOD;
}
int main () {
	cin >> n >> K;
	fact[0] = inv[0] = 1;
	for (int i = 1; i <= 250; ++i) fact[i] = fact[i-1] * i % MOD, inv[i] = pw(fact[i], MOD-2);
	for (int i = 1; i <= n; ++i) {
		// cout << nCr(n, i) << endl;
		dp[1][i] = nCr(n, i) * pw(K-1, 1LL * (n - i) ) % MOD;
        }
	// cout << dp[1][1] << ' ' << dp[1][2] << endl;
	ll ans = 0;
	for (int i = 2; i <= n; ++i) {
		// cout << i << endl;
		for (int j = 1; j <= n; ++j) {
			
			for (int k = 1; k <= j; ++k) {
				ll nw = j - k;
				if (nw == 0) {
					dp[i][j] = (dp[i][j] + ( ( ( (dp[i-1][k] % MOD) * (pw(1LL * K, 1LL * k) - pw(K - 1, 1LL * k) + MOD) ) % MOD * pw(1LL * K - 1, 1LL * max(0, n - k)) ) % MOD) ) % MOD;
				}
				else {
					dp[i][j] = (dp[i][j] + ( ( ( (dp[i-1][k] * nCr(n - k, nw) % MOD) * pw(1LL * K, 1LL * k)) % MOD * pw(1LL * K - 1, 1LL * n - nw - k) ) % MOD) ) % MOD;
				}
			}
		}
        }
	cout << dp[n][n] << endl;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details