Description
给定一张 \(n\) 个点的 DAG，保证点 \(1\sim k\) 没有入度，对每个 \(i\in[0,k]\)，求出满足条件的区间 \([l,r]\subseteq(k,n]\) 的数量，使得起点在 \([1,k]\) 且终点在 \([l,r]\) 的极大不相交路径组大小为 \(i\)。
\(n\leq 10^5,m\leq 10^6,k\leq 50\)。
Solution
首先如果已知起点和终点的配对判断有没有解可以用 LGV 引理做，令 \(f_{i,j}\) 表示从 \(s_i\) 走到 \(t_j\) 的方案数，再对 \(f\) 求行列式判断结果是不是 \(0\) 即可。
这里方案数很多，需要对一个质数 \(P\) 取模，为了提高正确率，为每条边随一个边权，\(f_{i,j}\) 改成所有路径边权乘积之和。而行列式是否非零只需要判断其是否满秩即可。
然后考虑怎么对一个区间 \([l,r]\) 求答案。
设区间长度为 \(L\)，设 \(a_{i,j}=f_{j,l+i-1}(1\leq i\leq L,1\leq j\leq k)\)，问题变为找到最大的 \(x\)，使得存在 \(a\) 的一个 \(x\times x\) 的子矩阵满秩。这是个线性代数经典结论，答案就是 \(a\) 的行秩。
设 \(V_{i,j}=f_{j,i}(k+1\leq i\leq n,1\leq j\leq k)\)，那么我们只需要维护 \(V_{l},V_{l+1},\ldots,V_{r}\) 的线性基大小。
考虑扫描线，从小到大枚举 \(l\)。用时间戳线性基维护即可。
时间复杂度：\(O(nk^2+mk)\)。
Code
#include <bits/stdc++.h>// #define int int64_tusing i64 = int64_t;
using u64 = uint64_t;const int kMaxN = 1e5 + 5, kMaxM = 1e6 + 5, kMaxK = 55, kMod = 998244353;int n, m, k;
int deg[kMaxN], val[kMaxM], tm[kMaxK];
i64 res[kMaxK];
std::vector<std::pair<int, int>> G[kMaxN];
std::mt19937_64 rnd(std::random_device{}());int qpow(int bs, int64_t idx = kMod - 2) {int ret = 1;for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)if (idx & 1)ret = (int64_t)ret * bs % kMod;return ret;
}inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }struct Vector {int a[kMaxK] = {0};friend Vector operator *(const Vector &b, const int w) {static Vector ret;for (int i = 1; i <= k; ++i) ret.a[i] = 1ll * w * b.a[i] % kMod;return ret;}friend Vector operator +(const Vector &a, const Vector &b) {static Vector ret;for (int i = 1; i <= k; ++i) ret.a[i] = add(a.a[i], b.a[i]);return ret;}
} f[kMaxN], bs[kMaxK];void prework() {std::queue<int> q;for (int i = 1; i <= n; ++i) {if (!deg[i]) q.emplace(i);if (i <= k) f[i].a[i] = 1;}for (; !q.empty();) {int u = q.front(); q.pop();for (auto [v, id] : G[u]) {f[v] = f[v] + f[u] * val[id];if (!--deg[v]) q.emplace(v);}}
}void ins(Vector a, int t) {for (int i = 1; i <= k; ++i) {if (a.a[i]) {if (t > tm[i]) std::swap(a, bs[i]), std::swap(t, tm[i]);int v = 1ll * a.a[i] * qpow(bs[i].a[i]) % kMod;a = a + bs[i] * sub(0, v);}}
}void dickdreamer() {std::cin >> n >> m >> k;for (int i = 1; i <= m; ++i) {int u, v;std::cin >> u >> v;G[u].emplace_back(v, i), ++deg[v], val[i] = rnd() % kMod;}prework();for (int i = k + 1; i <= n; ++i) {static int tt[kMaxK];ins(f[i], i);if (i > k) {for (int j = 1; j <= k; ++j) tt[j] = tm[j];tt[0] = i;std::sort(tt + 1, tt + 1 + k, std::greater<>());for (int j = 0; j <= k; ++j)if (tt[j]) res[j] += tt[j] - k;}}for (int i = 0; i < k; ++i) res[i] -= res[i + 1];for (int i = 0; i <= k; ++i) std::cout << res[i] << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}