题解：P12046 [USTCPC 2025] 生成树！

· · 题解

Solution

高考数学做法。

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

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

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

\sum_{\sum p_i = \frac{n}{k}} p_1 \prod p_ik

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

dp_n = \sum_{\sum p_i = n} p_1 \prod p_ik

则有

dp_n = n^2 k + \sum_{j=1}^{n-1} f_j (i-j)k

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

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

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

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

dp_{n+2} = 2k + (2+k) dp_{n+1} - dp_n

特别的，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;
}