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
?
?
?
?