[BZOJ5015] [Snoi2017]礼物

题目描述

Description

热情好客的请森林中的朋友们吃饭,他的朋友被编号为 1~N,每个到来的朋友都会带给他一些礼物:。其中,第一个朋友会带给他 1 个,之后,每一个朋友到来以后,都会带给他之前所有人带来的礼物个数再加他的编号的 K 次方那么多个。所以,假设 K=2,前几位朋友带来的礼物个数分别是1,5,15,37,83假设 K=3,前几位朋友带来的礼物个数分别是:1,9,37,111现在,好奇自己到底能收到第 N 个朋友多少礼物,因此拜托于你了。已知 N,K请输出第 N 个朋友送的礼物个数 mod1000000007。
PDF题面:www.lydsy.com/JudgeOnline/upload/gift.pdf

Input

第一行,两个整数 N,K N≤10^18,K≤10

Output

一个整数,表示第 N 个朋友送的礼物个数 mod1000000007。

Sample Input

4 2

Sample Output

37

题目分析

a[n]a[n]为答案,sum[n]=i=1na[i]sum[n]=\sum\limits_{i=1}^{n} a[i]
那么就有:
a[n]=sum[n1]+nk,sum[n]=2sum[n1]+nk a[n]=sum[n-1]+n^k,sum[n]=2*sum[n-1]+n^k
因为N很大 所以我们要考虑矩乘
关键是怎么从iki^k转移到(i+1)k(i+1)^k
不怕 我们有二项式定理:(i+1)k=j=0kCkjij1kj (i+1)^k =\sum\limits_{j=0}^{k}C^j_{k}*i^j*1^{k-j}
据此 我们可以得到转移矩阵如下:
[aij=1iaj1i1i2i3ik]×[0000000 1200000 Ck0Ck0C00C10C20Ck10Ck0 Ck1Ck10C11C21Ck11Ck1 Ck2Ck200C22Ck12Ck2  Ckk1Ckk1000Ck1k1Ckk1 CkkCkk0000Ckk]=\begin{bmatrix} a_i & \sum\limits_{j=1}^i{a_j} & 1 & i^1 & i^2 & i^3 & \cdots & i^k \end{bmatrix} \times \begin{bmatrix} \:0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\\ 1 & 2 & 0 & 0 & 0 & \cdots & 0 & 0 \\\ C^{0}_k & C^{0}_k & C^{0}_0 & C^{0}_1 & C^{0}_2 & \cdots & \: \: \: C^{0}_{k-1} & C^{0}_k \\\ C^{1}_k & C^{1}_k & 0 & C^{1}_1 & C^{1}_2 & \cdots & \: \: \: C^{1}_{k-1} & C^{1}_k \\\ C^{2}_k & C^{2}_k & 0 & 0 & C^{2}_2 & \cdots & \: \: \: C^{2}_{k-1} & C^{2}_k \\\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\\ \: \: \: C^{k-1}_k & \: \: \: C^{k-1}_k & 0 & 0 & 0 & \cdots & \: \: \: C^{k-1}_{k-1} & \: \: \: C^{k-1}_k \\\ C^{k}_k & C^{k}_k & 0 & 0 & 0 & \cdots & 0 & C^{k}_k \end{bmatrix}=
[ai+1j=1i+1aj1(i+1)1(i+1)2(i+1)3(i+1)k]\begin{bmatrix} a_{i+1} & \sum\limits_{j=1}^{i+1} a_j & 1 & (i+1)^1 & (i+1)^2 & (i+1)^3 & \cdots & (i+1)^k \end{bmatrix}

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
long long m,mod=1000000007,c[20][20];
struct your
{
    long long x[20][20]; 
    your() { memset(x,0,sizeof x); }
    friend your operator*(your x,your y)
    {
        your z;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int l=1;l<=n;l++)
                    z.x[i][j]=(z.x[i][j]+x.x[i][l]*y.x[l][j]%mod)%mod;
        return z;
    }
}A,B;
void ksm(long long y)
{
    while(y)
    {
        if(y&1) A=A*B;
        y>>=1,B=B*B;
    }
}   
void init()
{
    c[0][0]=1;
    for(int i=1;i<=10;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    A.x[1][1]=A.x[1][2]=1;
    for(int i=0;i<=k;i++) A.x[1][i+3]=1;
    B.x[2][1]=1,B.x[2][2]=2;
    for(int i=0;i<=k;i++) B.x[i+3][1]=B.x[i+3][2]=c[k][i];
    for(int i=0;i<=k;i++)
        for(int j=0;j<=i;j++) B.x[j+3][i+3]=c[i][j];
}
int main()
{   
    scanf("%lld%d",&m,&k),n=3+k;
    init(),ksm(m-1);
    printf("%lld",A.x[1][1]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注