251104A. 图
给定一个 \(n\) 个点的完全无向图，求给每条边定权在 \([1,V]\) 内的方案数，使得点 \(1\) 到点 \(n\) 的最短路长度等于 \(k\)。对非质数取模。
\[1\le n, k\le 13, 1\le V\le 10^9
\]
考虑按 \(1\) 到 \(x\) 的最短路长度 \(d_x\) 对原图分层，第 \(i\) 层包含所有 \(d_i=i\) 的点。
特别的，第 \(k+1\) 层包含所有 \(d_i > k\) 的点。
对于第 \(i\le k\) 层，设其包含 \(s_i\) 个点。
- 层内两两边无限制，贡献 \(V^{\binom {s_i}2}\) 种方案。
- 枚举 \(j<i\)，第 \(j\) 层到第 \(i\) 层每对点间边权满足 \(j+w \ge i\)。（否则 \(d_x\) 可以更小）
- 对于第 \(i\) 层内每个点，至少有一个第 \(j<i\) 层上的点使上述不等式取等。（否则 \(d_x\) 可以更小）
可以直接容斥计算。
具体来说，假如其之前共有 \(k\) 个点，第 \(i\) 个点需求边权 \(w_i \ge v_i\)。那么答案就是
\[\left(\prod_{i}(V-v_i+1)\right)-\left(\prod_i(V-v_i)\right)
\]
也即任意的方案减去没有取等的方案。
直接暴力枚举 \(d_x\)，方案数约为 \(\binom {n+k} k\)，可以接受。
由于枚举过程中钦定了顺序，可能要计算一下重排的方案数。
code
#include <algorithm>
#include <iostream>typedef long long i64;const int N = 15;
i64 n, k, V, MOD;int d[N], cnt[N];
i64 ans = 0, binom = 1;void dfs(int p, i64 plan, i64 binom) {binom *= (n - p + 1);binom /= ++cnt[d[p]];if(d[p] <= k) {i64 eq = 1, gr = 1;for(int i = 1; i < p; ++i) {if(d[i] == d[p]) {plan = plan * V %MOD;} else {int diff = d[p] - d[i];if(V - diff + 1 <= 0) eq = 0;else eq = eq * (V - diff + 1) %MOD;if(V - diff <= 0) gr = 0; else gr = gr * (V - diff) %MOD;}}plan = plan * (eq - gr +MOD) %MOD;} else {for(int i = 1; i < p; ++i) {if(d[i] == d[p]) {plan = plan * V %MOD;} else {int diff = k - d[i];if(V - diff <= 0) plan = 0;else plan = plan * (V - diff) %MOD;}}}if(p == n) {binom = binom * cnt[k] / (n - 1);ans = (ans + plan * (binom %MOD)) %MOD;} else {int upd = d[p] >= k ? k + 1 : k;int dwn = p == n - 1 ? std::max(d[p], (int)k) : d[p];for(int i = dwn; i <= upd; ++i) {d[p + 1] = i, dfs(p + 1, plan, binom);}}--cnt[d[p]];
}int main() {freopen("graph.in", "r", stdin);freopen("graph.out", "w", stdout);std::cin >> n >> k >> V >> MOD;d[1] = 0;for(int i = 1; i <= k; ++i) {d[2] = i; dfs(2, 1, 1);}std::cout << ans << "\n";
}