题意
给一个 \(n\) 个点 \(m\) 条边的 DAG 和一个 \(k\)，对于一个 \(k < l \le r \le n\) 的区间 \([l, r]\)，定义 \(f(l, r)\) 为起点在 \([1, k]\) 且终点在 \([l, r]\) 中的不相交路径组大小的最大值。对于每个 \(i \in [0, k]\)，求 \(f(l, r) = i\) 的区间个数。
\(1 \le n \le 10^5\)，\(1 \le m \le 10^6\)，\(1 \le k \le 50\)。
题解
第一反应网络流，但是复杂度无法有效利用 \(k\) 很小的性质。
- 有没有什么处理不相交路径的方法？
可以想到 LGV 引理。
- LGV 对 DAG 不相交路径计数计出来的不知道是什么玩意，怎么办？
观察题面，发现我们并不需要计数，直接判定就可以了。一点好处是当没有不相交路径时，LGV 算出来的行列式一定是 \(0\)（因为全部可以构造双射抵消掉）。
- 有不相交路径时行列式也有可能是 \(0\)，怎么办？
可以考虑将每一条边都赋一个随机权值，一条路径的权值就是边权的乘积，那此时行列式就大概率不为 \(0\) 了。
- 起点和终点是不固定的，你求什么东西的行列式？
设 \(d_{i, j}\) 表示 \(i\) 到 \(j\) 的所有路径的权值之和，则对于一个向量组：
\[\begin{pmatrix}
d_{1, l} & d_{1, l + 1} & \cdots & d_{1, r} \\
d_{2, l} & d_{2, l + 1} & \cdots & d_{2, r} \\
\vdots & \vdots & \ddots & \vdots \\
d_{k, l} & d_{k, l + 1} & \cdots & d_{k, r}
\end{pmatrix}
\]
存在大小为 \(i\) 的不相交路径组的充要条件是存在一个 \(i\) 阶子式的值不为 \(0\)，即他们是线性无关的，也就是他们的秩为 \(i\)。这个条件等价于这个向量组的线性基大小 \(\ge i\)。那么，我们直接暴力做，复杂度就有 \(\mathcal{O}(n^2k^2)\) 了。
- 太慢了。
使用前缀线性基即可（就是每个基维护时间戳，每次插入尽量选最新的）。复杂度 \(\mathcal{O}(nk^2 + mk)\)。注意不要写假。
int n,m,k,x,y,deg[100005],dis[55][100005],b[55][55],V[55],t[55],ans[55];
vector<pii>v[100005];
queue<int>q;
void insert(int T){fd(i,k,1)if(V[i]){if(!b[i][i]){memcpy(b[i],V,sizeof V),t[i]=T;break;}if(t[i]<T)swap(b[i],V),swap(t[i],T);int tmp=V[i]*qp(b[i][i],mod-2)%mod;fo(j,1,k)cminus(V[j],tmp*b[i][j]%mod);}
}
void solve(){cin>>n>>m>>k;fo(i,1,k)dis[i][i]=1;fo(i,1,m)cin>>x>>y,v[x].push_back({y,rdint(1,mod-1)}),deg[y]++;fo(i,1,n)if(!deg[i])q.push(i);while(q.size()){int x=q.front();q.pop();for(auto[i,w]:v[x]){fo(j,1,k)cplus(dis[j][i],dis[j][x]*w%mod);if(!(--deg[i]))q.push(i);}}fo(i,k+1,n){fo(j,1,k)V[j]=dis[j][i];insert(i);vector<int>tmp;fo(j,1,k)if(t[j])tmp.push_back(t[j]);tmp.push_back(k),sort(tmp.rbegin(),tmp.rend());// debug(i,tmp);fo(j,0,tmp.size()-1)ans[j]+=(j?tmp[j-1]:i)-tmp[j];}fo(i,0,k)cout<<ans[i]<<'\n';
}