简要题意可以去看其他题解。
前置知识：LGV 引理。
看到这道题我们先考虑该怎么判定 \(f(l,r)\) 是否等于 \(x\)。看完题面后很难不让人想到 LGV 引理（不相交路径，起点集 \(S\) 和终点集 \(T\)）。但是 LGV 引理是用于计数的，放在这里似乎并不好用。但是我们可以 注意到，只要没有合法情况，那么矩阵行列式的结果一定为 \(0\)，而如果有合法情况，我们给每个边赋一个在 \([1,P-1]\) 内的权值，其中 \(P\) 表示一个大质数，那么如果有合法情况，则行列式的值有极大概率不为 \(0\)。
那么现在判定 \(f(l,r)=k\) 是简单的。但是怎么对于 \(f(l,r)=x\) 判定呢？我们考虑矩阵的条件是什么。
行列式的基本性质告诉我们，如果一个矩阵存在两行（列）成比例则 \(\det(A)=0\)。这告诉我们，如果这个矩阵存在线性相关，那么行列式结果一定是零。所以 \(f(l,r)=x\) 当且仅当矩阵的矩阵的秩等于 \(x\)。
那么我们可以套路的想到扫描线，枚举每个 \(r\)，对于每个 \(x\) 求最大的 \(l\) 满足 \(f(l,r)=x\)，然后我们考虑使用线性基，贪心的对于每个基底选择出现时间最晚的基底，然后就可以解决本题了！
时间复杂度 \(\mathcal{O}(nk^2+mk)\)。
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define id(x, y) ((x - 1) * n + y)
#define eb emplace_back
#define inf 1000000050
#define linf 10000000000000000
#define pii pair <int, int>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
constexpr int N = 2e6 + 5, M = 50 + 5, P = 1042702009;
typedef long long ll;
inline ll rd () {
ll x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int qpow (int x, int y) {
int ret = 1;
for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;
return ret;
}
int n, m, k;
int deg[N];
vector <pii> e[N];
class Poly {
public:
int c[M];
friend Poly operator + (const Poly& a, const Poly& b) {
Poly c;
rep (i, 1, 50) c.c[i] = (a.c[i] + b.c[i]) % P;
return c;
}
friend Poly operator - (const Poly& a, const Poly& b) {
Poly c;
rep (i, 1, 50) c.c[i] = (a.c[i] - b.c[i]) % P;
return c;
}
friend Poly operator * (const Poly& a, const int& b) {
Poly c;
rep (i, 1, 50) c.c[i] = a.c[i] * b % P;
return c;
}
} f[N];
void topo () {
queue <int> q;
rep (i, 1, k) {
f[i].c[i] = 1;
}
rep (i, 1, n) if (! deg[i]) q.push (i);
while (! q.empty ()) {
int u = q.front ();
q.pop ();
for (auto p : e[u]) {
int v = p.first, w = p.second;
f[v] = f[v] + f[u] * w;
if (! -- deg[v]) q.push (v);
}
}
}
int tim[N];
Poly vt[N];
void insert (Poly x, int t) {
rep (i, 1, k) {
if (! x.c[i]) continue;
if (! tim[i]) {
tim[i] = t, vt[i] = x;
return ;
} else {
if (tim[i] < t) swap (tim[i], t), swap (vt[i], x);
int div = qpow (vt[i].c[i], P - 2) * x.c[i] % P;
rep (j, 1, k) (x.c[j] -= vt[i].c[j] * div) %= P;
}
}
}
vector <int> vec;
int ans[M];
signed main () {
mt19937 rnd (time (NULL));
n = rd (), m = rd (), k = rd ();
rep (i, 1, m) {
int u = rd (), v = rd ();
e[u].eb (pii (v, rnd () % (P - 1) + 1)); ++ deg[v];
}
topo ();
rep (i, k + 1, n) {
insert (f[i], i);
rep (j, 1, k) if (tim[j]) vec.eb (tim[j]);
vec.eb (k), vec.eb (i);
sort (vec.begin (), vec.end (), greater <int> ());
for (int j = 0; j + 1 < vec.size (); ++ j) ans[j] += vec[j] - vec[j + 1];
vec.clear ();
}
rep (i, 0, k) printf ("%lld\n", ans[i]);
}