题面

题解

把求和的柿子用斐波那契数列的通项公式展开

\[ \begin{aligned} Ans &=\sum\limits_{i = 1}^{n} \left(\frac{(\frac{1 + \sqrt{5}}{2})^{i} - (\frac{1 - \sqrt{5}}{2})^{i}}{\sqrt{5}}\right)^{k} \\ &= \left(\frac{1}{\sqrt{5}}\right)^{k}\sum\limits_{i = 1}^{n} \sum\limits_{j = 0}^{k}{k \choose j}(-1)^{k - j}\left(\frac{1 + \sqrt{5}}{2}\right)^{ij}\left(\frac{1 - \sqrt{5}}{2}\right)^{i(k - j)} \\ &= \left(\frac{1}{\sqrt{5}}\right)^{k}\sum\limits_{j = 0}^{k}{k \choose j}(-1)^{k - j}\sum\limits_{i = 1}^{n} \left(\left(\frac{1 + \sqrt{5}}{2}\right)^{j}\left(\frac{1 - \sqrt{5}}{2}\right)^{k - j}\right)^{i}\\ \end{aligned} \]

后面就是个等比数列求和公式，直接算就行了

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;const int N=1e5+5,P=1e9+9,s=383008016;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R ll y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}int inv[N],fac[N],ifac[N],v1[N],v2[N],k,res,p,q;ll n;inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}inline int Inv(R int n){return n