Noi模拟 最长路径 DP 奇妙推论

【题目描述】

在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。

Byteasar居住在1号城市,他希望从1号城市出发,沿着单向道路不重复地访问一些城市,使得访问的城市数尽可能多。

请写一个程序,帮助Byteasar计算有多少种道路修建方式,使得从1号点出发的最长简单路径经过点数恰好为k,由于答案可能很大,请对P取模输出。

【输入数据】

第一行包含两个正整数n,P,表示点数和模数。

【输出数据】

输出n行,第i行输出从1出发的最长简单路径经过点数恰好为i的竞赛图个数模P。

【样例输入1

2 233

【样例输出1

1

1

【样例输入2

3 233

【样例输出2

2

2

4

【数据范围】

60% n<=8

100% n <= 2000

对于100%的数据,2≤P≤10^9。

////////////////////////////////////////////////////////////////////////////////////////////////////

这种题考场上是不可能想出来了。准确说看到题解都半天没懂。。。。

这是题解,然而我猜你看不懂,,,,,,,

于强连通竞赛图一定存在哈密顿回路,因此从1号点出发的最长简单路径就是将竞赛图缩点之后i所在的连通块及其之后的连通块的点数之和。

记表示1号点在第1个连通块的i个点的竞赛图数量,那么,。

时间复杂度O(n^2)

//貌似公式传不上来,,,,QWQ下面我会手打。。。

 

我也只有浅显的一些理解,最后我们强连通缩一下点,原图必定会变成一条链。注意边不一定只有相邻的点中间才有,可能有跨过好多点有边的情况。我们考虑f[i]表示i个点的组成的竞赛图的种类数f[i],显然我们要枚举每条边的正反,显然是2^(i * (i – 1) / 2)。我们接着考虑g[i],表示1号点在第一个联通块的(i个点情况下)方案数。我们考虑容斥,用总的方案数-不合法的方案数。我们考虑如何求g[i],1不在第一个联通块,也就是不在链的最上端,我们枚举1号点究竟在哪个联通块,那么1号点所在的下半部分是以1号点在第一个联通块的,就是g[i – x],上面显然剩余的那些点怎么构造都不影响i号点在x的事实,所以是f[x]。就可以了,所以g[i] = f[i] – sum(j = 1 -> i – 1)(C(i -1,j-1)g[j]*f[i – j])。然后答案怎么求呢,如果最大长度只有x,那么显然1号点位于x个点的联通块的开始,也就是g[x],上面依旧随意,那么答案就是ans[i] = C(n – 1,i – 1)f[i] g[n – i]。

大概就是这样子了,,QwQ。。

发表评论