题解：P15569 [COCI 2025/2026 #5] 结构 / Struktura

· · 题解

首先，每个数都独立地、等概率地从 1 到 k 之间选择的条件可以在计算完满足条件的数组的方案数后再乘上 (\frac{1}{k})^n 即可。

然后我们考虑怎么算出满足条件的 a 数组的数量。

在满足 |a_i+i-n-1| \le 1 的条件下，可以发现，a_1 能选 n+1、n、n-1，a_2 能选 n、n-1、n-2，a_2 能选 n-1、n-2、n-3。

我们设定一个 DP 数组 dp_{i,j}，i 表示按 1 到 n 的顺序选完了前 i 个的值，j 表示在 a_i 能选择的值中，哪些被选了。\ 具体的：

  1. 从大到小第一个（即 a_1 的 n+1、 a_2 的 n 等） 被选了，记为 4。
  2. 从大到小第二个（即 a_1 的 n、 a_2 的 n-1 等） 被选了，记为 2。
  3. 从大到小第三个（即 a_1 的 n-1、 a_2 的 n-2 等） 被选了，记为 1。

最后的 j 值即为上述的和（如 a_2 选择后 n 和 n-1 被选了，则这种情况的 j 为 4+2=6）

最后写出 DP 转移方程

经过思考可以发现，记录上述的第一条是无用的，即 j 的范围为 0 到 3。

然后可以发现，符合所有条件有效的 j 值只有 1 和 2。

最后推出：

然后把 j 为 1 的 dp 并入 j 为 2 的，就发现 dp_i=dp_{i-1}+dp_{i-2}。然后变成了斐波那契数列。直接矩阵快速幂即可。

记得特判 k<n 的情况答案为 0。 ::::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int ksm(int A,int B)
{
    int S=1;
    while(B)
    {
        if(B&1)S=S*A%mod;
        A=A*A%mod;
        B>>=1;
    }
    return S;
}
struct jz//2*2
{
    int c[3][3];
};
jz operator * (jz A,jz B)
{
    jz T;
    T.c[1][1]=0,T.c[1][2]=0;
    T.c[2][1]=0,T.c[2][2]=0;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int l=1;l<=2;l++)T.c[i][l]=(T.c[i][l]+A.c[i][j]*B.c[j][l]%mod)%mod;
    return T;
}
jz jzksm(jz A,int B)
{
    jz S;
    S.c[1][1]=1,S.c[1][2]=0;
    S.c[2][1]=0,S.c[2][2]=1;
    while(B)
    {
        if(B&1)S=S*A;
        A=A*A;
        B>>=1;
    }
    return S;
}
int n,k,c[100005];
signed main()
{
    cin>>n>>k;
    if(k<n)
    {
        cout<<0;
        return 0;
    }
    jz A;
    A.c[1][1]=1,A.c[1][2]=1;
    A.c[2][1]=0,A.c[2][2]=0;

    jz B;
    B.c[1][1]=1,B.c[1][2]=1;
    B.c[2][1]=1,B.c[2][2]=0;

    jz P=(A*jzksm(B,n-1));
    cout<<P.c[1][1]*ksm(ksm(k,mod-2),n)%mod;
    return 0;
}

::::