题面欺诈系列...
因为一个点最多只能连到前k个点,所以只有当前的连续k个点的连通情况是对接下来的求解有用的
那么就可以计算k个点的所有连通情况,dfs以下发现k=5的时候有52种。
我们把它们用类似于并查集的方式表达(比如12132代表点1和点3连通,2和5连通,3自己),然后再压缩一下。
但要注意的是,12132和23213这两种实际对应的是一种连通情况,我们只要把它都化成字典序最小的那种就可以了
然后考虑增加一个新点以后状态的转移,可以枚举这个点与前k个点(始状态S)的连边情况,其中有一些是不合法的:
1.连到了两个本来就连通的点上(导致成环)
2.在1号点不与其他点连通的情况下,没有连到1号点(导致不连通)
然后再根据连边情况得到终状态E,将trans[S][E]++。最后trans[i][j]表示的就是加入一个点后由i状态到j状态的方案数
那么就可以得到递推式$f[i][j]=\sum^{总状态数}_{k=1}{f[i-1][k]*trans[k][j]}$,其中f[i][j]表示以i为结尾的k个点状态是j的方案数
那么答案就是f[N][1](假设1是都连通的状态)
然后初值就应该是f[K][i]=i状态的方案数,其中i状态的方案数为它其中每个联通块方案数的乘积。
那么联通块的方案数怎么算呢?其实题面已经说了...n个点的方案数就是$n^{n-2)}$
然后就可以愉快地dp一脸啦
容易发现递推的形式其实和矩阵乘法是相同的,把f[i]和trans看作矩阵,就是$f[N]=f[K]*trans^{N-K}$
然后就可以倍增做矩阵快速幂了。方法和整数的快速幂是一样的。
复杂度:
K=5的状态数接近50,$log(10^{15})$接近50。
所以基本上是$50^3*50=6250000$的。
代码写的很蛋疼...
1 #include 2 #include 3 #include 4 #include