原来这个也叫做倍增...

懒得打$lat_{e}^x$，就直接贴图了

 

这个数据正解应该是矩阵快速幂的，但是大佬们想出了各种神奇的方法，一个个数竞的一样...

实现的话要记忆化，因为是二维的大数，所以直接用map就好了

然后的话，因为组合数要求的其实很小，你直接杨辉三角上是一样的..

 

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 inline int read(){
 5     int ans=0,f=1;char chr=getchar();
 6     while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
 7     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 8     return ans*f;
 9 }const int P=1e9+7;
10 int n,k,inv[25],fac[25],R;
11 inline void Pre(){
12     fac[0]=1;
13     for(int i=1;i<=20;i++) fac[i]=fac[i-1]*i%P;
14     inv[0]=inv[1]=1;
15     for(int i=2;i<=20;i++) inv[i]=(P-P/i)*inv[P%i]%P;
16     for(int i=1;i<=20;i++) inv[i]=inv[i-1]*inv[i]%P;
17 }
18 inline int ksm(int x,int y){
19   int ret=1; x%=P;
20   for(;y;y>>=1,x=x*x%P) if(y&1) ret=ret*x%P;
21   return ret;
22 }
23 map<pair<int,int>,int> mp;
24 int C(int x,int y){return fac[x]*inv[y]%P*inv[x-y]%P;}
25 int f(int n,int k){
26     if(n==0) return 0;
27     if(n==1) return R;
28     if(mp[make_pair(n,k)]) return mp[make_pair(n,k)];
29     if(n&1){
30         int tmp=f(n-1,k);
31         tmp=(tmp+ksm(R,n)*ksm(n,k))%P;
32         return mp[make_pair(n,k)]=tmp;
33     }int tmp=f(n>>1,k),a=0;
34     n>>=1;
35     for(int i=0;i<=k;i++) a=(a+C(k,i)*ksm(n,k-i)%P*f(n,i))%P;
36     tmp=(tmp+a*ksm(R,n)%P)%P;
37     return mp[make_pair(n<<1,k)]=tmp;
38 }
39 signed main(){
40     Pre();
41     R=(P+1)>>1;
42     n=read(),k=read();
43     int ans=(ksm(n,k)+ksm(2,n-1)*f(n-1,k)%P)%P;
44     cout<<ans<<endl;
45     return 0;
46 }