「SNOI2017」礼物

题目链接：Click here

Solution:

设\(f(x)\)代表第\(x\)个人送的礼物的数量，\(s(x)\)代表\(f(x)\)的前缀和，即：

\[f(x)=s(x-1)+x^k\\
s(x)=s(x-1)+f(x)\\
s(x)=2\times s(x-1)+x^k
\]

则我们只需求出\(s(n-1)\)即可，\(n\le1e18\)，考虑矩阵快速幂优化\(dp\)

这里唯一麻烦的就是\(x^k\)，考虑二项式定理：\((x+1)^k=\sum_{i=0}^k{k\choose i}x^{k-i}\)

则我们得到这样的转移：

\[\left[
\begin{matrix}
2&C_k^0&C_k^1&\dots &C_k^k\\
0&C_k^0&C_k^1&\dots &C_k^k\\
0&0&C_{k-1}^0&\dots &C_{k-1}^{k-1}\\
\vdots&\ddots&\dots& &\vdots\\
0&0&0&\dots&C_0^0
\end{matrix}
\right]
\left[
\begin{matrix}
s(x)\\
x^k\\
x^{(k-1)}\\
\vdots\\
x^0
\end{matrix}
\right]
=
\left[
\begin{matrix}
s(x+1)\\
(x+1)^k\\
(x+1)^{(k-1)}\\
\vdots\\
(x+1)^0
\end{matrix}
\right]
\]

Code:

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int mod=1e9+7;

int n,k,c[11][11];

struct Matrix{

    int g[12][12],w,h;

    void init(){memset(g,0,sizeof(g));}

    void org(){for(int i=0;i<12;i++)g[i][i]=1;}

    friend Matrix operator *(Matrix a,Matrix b){

        Matrix tmp;tmp.w=a.w;tmp.h=b.h;tmp.init();

        for(int i=0;i<a.w;i++)

            for(int j=0;j<b.h;j++)

                for(int k=0;k<a.h;k++)

                    tmp.g[i][j]=(tmp.g[i][j]+(a.g[i][k]*1ll*b.g[k][j])%mod)%mod;

        return tmp;

    }

};

Matrix qpow(Matrix a,int b){

    Matrix re;re.w=re.h=k+2;

    re.init();re.org();

    while(b){

        if(b&1) re=re*a;

        b>>=1;a=a*a;

    }return re;

}

int pow(int a,int b){

    int re=1;

    while(b){

        if(b&1) re=(re*1ll*a)%mod;

        b>>=1;a=(a*1ll*a)%mod;

    }return re;

}

int read(){

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

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

    return x*f;

}

signed main(){

    n=read(),k=read();

    for(int i=0;i<=k;i++) c[i][i]=c[i][0]=1;

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

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

            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

    Matrix trans;trans.w=k+2,trans.h=k+2;

    trans.init();trans.g[0][0]=2;

    for(int i=1;i<=k+1;i++) trans.g[0][i]=c[k][i-1];

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

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

            trans.g[i][j]=c[k+1-i][j-i];

    if(n==1) return puts("1"),0;

    trans=qpow(trans,n-2);

    Matrix ans;ans.w=k+2;ans.h=1;ans.init();

    for(int i=0;i<=k+2;i++) ans.g[i][0]=1;

    ans=trans*ans;printf("%lld\n",(ans.g[0][0]+pow(n%mod,k))%mod);

    return 0;

}

巴特西

「SNOI2017」礼物

Solution:

Code:

最新文章

热门文章