@bzoj - 5219@ [Lydsy2017省队十连测]最长路径

冷不防 2023-06-01 12:59 36阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

在Byteland一共有n个城市，编号依次为1到n，形成一个n个点的竞赛图。  
请写一个程序，帮助Byteasar计算有多少种道路修建方式，使得从1号点出发的最长简单路径经过点数恰好为k，由  
于答案可能很大，请对P取模输出

**Input**  
第一行包含两个正整数n,P，表示点数和模数。  
2≤P≤1e9,N<=2000  
**Output**  
输出n行，第i行输出从1出发的最长简单路径经过点数恰好为i的竞赛图个数模P。

**Sample Input**  
2 233  
**Sample Output**  
1  
1

## @solution@ ##

首先根据我们竞赛图的性质，在进行强连通缩点后，一个点出发的最长简单路径长度 = 它所在强连通分量大小 + 拓扑序在它之后的点数。  
至于证明，[我的这篇博客里面有][Link 1]。

考虑如果路径长度为 k 时，枚举 1 所在强连通分量的大小为 p。则只需要保证 1 之前的 n - k 个点全部向后面连边，1 之后的 k - p 个点全部由前面连过来即可，其他就没有多余的对这 n - p 个点的限制。  
我们记 f\[i\] 表示 i 个点的竞赛图个数，g\[i\] 表示 i 个点的强连通竞赛图个数，则（注意要保证 1 号点一定在强连通内部）：  
\\\[ans\[k\] = \\sum\_\{p=1\}^\{k\}C\_\{n-1\}^\{n-k\}\*C\_\{k-1\}^\{k-p\}\*f\[n-k\]\*g\[p\]\*f\[k-p\]\\\]

因为 \\(f\[i\] = 2^\{C\_i^2\}\\)，所以我们考虑怎么求 g。  
考虑经典容斥。假如 i 个点不形成强连通，则我们枚举将 i 个点缩点后拓扑序最靠前的强连通大小，就可以容斥。即：  
\\\[g\[i\] = f\[i\] - \\sum\_\{j=1\}^\{i-1\}C\_\{i\}^\{j\}\*g\[j\]\*f\[i-j\]\\\]

## @accepted code@ ##

#include<cstdio> const int MAXN = 2000; int f[MAXN + 5], g[MAXN + 5], h[MAXN + 5]; int c[MAXN + 5][MAXN + 5]; int n, P; int main() { scanf("%d%d", &n, &P); for(int i=0;i<=n;i++) { c[i][0] = 1; for(int j=1;j<=i;j++) c[i][j] = (c[i-1][j] + c[i-1][j-1])%P; } int tmp = 1; f[0] = f[1] = 1; for(int i=2;i<=n;i++) tmp = 2LL*tmp%P, f[i] = 1LL*f[i-1]*tmp%P; for(int i=1;i<=n;i++) { g[i] = f[i]; for(int j=1;j<i;j++) g[i] = (g[i] + P - 1LL*c[i][j]*g[j]%P*f[i-j]%P)%P; } for(int i=1;i<=n;i++) { h[i] = 0; for(int j=1;j<=i;j++) h[i] = (h[i] + 1LL*c[n-1][n-i]*c[i-1][i-j]%P*f[n-i]%P*g[j]%P*f[i-j]%P)%P; } for(int i=1;i<=n;i++) printf("%d\n", h[i]); }

## @details@ ##

实际实现中，并没有必要写快速幂，因为可以从 f\[i-1\] 直接递推到 f\[i\]。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11381132.html

[Link 1]: https://www.cnblogs.com/Tiw-Air-OAO/p/11381034.html