[SNOI2017]礼物

佚名 6年前 (2019-05-11) 随笔 1131人围观抢沙发百度已收录

这题太傻了，众所周知二项式定理

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

\[(x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k\]

于是把这个组合数放到矩阵里转移就好了

由于矩阵长得很特殊接近一个下三角，于是可以魔改一波优化常数

代码

#include<cstdio>
#define re register
const int mod=1e9+7;
struct mat {int a[15][15];}S,a;
long long n;int k,sz; 
int c[15][15];
inline mat operator*(mat a,mat b) {
    mat c;
    for(re int i=0;i<sz;i++)
        for(re int j=0;j<sz;j++)
            c.a[i][j]=0;
    for(re int i=0;i<=k;i++)
        for(re int j=0;j<=i;j++)
            for(re int t=0;t<=i;t++) 
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][t]*b.a[t][j]%mod)%mod;
    for(re int i=k+1;i<sz;i++)
        for(re int j=0;j<sz;j++) {
            if(j==k+1) continue;
            for(re int t=0;t<sz;t++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][t]*b.a[t][j]%mod)%mod;
        }
    return c;
}
int main() {
    scanf("%lld%d",&n,&k);
    for(re int i=0;i<=k;i++) c[i][0]=c[i][i]=1;
    for(re int i=2;i<=k;i++)
        for(re int j=1;j<i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    sz=k+3;
    for(re int i=0;i<=k;i++)
        for(re int j=0;j<=i;j++)
            a.a[i][j]=c[i][j];
    for(re int j=0;j<=k;j++)
        a.a[k+1][j]=a.a[k+2][j]=c[k][j];
    a.a[k+1][k+2]=1;a.a[k+2][k+2]=2;
    S=a;n--;
    while(n) {if(n&1ll) S=S*a;n>>=1ll;a=a*a;}
    printf("%d\n",S.a[k+1][0]);
    return 0;
}