题目链接
题目思路
其实本题就是第二类特兰数的式子
\(dp[i][j]=dp[i-1][j]*(i-1)+dp[i][j-1]*(k-j+1);\)
但是\(n\)太大，所以使用矩阵快速幂递推
然后再对所有矩阵求和即可
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=31,inf=0x3f3f3f3f,mod=1234567891;
const double eps=1e-6;
int n,k;
struct matrix{
ll a[maxn][maxn];
}base,basetemp,ans,zero;
matrix mul(matrix a,matrix b){
matrix temp;
memset(temp.a,0,sizeof(temp.a)); //一定1要清空
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
temp.a[i][k]+=(a.a[i][j])*(b.a[j][k]);
temp.a[i][k]%=mod;
}
}
}
return temp;
}
matrix add(matrix a,matrix b){
matrix temp;
memset(temp.a,0,sizeof(temp.a)); //一定1要清空
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
temp.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
}
}
return temp;
}
matrix qpow(ll n,ll b){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
ans.a[i][j]=(i==j);
base.a[i][j]=basetemp.a[i][j];
}
}
while(b){
if(b&1){
ans=mul(ans,base);
}
base=mul(base,base);
b=b>>1;
}
return ans;
}
matrix dfs(int x){
if(x==0){
return zero;
}
if(x%2==1){
matrix temp1=qpow(n,x);
x--;
matrix temp2=dfs(x);
matrix tempsum=add(temp1,temp2);
return tempsum;
}else{
matrix temp1=qpow(n,x/2);
for(int i=0;i<=n;i++){
temp1.a[i][i]=(temp1.a[i][i]+1)%mod;
}
matrix temp2=dfs(x/2);
matrix tempsum=mul(temp1,temp2);
return tempsum;
}
}
signed main(){
// dp[i][j]=dp[i-1][j]*(i-1)+dp[i][j-1]*(k-j+1);
int _;scanf("%d",&_);
while(_--){
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++){
basetemp.a[i][i]=i;
basetemp.a[i-1][i]=n-i+1;
}
matrix pr=dfs(k);
printf("%lld\n",pr.a[0][n]);
}
return 0;
}