[bzoj5015][Snoi2017]礼物

来自FallDream的博客，未经允许，请勿转载，谢谢。

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

N≤10^18,K≤10

首先把它给你的数字前缀和一下得到递推式f[i]=2*f[i-1]+i^k

构造一个k+2维的矩阵，一维维护答案，另外分别维护i的0到k次方数字。

转移矩阵的话，n^k -> (n+1)^k ，把后面的用组合数拆开就行了。

复杂度k^3logn

#include<iostream>

#include<cstring>

#include<cstdio>

#define mod 1000000007

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int k,C[][];long long n;

struct Matrix

{

    int s[][];

    Matrix(){memset(s,,sizeof(s));}

    Matrix operator * (const Matrix&b)

    {

        Matrix c;

        for(int i=;i<=k+;++i)

            for(int j=;j<=k+;++j)

                for(int K=;K<=k+;++K)

                    c.s[i][j]=(c.s[i][j]+1LL*s[i][K]*b.s[K][j])%mod;

        return c;

    }

    void print()

    {

        for(int i=;i<=k+;++i,puts(""))

            for(int j=;j<=k+;++j)

                printf("%d ",s[i][j]);

    }

}A,B,c,d;

int Solve(long long N)

{

    A=c;B=d;

    for(;N;N>>=,A=A*A) if(N&) B=A*B;

    return B.s[k+][];

}

int main()

{

    for(int i=;i<=;++i) C[i][]=;

    for(int i=;i<=;++i)for(int j=;j<=i;++j) C[i][j]=(C[i-][j-]+C[i-][j])%mod;

    cin>>n>>k;

    A.s[k+][k+]=;A.s[k+][k]=;A.s[][]=;

    for(int i=;i<=k;++i)

    {

        B.s[i][]=;

        for(int j=;j<=i;++j)

            A.s[i][j]=C[i][i-j];

    }

    c=A;d=B;

    printf("%d\n",(Solve(n)-Solve(n-)+mod)%mod);

    return ;

}

巴特西

[bzoj5015][Snoi2017]礼物

最新文章

热门文章