Pendant

/*题意：有k种珍珠，每种n个，现在问你能组成多少长度为1~n的珍珠项链，要求每条项链必须有k中珍珠初步思路：......没思路算是思路么？#补充：看了一下题解，dp搞，dp[i][j]表示长度为i，用j种珍珠的方案，状态转移方程为：    dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(k-j+1); 长度为i 用j种珍珠的方案，用长度为i-1 用j种    珍珠的项链再从j种珍珠中再拿一个组成长度为i，用j种珍珠的项链，在加上长度为i，用j-1种珍珠    的项链再选另外的k-(j-1)种珍珠组成长度为i，用j种珍珠的项链。        答案为，dp[1][k]+dp[2][k]+...+dp[n][k]            写的时候是不容易实现的，因为dp数组开不到3e10，所以只能用矩阵来求递推公式。*/#include<bits/stdc++.h>#define mod 1234567891#define ll long longusing namespace std;/********************************矩阵模板**********************************/class Matrix {    public:        ll a[31][31];        int n;          void init(int x) {            memset(a,0,sizeof(a));            if (x)                  for (int i = 0; i < 31 ; i++)                    a[i][i] = 1;        }        Matrix operator +(Matrix b) {            Matrix c;            c.n = n;            for (int i = 0; i < n; i++)                for (int j = 0; j < n; j++)                    c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;            return c;        }        Matrix operator +(int x) {            Matrix c = *this;            for (int i = 0; i < n; i++)                c.a[i][i] += x;            return c;        }        Matrix operator *(Matrix b)        {            Matrix p;            p.n = b.n;               p.init(0);            for (int i = 0; i < n; i++)                for (int j = 0; j < n; j++)                for (int k = 0; k < n; k++)                    p.a[i][j] = (p.a[i][j] + (a[i][k]*b.a[k][j])%mod) % mod;            return p;        }        Matrix power(ll t) {            Matrix ans,p = *this;            ans.n = p.n;              ans.init(1);            while (t) {                if (t & 1)                    ans=ans*p;                p = p*p;                t >>= 1;            }            return ans;        }};Matrix unit;int t;ll n;int k;/********************************矩阵模板**********************************/int main(){    // freopen("in.txt","r",stdin);    scanf("%d",&t);    while(t--){        scanf("%d%lld",&n,&k);        k++;        unit.init(0);        unit.n=k;        for(int i=0;i<k-1;i++){            unit.a[i][i]=i+1;            unit.a[i][i+1]=k-i-2;        }        unit.a[k-1][k-1]=unit.a[k-2][k-1]=1;        unit=unit.power(n);        // for(int i=0;i<k;i++){            // for(int j=0;j<k;j++){                // cout<<unit.a[i][j]<<" ";            // }            // cout<<endl;        // }        printf("%lld\n",(k-1)*unit.a[0][k-1]%mod);    }    return 0;}