简要题意

开始是一个 $1\sim n$ 的排列，每次等概率、随机选 $i,j\in[1,n],i,j\in\mathbb{N}$，然后 $a_i=a_j$。

问 $t$ 次后大于等于 $k$ 种数的概率。

题解

首先，$t$ 很大，达到了 $10^{18}$ 级别，矩阵乘法显然。

考虑维护状态，如果维护每一个数有多少个，有 $10^{10}$ 的空间，显然不可行。

发现一个性质，只需要记录每一个数有多少个，并且不用关心是哪一种数有多少个。

举个例子，1 1 2 2 3 和 2 2 5 7 5 在我们认为是一样的，因为都是有 $2$ 种数字有 $2$ 个，$1$ 种数字有 $1$ 个。

所以，只需要记录每一种有数字有多少个就好了。

我们可以从小到大排序，把每一个数有多少个进行一个状压（直接用十进制，反正比较小）。

状态总数是一个插板问题，$\sum\limits_{i=1}^{n-1}C_{n-1}^{i-1}$，最大值当 $n=10$ 的时候取到最大值为 $2^{9}-1$，给一个巧算的方法，看成集合里取子集，每个元素可以取或者不取，总共 $2^{n-1}$ 种方法，注意没有切 $n-1$ 刀，所以就是 $2^9-1$。

复杂度 $O(511^3\times\log t)$，显然无法通过。

发现记录每一种数字有多少个也没有关系，比如我们第 $i$ 种数字有 $cnt_i$ 个，我们统计的只是 $cnt$ 序列单调递增的就行了，因为数字变一下是没有关系的。

那么，有多少种呢？

感觉不是很多，手枚一下。

1 : 1 1 1 1 1 1 1 1 1 1
2 : 1 1 1 1 1 1 1 1 2 
3 : 1 1 1 1 1 1 1 3  
4 : 1 1 1 1 1 1 2 2  
5 : 1 1 1 1 1 1 4   
6 : 1 1 1 1 1 2 3    
7 : 1 1 1 1 2 2 2   
8 : 1 1 1 1 1 5    
9 : 1 1 1 1 2 4    
1: 1 1 1 1 3 3    
11: 1 1 1 2 2 3    
12: 1 1 2 2 2 2    
13: 1 1 1 1 6     
14: 1 1 1 2 5     
15: 1 1 1 3 4     
16: 1 1 2 2 4     
17: 1 1 2 3 3     
18: 1 2 2 2 3     
19: 2 2 2 2 2
20: 1 1 1 7      
21: 1 1 2 6      
22: 1 1 3 5      
23: 1 1 4 4      
24: 1 2 2 5      
25: 1 2 3 4      
26: 1 3 3 3      
27: 2 2 2 4      
28: 2 2 3 3      
29: 1 1 8        
30: 1 2 7       
31: 1 3 6        
32: 1 4 5       
33: 2 2 6       
34: 2 3 5        
35: 2 4 4       
36: 3 3 4        
37: 1 9        
38: 2 8        
39: 3 7        
40: 4 6        
41: 5 5      
42: 10       

上面是真的手枚的 $n=10$ 的情况（除了我一开始把第 $19$ 个落下了）。

所以我们可以写出代码：

大家可以手枚 $n=1,2,3,4,5,6,7,8,9$ 的情况，然后手动分类讨论一下就好了。

复杂度最大 $O(42^3\times\log t)$，可以通过。

不放代码。

这个代码一看就又臭有长，难写难调浪费时间，不放的原因是我没写。

而写手枚容易错。

那就用程序啊。

程序的作用不仅仅打标，还可以处理出转移矩阵。

用程序进行 bfs，遇到一个没遇到的就入队，只要搜到的，就加上贡献。

最后都除以 $n^2$，就是乘上逆元。

然后代码就写好了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, t, k, inv, a[15], sum[45], H, T, now, S, res, num[45], cnt[15], tem, tt;
map<int, int>f;
struct martix{
	int a[45][45];
	martix(){
		memset(a, 0, sizeof(a));
	}
	inline void init(){
		for(int i = 1; i <= T; i++) a[i][i] = 1;
	}
	inline void print(){
		for(int i = 1; i <= T; i++){
			for(int j = 1; j <= T; j++){
				printf("%lld ", a[i][j]);
			}
			putchar('\n');
		}
	}
}base, ans;
inline int qp(int x, int y){
	int res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod, y >>= 1;
	}
	return res;
}
inline martix operator * (martix x, martix y){
	martix res;
	for(int i = 1; i <= T; i++){
		for(int k = 1; k <= T; k++){
			if(x.a[i][k] == 0) continue ;
			for(int j = 1; j <= T; j++){
				res.a[i][j] += x.a[i][k] * y.a[k][j] % mod;
				res.a[i][j] %= mod;
			}
		}
	}
	return res;
}
inline int calc(int x){
	S = 0; 
	for(int i = 1; x; i++){
		cnt[i] = x % 10;
		S++;
		x /= 10;
	}
	now = 0;
	for(int i = 1; i <= S; i++){
		for(int j = 1; j <= cnt[i]; j++){
			a[++now] = i;
		}
	}
	return S;
}
inline int work(){
	for(int i = 1; i <= 10; i++) sum[i] = 0;
	for(int i = 1; i <= n; i++) sum[a[i]]++;
	int res = 0;
	sort(sum + 1, sum + 11);
	for(int i = 1; i <= 10; i++){
		res = res * 10 + sum[i];
	}
	return res;
}
inline void bfs(){
	for(int i = 1; i <= n; i++) a[i] = i;
	tem = work();
	f[tem] = 1;
	num[T = 1] = tem;
	while(H < T){
		H++;
		calc(num[H]);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				tt = a[j];
				a[j] = a[i];
				tem = work();
				if(f[tem] == 0){
					f[tem] = ++T;
					num[T] = tem;
				}
				base.a[H][f[tem]]++;
				a[j] = tt;
			}
		}
	}
}
inline martix ksm(martix x, int y){
	martix res;
	res.init();
	while(y){
		if(y & 1) res = res * x;
		x = x * x, y >>= 1;
	}
	return res;
}
signed main(){
	scanf("%lld%lld%lld", &n, &t, &k);
	inv = qp(n * n, mod - 2);
	bfs();
	for(int i = 1; i <= T; i++) for(int j = 1; j <= T; j++) base.a[i][j] = base.a[i][j] * inv % mod;
	base = ksm(base, t);
	ans.a[1][1] = 1;
	ans = ans * base;
	for(int i = 1; i <= T; i++){
		if(calc(num[i]) >= k){
			res += ans.a[1][i];
			res %= mod;
		}
	}
	printf("%lld", res);
	return 0;
} 

如果不懂，可以评论/私信。