DPA.
纪念场切题。
记 \(f[i, j, x, 0/1, 0/1]\) 表示前 \(i\) 个车站都已经经过，\(i\rightarrow i+1\) 的边走过 \(j\) 次，总距离 \(\bmod m=x\) ，是否钦定起点，是否钦定终点（这 \(j\) 条边经过是有顺序）。
为了转移简便，我们强制起点在终点之前钦定，最后将答案全部 \(\times 2\) 即可，因为过程是完全对称的。
以已钦定起点，未钦定终点为例（注意到 \(j\) 一定为奇数）。
- 钦定 \(i\) 为终点
- \(j\) 中的最后一条停留在这里，转移到 \(f[i, j-1, nx, 1, 1]\) 。
- \(j\) 全部顺延，最后再返回一条边终止于 \(i\) ，转移到 \(f[i, j+1, nx, 1, 1]\) 。
- \(i\) 不为终点
- \(j\) 中的某条边“顺路”经过 \(i\) ，\(\times j\rightarrow f[i, j, nx, 1, 0]\) 。
- \(j\) 中的某组边（向右又向左）经过 \(i\) ，这样的组有 \(\frac{j-1}{2}\) 个，\(\times \frac{j-1}{2}\rightarrow f[i, j-2, nx, 1, 0]\) 。
- \(j\) 全部顺延，最后返回一组边经过 \(i\) , 这样的位置有 \(\frac{j+1}{2}\) 个，\(\times \frac{j+1}{2}\rightarrow f[i, j+2, nx, 1, 0]\) 。
上文中， \(nx=(x+j\times \Delta x)\bmod m\) 。
初值直接赋给 \(1\) 是/不是起点就好了，直接赋值 \(2\) 省去 \(\times 2\) 的过程。
点击查看
#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 1000 + 7;
const int LM = 100 + 7;
const int mod = 998244853;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int T, n, m, a[LN], f[2][LN][LM][2][2];bool ENDPOS;il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int& u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int& u, int v) { u = mul(u, v); }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock(), nx;std::cin >> T;while (T--) {std::cin >> n >> m;lep(i, 1, n) std::cin >> a[i];std::sort(a + 1, a + 1 + n);lep(i, 1, n) a[i] %= m;int p = 0;std::memset(f[p], 0, sizeof(f[p]));f[p][1][0][1][0] = f[p][2][0][0][0] = 2;lep(i, 2, n) {std::memset(f[p ^ 1], 0, sizeof(f[p ^ 1]));lep(j, 1, n) lep(x, 0, m - 1) { nx = (1ll * (m + a[i] - a[i - 1]) * j % m + x) % m;if (j & 1) {//S nupa(f[p ^ 1][j - 1][nx][1][1], f[p][j][x][1][0]);upa(f[p ^ 1][j + 1][nx][1][1], f[p][j][x][1][0]);upa(f[p ^ 1][j][nx][1][0], mul(j, f[p][j][x][1][0]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][1][0], mul(j / 2, f[p][j][x][1][0]));upa(f[p ^ 1][j + 2][nx][1][0], mul(j / 2 + 1, f[p][j][x][1][0]));}else {// S Tupa(f[p ^ 1][j][nx][1][1], mul(j, f[p][j][x][1][1]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][1][1], mul(j / 2, f[p][j][x][1][1]));upa(f[p ^ 1][j + 2][nx][1][1], mul(j / 2, f[p][j][x][1][1]));//n nupa(f[p ^ 1][j][nx][0][0], mul(j, f[p][j][x][0][0]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][0][0], mul(j / 2 - 1, f[p][j][x][0][0]));upa(f[p ^ 1][j + 2][nx][0][0], mul(j / 2 + 1, f[p][j][x][0][0]));if (j) upa(f[p ^ 1][j - 1][nx][1][0], f[p][j][x][0][0]);upa(f[p ^ 1][j + 1][nx][1][0], f[p][j][x][0][0]);}}p ^= 1;}lep(i, 0, m - 1) std::cout << f[p][0][i][1][1] << ' ';std::cout << '\n';}#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}