细节挺多的。
题意
有一个长度为 \(n\) 的数组 \(a\) 和一个长度为 \(m\) 的队列 \(q\)，初始时 \(q\) 中的元素和为 \(0\)。对 \(x=1,2,\cdots,n\) 进行如下操作：
- 如果队首元素 \(q_1<a_x\)，则 \(q\) 弹出队首，将 \(a_x\) 插入队尾。
在操作结束后，定义数组 \(a\) 的 权值 为 \(q\) 中元素的和。
给定长度为 \(n\) 的数字 \(b\)，\(b\) 中元素两两不等。求数组 \(b\) 重拍后得到的所有排列 \(a\) 的权值值和，对 \(10^9+7\) 取模。
\(n,m \le 500\)。
思路
首先，我们定义数组 \(p\) 表示加入过队列 \(q\) 的元素。上述例子中 \(p=[1,9,2,6,3,10,4]\)，其个数 \(n_p\) 定义为 \(a\) 的 度。
假定 \(p\) 的元素个数为 \(n_p\)，则对于 \(i \le n_p-m\)，满足 \(p_i<p_{i+m}\)。考虑将 \(v \notin p\) 中的元素插入到 \(p\) 中，使其变成数组 \(a\)，插入的条件为对于 \(m+1 \le i \le n_p+1\)，\(i\) 与 \(i-1\) 之间插入的数字序列 \(S_i\) 中的每个元素 \(\le p_{i-m}\)，可以发现，\(i\) 后面插入的数字与 \(p_{i-m}\) 有关，而 \(p_i\) 也只是与 \(p_{i-m}\) 有关，所以我们考虑对每个 \(0 \le j < m\)，\(i \bmod m=j\) 组成的子序列进行计数。
整理一下，对于每个子序列 \([p_{i_1},p_{i_2},\cdots,p_{i_l}]\)，满足 \(p_{i_j}<p_{i_{j+1}}\)，而 \(S_{i_j}\) 中的元素 \(\le\) \(p_{i_j-1}\)。
对这种序列 \(dp\)，考虑令 \(f_{i,j}\) 表示填了 \(i\) 个数字，其度为 \(j\) 个的方案数个数。对于每个 \(i\) 考虑从大到小求解，令 \(g_{j,k}\) 表示放了最大的 \(j\) 个数字，其度为 \(k\) 的方案数个数。转移枚举第 \(j-1\) 大的数字在不在 \(p\) 序列即可。
考虑对原序列进行计数，令 \(\lfloor \frac{n_p}{m} \rfloor=x\)，则原序列的 \(p\) 序列的每个子序列长度为 \(x\) 或 \(x+1\)，子序列个数总和为 \(m\)。而对于位置 \(n_p\) 与 \(n_p+1\) 之间填的数字，考虑可以在统计 \(p\) 序列后强行添加 \(n+1\) 进行计算。而因为枚举 \(x\) 的时候保证不重复，对于统计 \(x\) 的时候，保证至少有一个子序列长度 \(x\)。显然，\((n_p+1) \bmod m\) 子序列原本只有 \(x\) 个，加入 \(n+1\) 后会是 \(x+1\) 个元素，称这种子序列为特殊子序列。
令 \(dp_{1,i,j}\) 表示 \(p\) 序列中填了 \(j\) 个长度为 \(x\) 的子序列，\(a\) 序列中填了 \(i\) 个的方案数。
令 \(dp_{2,i,j}\) 表示 \(p\) 序列中填了 \(j\) 个长度为 \(x + 1\) 的子序列，\(a\) 序列中填了 \(i\) 个的方案数。
令 \(dp_{0,i,j}\) 表示 \(p\) 序列中填了 \(m-1\) 个子序列，包含特殊子序列，\(x+1\) 子序列的个数为 \(j\) 个，\(a\) 序列中填了 \(i\) 个的方案数。
令 \(dp_{3,i,j}\) 表示 \(p\) 序列中填了 \(m-1\) 个子序列，刚好不包含特殊子序列，\(x+1\) 子序列的个数为 \(j\) 个，\(a\) 序列中填了 \(i\) 个的方案数。
然后考虑统计答案，即每个 \(p\) 序列最后 \(m\) 个元素的权值和（不包含 \(n+1\)），枚举一下即可，需要分情况讨论，用到 \(dp_{0,i,j}\) 与 \(dp_{3,i,j}\)。
因为 \(j \le m\)，而且 \(x \le \frac nm\)，复杂度是 \(O(n^3)\)。
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
int rd() {
int x = 0, f = 1;
char ch = getchar();
while (!('0' <= ch && ch <= '9')) {
if (ch == '-') f = -1; ch = getchar();
}
while ('0' <= ch && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();
}
return x * f;
}
void wr(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) wr(x / 10); putchar(x % 10 + '0');
}
bool MemoryST;
const int N = 510;
const int mod = 1e9 + 7;
int b[N];
int c[N][N], p[N];
int dp1[N][N], dp2[N][N], dp3[N][N];
int n, m, dp[N][N], f[N][N], g[N][N];
void init(int n) {
for (int i = 0; i <= n; ++i) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; ++j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
void Add (int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int ksm (int x, int y = mod - 2) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod; y >>= 1;
}
return res;
}
void Mainsolve() {
int n, m; cin >> n >> m;
init(n + 1);
for (int i = 1; i <= n; ++i)
cin >> b[i];
for (int i = 1; i <= n; ++i)
for (int x = i; x <= n; ++x)
p[i] = (p[i] + 1ll * c[x - 1][i - 1] * b[x] % mod) % mod;
for (int i = 1; i <= n + 1; ++i) {
for (int j = 1; j <= i; ++j)
for (int k = 1; k <= i; ++k)
g[j][k] = 0;
g[i][1] = 1;
for (int j = i; j >= 2; --j)
for (int k = 1; k <= i; ++k)
Add(g[j - 1][k + 1], g[j][k]), Add(g[j - 1][k], 1ll * g[j][k] * (i - j) % mod);
for (int j = 1; j <= i; ++j)
f[i][j] = g[1][j];
}
int ans = 0;
int inv = ksm(m - 1);
for (int x = 1; x <= n / m; ++x) {
for (int i = 0; i <= n + 1; ++i)
for (int j = 0; j <= m; ++j)
dp1[i][j] = dp2[i][j] = dp3[i][j] = dp[i][j] = 0;
dp1[0][0] = 1;
for (int i = 0; i < n + 1; ++i)
for (int j = 0; j < m; ++j)
for (int k = 1; k <= n + 1 - i; ++k)
Add(dp1[i + k][j + 1], 1ll * dp1[i][j] * f[k][x] % mod * c[i + k][i] % mod);
// dp1[i][j] 表示 i 个点，有 j 个位置的方案数个数，填的个数是 x
dp2[0][0] = 1;
for (int i = 0; i < n + 1; ++i)
for (int j = 0; j < m; ++j)
for (int k = 1; k <= n + 1 - i; ++k)
Add(dp2[i + k][j + 1], 1ll * dp2[i][j] * f[k][x + 1] % mod * c[i + k][i] % mod);
// dp2[i][j] 表示 i 个点，有 j 个位的方案数个数，填的数字是 x + 1
for (int i = 0; i <= n + 1; ++i)
for (int j = 0; j <= n + 1 - i; ++j)
for (int k = 0; k <= m - 1; ++k)
Add(dp3[i + j][k], 1ll * dp1[i][m - 1 - k] * dp2[j][k] % mod * c[i + j][i] % mod);
for (int i = n + 1; i >= 0; --i)
for (int j = 0; j < m; dp2[i][j] = 0, ++j)
for (int k = 1; k <= n + 1 - i; ++k)
Add(dp2[i + k][j + 1], 1ll * dp2[i][j] * f[k][x + 1] % mod * c[i + k - 1][i] % mod);
for (int i = 0; i <= n + 1; ++i)
for (int j = 0; j <= n + 1 - i; ++j)
for (int k = 0; k <= m - 1; ++k)
Add(dp[i + j][k], 1ll * dp1[i][m - 1 - k] * dp2[j][k] % mod * c[i + j - 1][i] % mod);
// dp[i][j] 表示 i 个点，有 j 个位置填了 x + 1 的数字的方案数
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m - 1; ++j)
Add(ans, 1ll * f[i + 1][x + 1] * dp3[n - i][j] % mod * p[i] % mod);
for (int j = 1; j <= m - 1; ++j)
Add(ans, 1ll * f[i][x] * dp[n + 1 - i][j] % mod * (m - j) % mod * p[i] % mod);
for (int j = 1; j <= m - 1; ++j)
Add(ans, 1ll * f[i][x + 1] * dp[n + 1 - i][j] % mod * j % mod * p[i] % mod);
}
}
cout << ans << endl;
}
bool MemoryED;
int main() {
// freopen ("potential.in", "r", stdin);
// freopen ("potential.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cerr << fixed << setprecision(6) << (&MemoryST - &MemoryED) / 1048576.0 << "MB\n";
int T = 1;
while (T--) Mainsolve();
cerr << endl << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}