本蒟蒻的第一篇题解。

前置知识

矩阵乘法快速幂 有理数取余

题意简述

随机取 $n$ 个 $1$ 至 $k$ 的正整数，求这 $n$ 个数满足如下条件概率取余 $10^9+7$ 的值。

整数 $1,2,\dots,n$ 在数组中各出现恰好一次。

对每个下标 $i$（$1 \le i \le n$），都有 $|a_i + i - n - 1| \le 1$。

题目分析

沿用题目中的定义，设合法方案数为 $P$ 此题概率明显为合法方案数除以总方案数。

总方案数显然为 $k^n$。难点在于如何求合法方案数。

先考虑 $n > k$：我们需要 $1,2,\dots,n$ 各出现恰好一次，共需要 $n$ 个不同数字，但只有 $k$ 个数字可选，$n>k$ 时无解，合法方案数为 $0$。

再考虑 $n \leq k$： 题目中给到的合法条件是 $|a_i+i-n-1|\leq 1$，这相当于 $|a_i-(n-i+1)|\leq 1$，这里我们可以将数组颠倒过来，此时条件变为 $|a_i-i|\leq 1$。

考虑动态规划，定义 $dp_i$ 表示前 $i$ 个数的合法方案数。初始化为 $dp_0=1$，$dp_1=1$。

接着思考如何转移，因为 $|a_i-i|\leq 1$，所以 $a_i$ 只能等于 $i+1$，$i-1$ 或 $i$。

• 当 $a_i=i$ 时，只要确定前 $i-1$ 位合法就可以了，合法方案数为 $dp_{i-1}$。
• 当 $a_i=i-1$ 时，显然 $a_{i-1} = i$，这时让确定前 $i-2$ 位合法，方案数为 $dp_{i-2}$。
• $a_i=i+1$ 这种情况相当于下一次转移的第一种情况，会被下一次转移考虑到。

得到 $dp_i=dp_{i-1}+dp_{i-2}$，就是斐波那契数列。

最后利用费马小定理求乘法逆元再输出就行了。

直接计算斐波那契数列会超时。为什么会超时呢？因为 同学试过 这个代码时间复杂度为 $O(n)$ 而 $n$ 的范围是 $n\leq 10^9$，肯定超时。

考虑使用矩阵快速幂优化，优化后复杂度为 $O(\log_2{n})$。

实现中的部分细节

为什么求解时求的是矩阵的 $n-2$ 次方？

因为 $dp_1$ 与 $dp_2$ 是不需要进行矩阵乘法就能求的。也就是说，如果只进行一次乘法，就已经求出 $dp_3$ 了。

为什么 $a_i = i+1$ 不算一种新情况？

推导 DP 转移时，我曾纠结于 $a_i=i+1$ 是否需要额外处理。但仔细观察后发现：如果第 $i$ 位填了 $i+1$，那么第 $i+1$ 位就必须填 $i$。

这里为什么可以用费马小定理？

因为模数 $10^9+7$ 是质数且保证 $Q$ 不被模数整除。

完结撒花

:::success[AC Code]

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
struct Matrix{
	long long c[3][3];
	long long size;
	Matrix(long long n){
		size=n;
		memset(c,0,sizeof(c));
	}
	Matrix operator*(Matrix &o){//矩阵乘法
		Matrix ans(size);
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				for(int k=1;k<=2;k++){
					ans.c[i][j]+=c[i][k]*o.c[k][j]%mod;
					ans.c[i][j]%=mod;
				}
			}
		}
		return ans;
	}
};
long long qpow(long long a,long long p){//快速幂
	long long ans=1;
	a=a%mod;
	while(p>0){
		if(p&1) ans=ans*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return ans;
}
signed main(){
	long long n,k;
	cin>>n>>k;
	if(n>k){//不可能把k个数字分给大于k个格子
		cout<<0;
		return 0;
	}
	if(n<=2){//不用矩阵乘法
		cout<<n*qpow(qpow(k,n),mod-2)%mod;
		return 0;
	}
	Matrix a(2),ans(2);
	long long n2=n;
	n--;
	ans.c[1][1]=ans.c[1][2]=1;//答案矩阵
	a.c[1][1]=a.c[1][2]=a.c[2][1]=1;
	while(n>0){//矩阵乘法快速幂
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	cout<<ans.c[1][1]%mod*qpow(qpow(k,n2),mod-2)%mod;//qpow(qpow(k,n2),mod-2)是费马小定理求乘法逆元
	return 0;
}

:::

讲下赛时思路吧，没题解好想：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL P = 1e9 + 7;
 
struct node {
	LL a[2][2];
	node() {
		memset(a, 0, sizeof(a));
	}
};
 
node operator*(node na, node nb) {
	node res;
	for (int i = 0;i <= 1; i ++) {
		for (int j = 0; j <= 1; j ++) {
			for (int k = 0; k <= 1; k ++) {
				res.a[i][j] = (res.a[i][j] + na.a[i][k] * nb.a[k][j] % P) % P ;
			}
		}
	}
	return res;
}
 
node mq_pow(node a, LL b) {
	node c;
	c.a[0][0] = c.a[1][1] = 1;
	while (b) {
		if (b & 1) {
			c = c * a;
		}
		a = a * a;
		b >>= 1;
	}
	return c;
}
 
LL q_pow(LL a, LL b) {
	LL c = 1;
	while (b) {
		if (b & 1) {
			c = c * a % P;
		}
		a = a * a % P;
		b >>= 1;
	}
	return c;
}
 
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	LL n, K;
	cin >> n >> K;
	
	if (K < n) {
		cout << "0\n";
		return 0;
	}
	node t;
	t.a[0][0] = 1; t.a[0][1] = 1;
	node tt;
	tt.a[0][0] = tt.a[0][1] = tt.a[1][0] = 1;
	node ans = t * mq_pow(tt, n - 1);
	LL dow = q_pow(K, n);
	dow = q_pow(dow, P - 2);
	
	
	cout << (ans.a[0][0] * dow % P) << "\n";
	
	return 0;
}