UNR 考的完全爆炸！
这个 D2T2 还是很有意思的，可以写写。
首先考虑给出的一个链的部分分。我们容易将所有的限制写成 \(x_{i - 1} - a_{i - 1, i} \le x_i \le x_{i - 1} + a_{i, i - 1}\) 的形式，然后每个点自己还有 \(0 \le x_i \le T\) 的限制。那么我们可以直接写一个超级长的 \(\sum\) 式子，大概形如：
我们要求的答案就是这样的一个式子。容易发现这其实一直在进行多项式前缀和，而每个变量只与前一个变量有关，那么我们可以从后往前维护一个关于 \(x_{n - 1}\) 的多项式，每次将这个多项式进行前缀和，再将上下界带入，就能令 \(n - 1\)，且得到一个关于 \(x_{n - 2}\) 的多项式，那么一直进行这样的操作，就能得到答案了。
但是还有一个问题，就是这个式子的上下界是有 \(\max/\min\) 的，不能直接把上下界代入然后差分。考虑枚举 \(\max / \min\) 等于两个选项中的哪一个，上下界全部可以 \(2^{2n}\) 枚举出来。枚举完之后，我们就能直接用上面的方法前缀和，代入然后差分了，但是我们必须限制 \(\max/\min\) 确实等于，也就是有若干大致形如 \(x_{i - 1} + a_{i, i - 1} \ge T\) 的不等式，发现这其实是对 \(x_{i - 1}\) 的上下界进行了进一步的限制。那么我们可以直接维护两个数组 \(L_i, R_i\) 表示 \(x_i \in [L_i, R_i]\)，上述的 \(\sum\) 式子中的 \(0, T\) 改成 \(L_i, R_i\)。这样，我们就可以在 \(O(2^{2n} \times \mathrm{poly}(n))\) 的复杂度内解决链的情况了。爷写了，没调完，亏死了。
我们考虑将这样的思路拓展到任意情况上。这时候，其实式子改变并不大，只不过是现在每个 \(x_i\) 有了 \(i\) 个限制（\(x_{1 \cdots n}\) 与 \(x_n\) 的关系限制和上下界限制），我们再枚举 \(\max/\min\) 的时候就需要枚举 \(i\) 种情况了。我们可以完全套用上面的做法，做到 \(O((n!)^2 \times ???)\)。由于现在 \(x_n\) 的取值与 \(n-1\) 个值有关了，我们需要维护多元多项式，可以直接暴力维护，可以看作常数不计。这样已经能拿到比较多的分数了，但是复杂度还是不能接受，因为我们有一个 \((n!)^2\)。
考虑容斥。我们可以考虑类似于二维前缀和求矩形和的方式，我们先 \(2^n\) 去枚举哪些数选上界，哪些数选下界。这样我们的 \(\sum\) 式子就只有上界没有下界了。这样，我们再去使用上面的做法，就只用枚举 \(O(n!)\) 个值了。同时发现，这时候我们每次代入的值一定是一个只与某个变量有关的多项式，那么说明我们维护的多元多项式一定是多个单元多项式的乘积，那么我们就可以直接分开维护每个元的多项式了。还是直接跑上面的做法，我们就得到了一个 \(O(n! 2^n \mathrm{poly}(n))\) 的做法。
具体的细节：我们枚举了上界取的哪一个值之后，我们相当于要满足别的每个值都小于/大于这个值，那么我们就可以相对应的去更新 \(a_{i, j} / L_i / R_i\)。需要注意我们必须满足上界大于等于下界，否则差分会出现错误。由于上界是 \(\min\)，下界是 \(\max\)，所以我们完全可以让上界的每一个数大于等于下界的每一个数，这样就一定能够满足上界大于等于下界了。同时需要注意，下界的限制不能大于上界的常数限制，即 \(x_i - a_{i, n} \le R_n\)，上界同理。
赛后发神经：链的情况拓展到一般情况也太容易了吧，但凡我没在 D2T1 上浪费三个半小时我觉得我 T2 拿四五十分是没啥问题的）算了我赛时连链的情况都没调出来，还是别搁这瞎幻想了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15, P = 998244353;
int n, m;
long long T;
array<array<long long, MAXN>, MAXN> a;
struct Polynomial {
vector<int> a;
int len;
Polynomial(int len = 0) : len(len) { a.resize(len + 1); }
void set(int len) { this->len = len, a.resize(len + 1); }
Polynomial(initializer_list<int> l) : len(l.size() - 1), a(l) {}
int& operator[](int b) { return a[b]; }
Polynomial operator*(Polynomial b) {
Polynomial c(len + b.len);
for (int i = 0; i <= len; i++) {
for (int j = 0; j <= b.len; j++) {
c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % P;
}
}
return c;
}
Polynomial operator*(int b) {
Polynomial c = *this;
for (int i = 0; i <= len; i++)
c[i] = 1ll * c[i] * b % P;
return c;
}
Polynomial operator+(Polynomial b) {
Polynomial c = *this;
c.set(max(len, b.len));
for (int i = 0; i <= b.len; i++)
c[i] = (c[i] + b[i]) % P;
return c;
}
Polynomial operator-(Polynomial b) {
Polynomial c = *this;
c.set(max(len, b.len));
for (int i = 0; i <= b.len; i++)
c[i] = (c[i] - b[i] + P) % P;
return c;
}
Polynomial operator+(int b) {
Polynomial c = *this;
c[0] = (c[0] + b) % P;
return c;
}
Polynomial operator-(int b) {
Polynomial c = *this;
c[0] = (c[0] - b + P) % P;
return c;
}
int operator()(long long x) {
x = (x % P + P) % P;
int ret = 0;
for (int i = len; i >= 0; i--) {
ret = (1ll * ret * x + a[i]) % P;
}
return ret;
}
void print() {
for (int i : a)
printf("%d ", i);
printf("\n");
}
};
int fac[5005], inv[5005];
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * inv[m] % P * inv[n - m] % P;
}
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
Polynomial qpow(Polynomial a, int b) {
Polynomial ans({1});
while (b) {
if (b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--)
inv[i - 1] = 1ll * inv[i] * i % P;
assert(inv[0] == 1);
}
Polynomial s[MAXN], pre[MAXN], suf[MAXN];
int y[MAXN];
Polynomial calc(int k) {
for (int i = 0; i <= k + 1; i++) {
if (i) y[i] = y[i - 1];
y[i] = (y[i] + qpow(i, k)) % P;
if (i == 0 && k != 0) y[0] = 0;
}
pre[0] = { 0, 1 };
suf[k + 2] = { 1 };
for (int i = 1; i <= k + 1; i++)
pre[i] = pre[i - 1] * Polynomial({ P - i, 1 });
for (int i = k + 1; i >= 0; i--)
suf[i] = suf[i + 1] * Polynomial({ P - i, 1 });
Polynomial ret = suf[1] * y[0] * inv[k + 1] * (((k + 1) & 1) ? P - 1 : 1);
for (int i = 1; i <= k + 1; i++) {
ret = ret + pre[i - 1] * suf[i + 1] * y[i] * inv[i] * inv[k + 1 - i] * (((k + 1 - i) & 1) ? P - 1 : 1);
}
return ret;
}
Polynomial presum(Polynomial a) {
Polynomial b;
for (int i = 0; i <= a.len; i++) {
b = b + s[i] * a[i];
}
return b;
}
Polynomial fuhe(Polynomial a, Polynomial b) {
Polynomial c;
for (int i = a.len; i >= 0; i--) {
c = c * b + a[i];
}
return c;
}
int ans;
void chkmin(long long &a, long long v) {
a = min(a, v);
}
void chkmax(long long &a, long long v) {
a = max(a, v);
}
int norm(long long x) { return (x % P + P) % P; }
void dfs(int n, array<array<long long, MAXN>, MAXN> a, vector<Polynomial> f, vector<long long> L, vector<long long> R) {
if (L[n] > R[n]) return;
for (int j = 1; j < n; j++) {
if (-a[j][n] > a[n][j]) return;
}
if (n == 1) {
f[1] = presum(f[1]);
ans = (1ll * ans + f[1](R[1]) - f[1](L[1] - 1) + P) % P;
return;
}
for (int i = 1; i < n; i++) {
chkmin(R[i], R[n] + a[i][n]);
chkmax(L[i], L[n] - a[n][i]);
}
{ // choose R
{ // choose R[n]
vector<Polynomial> nf = f;
vector<long long> nL = L, nR = R;
for (int j = 1; j < n; j++) {
chkmax(nL[j], R[n] - a[n][j] + 1);
chkmin(nR[j], R[n] + a[j][n]);
}
nf[n - 1] = f[n - 1] * presum(f[n])(R[n]);
dfs(n - 1, a, nf, nL, nR);
}
for (int i = 1; i < n; i++) { // choose i
array<array<long long, MAXN>, MAXN> na = a;
vector<Polynomial> nf = f;
vector<long long> nL = L, nR = R;
chkmin(nR[i], R[n] - a[n][i]);
for (int j = 1; j < n; j++) if (j != i) {
chkmin(na[i][j], a[n][j] - a[n][i] - (i > j));
chkmin(na[j][i], a[n][i] + a[j][n]);
}
nf[i] = f[i] * fuhe(presum(f[n]), Polynomial({ norm(a[n][i]), 1 }));
dfs(n - 1, na, nf, nL, nR);
}
}
{ // choose L
{ // choose L[n]
vector<Polynomial> nf = f;
vector<long long> nL = L, nR = R;
for (int j = 1; j < n; j++) {
chkmin(nR[j], L[n] + a[j][n] - 1);
chkmax(nL[j], L[n] - a[n][j]);
}
nf[n - 1] = f[n - 1] * presum(f[n])(L[n] - 1) * (P - 1);
dfs(n - 1, a, nf, nL, nR);
}
for (int i = 1; i < n; i++) { // choose i
array<array<long long, MAXN>, MAXN> na = a;
vector<Polynomial> nf = f;
vector<long long> nL = L, nR = R;
chkmax(nL[i], L[n] + a[i][n]);
for (int j = 1; j < n; j++) if (j != i) {
chkmin(na[j][i], a[j][n] - a[i][n] - (i > j));
chkmin(na[i][j], a[i][n] + a[n][j]);
}
nf[i] = f[i] * fuhe(presum(f[n]), Polynomial({ norm(-a[i][n] - 1), 1 })) * (P - 1);
dfs(n - 1, na, nf, nL, nR);
}
}
}
int main() {
init(5000);
for (int i = 0; i <= 10; i++)
s[i] = calc(i);
scanf("%d%d%lld", &n, &m, &T);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = T;
}
}
for (int i = 1; i <= m; i++) {
int u, v; long long c; scanf("%d%d%lld", &u, &v, &c);
a[u][v] = min(a[u][v], c);
}
dfs(n, a, vector<Polynomial>(n + 1, Polynomial({1})), vector<long long>(n + 1, 0), vector<long long>(n + 1, T));
printf("%d\n", ans);
return 0;
}