自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:12:25，当前版本为作者最后更新于2025-04-13 17:04:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

高考数学做法。

考虑枚举所有和 $0$ 连的点的编号的间隔，设为 $p_1k$,$p_2k$，$p_3k$,$\cdots$。

显然需要满足：$\sum p_i = \frac{n}{k}$。

给定一组 $\{p\}$ 之后，你有 $\prod p_ik$ 种方法断掉环上的边。而显然还有 $p_1$ 种方法确定第一个点的位置。所以答案就是：

显然我们能写出 $O(n^2)$ 的 DP：设

则有

暴力实现 $O(n^2)$ 的 DP 发现是对的！

考虑优化。如果你高考数学学明白了，就知道这种递推式带求和的数列求值可以多写几项然后抵消。

发现 $i-j$ 这个东西是等差数列，那么灵光一闪——我们计算 $dp_{n+2} + dp_{n+1} - 2dp_{n}$。（等差数列 $\{x\}$ 满足性质 $a_x + a_{x+2} = 2a_{x+1}$，所以我们这么做可以抵消掉很多东西！）

具体咋化简的不展示了，可以得到：

特别的，$dp_1=k$，$dp_2 = 4k + k^2$。

使用矩阵快速幂维护即可，复杂度 $O(\log n)$。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100,MOD=1e9+7;
int n,k;
struct Mat {int v[3][3];}ori,mul;
Mat operator *(Mat A,Mat B) {
	Mat C;
	memset(C.v,0,sizeof(C.v));
	ffor(i,0,2) ffor(j,0,2) ffor(k,0,2) C.v[i][k]=(C.v[i][k]+A.v[i][j]*B.v[j][k])%MOD;
	return C;
}
Mat operator ^(Mat A,int p) {
	Mat C;
	memset(C.v,0,sizeof(C.v));
	C.v[0][0]=C.v[1][1]=C.v[2][2]=1;
	while(p) {
		if(p&1) C=C*A;
		A=A*A,p>>=1;
	}
	return C;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	int nk=k%MOD;
	ori.v[0][0]=(4*nk+nk*nk)%MOD,ori.v[0][1]=nk,ori.v[0][2]=1;
	mul.v[0][0]=nk+2,mul.v[0][1]=1,mul.v[0][2]=0;
	mul.v[1][0]=-1,mul.v[1][1]=0,mul.v[1][2]=0;
	mul.v[2][0]=2*nk%MOD,mul.v[2][1]=0,mul.v[2][2]=1;
	if(n/k==1) cout<<nk;
	else ori=ori*(mul^(n/k-2)),cout<<(ori.v[0][0]%MOD+MOD)%MOD;
	return 0;
}