请不要随便@站长团成员
@[icy](/space/show?uid=20487)
by Hono @ 2017-09-20 19:30:51
@[Hono](/space/show?uid=27115) 谢谢告知，另外向kkk表示抱歉，不会再有下一次了。
因为这题另外一个楼@了kkk所以也这么做了T.T
by 消失的海岸线 @ 2017-09-20 19:49:00
get
by icy @ 2017-09-21 13:56:31
我写的没超时，献上鄙人拙码```cpp
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int read();
int M(int x) { return x >= mod ? x - mod : x; }
void Add(int &x, int y) { (x += y) >= mod ? x -= mod : x; }
int n, m;
int a[502], b[502], st[502], top;
int f[2][502][502];
int s[502], g[502][502];
void init() {
for (int i = 1; i <= n; ++i) s[i] = i * (i + 1) / 2;
for (int l = 1; l <= n; ++l)
for (int r = l; r <= n; ++r)
g[l][r] = s[l - 1] + s[n - r] + s[r - l + 1];
}
int main() {
n = read(), m = read(), init();
for (int i = 1; i <= n; ++i) a[i] = st[i] = read();
sort(st + 1, st + 1 + n), top = unique(st + 1, st + 1 + n) - st - 1;
for (int i = 1; i <= n; ++i)
b[i] = lower_bound(st + 1, st + 1 + top, a[i]) - st;
b[0] = b[n + 1] = top + 1;
// for (int i = 1, l, r; i <= n; ++i) {
// l = r = i;
// while (b[l - 1] <= b[i]) --l;
// while (b[r + 1] <= b[i]) ++r;
// Add(f[0][l][r], M(mod + st[b[i]] - st[b[i] + 1]));
// }
for (int l = 1; l <= n; ++l) {
for (int r = l, mx = 0; r <= n; ++r) {
mx = max(mx, b[r]);
for (int i = mx; i < min(b[l - 1], b[r + 1]); ++i)
Add(f[0][l][r], M(mod + st[i] - st[i + 1]));
}
}
// for (int i = 1; i <= n; ++i) {
// int res = 0;
// for (int l = 1; l <= i; ++l)
// for (int r = i; r <= n; ++r) Add(res, f[0][l][r]);
// printf("%d ", res);
// }
// puts("");
int p = 0, q = 1;
for (int i = 1; i <= m; ++i) {
for (int l = 1; l <= n; ++l)
for (int r = l; r <= n; ++r)
f[q][l][r] = 1ll * f[p][l][r] * g[l][r] % mod;
for (int l = 1; l <= n; ++l)
for (int r = n, t = 0; r >= l; --r)
Add(f[q][l][r], t), Add(t, 1ll * f[p][l][r] * (n - r) % mod);
for (int r = 1; r <= n; ++r)
for (int l = 1, t = 0; l <= n; ++l)
Add(f[q][l][r], t), Add(t, 1ll * f[p][l][r] * (l - 1) % mod);
swap(p, q);
}
for (int i = 1; i <= n; ++i) {
int res = 0;
for (int l = 1; l <= i; ++l)
for (int r = i; r <= n; ++r) Add(res, f[p][l][r]);
printf("%d ", res);
}
puts("");
return 0;
}
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
```
by _红_ @ 2021-04-19 21:09:21
但是此题 LOJ 只有 1s
by henryhu2006 @ 2022-05-31 14:13:25