bzoj 5015 [Snoi2017]礼物 矩阵乘法

时间：2021-06-29 10:04:07

5015: [Snoi2017]礼物

Time Limit: 15 Sec  Memory Limit: 512 MB
Submit: 163  Solved: 115
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

4 2

Sample Output

37

%%cqzhangyu https://www.cnblogs.com/CQzhangyu/p/7500294.html

很好想的吧。

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #define ll long long

 #define mod 1000000007

 #define N 20

 #define Wb putchar(' ')

 #define We putchar('\n')

 using namespace std;

 inline ll read()

 {

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

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

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 inline void write(ll x)

 {

     if(x<) putchar('-'),x=-x;

     if (x==) putchar();

     int num=;char c[];

     while(x) c[++num]=(x%)+,x/=;

     while(num) putchar(c[num--]);

 }

 ll n,K;

 ll c[N][N];

 struct Node

 {

     ll a[N][N];

     void init()

     {

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

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

                 a[i][j]=;

     }

     friend Node operator*(Node x,Node y)

     {

         Node t;t.init();

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

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

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

                     t.a[i][j]=(t.a[i][j]+x.a[i][k]*y.a[k][j])%mod;

         return t;

     }

 }dw,a,b;

 void fast_pow(Node &ans,Node a,ll b)

 {

     while(b)

     {

         if (b&) ans=ans*a;

         a=a*a;

         b>>=;

     }

 }

 int main()

 {

     n=read(),K=read();

     for (int i=;i<=K;i++)c[i][]=;

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

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

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

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

         a.a[][i]=b.a[][i]=;

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

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

             dw.a[i][j]=c[j-][i-];

     dw.a[][]=;

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

         dw.a[i][]=c[K][i-];

     if (n==) write();

     else

     {

         fast_pow(a,dw,n-),fast_pow(b,dw,n-);

         ll ans=b.a[][]-a.a[][];

         write((ans%mod+mod)%mod);

     }

 }

相关文章