SPOJ

Luogu

分析

为了方便，设
$$
\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}
$$
把斐波那契数列的通项式代入得到
$$
\begin{aligned}
D(n,x)&=\sum_{i=1}^n\frac{\alpha^i-\beta^i}{\sqrt{5}}\times x^i\\
&=\frac{1}{\sqrt{5}}\left(\left(\sum_{i=1}^n(\alpha x)^i\right)-\left(\sum_{i=1}^n(\beta x)^i\right)\right)
\end{aligned}
$$
两个求和号中的部分利用等比数列求和公式计算即可。

但是 $5$ 在模 $10^9+7$ 意义下没有二次剩余，所以需要扩域。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}
const int inv2=qpow(2,mod-2),inv5=qpow(5,mod-2);

inline int sum(int a,int b) { return (a+b)%mod; }
inline int sub(int a,int b) { return (a-b+mod)%mod; }
inline int mul(int a,int b) { return 1ll*a*b%mod; }

struct num { //x+y*sqrt{5}
    int x,y;
    num(int x_=0,int y_=0):x(x_%mod),y(y_%mod) { }
};
num operator +(num a,num b) {
    return num(sum(a.x,b.x),sum(a.y,b.y));
}
num operator -(num a,num b) {
    return num(sub(a.x,b.x),sub(a.y,b.y));
}
num operator *(num a,num b) {
    return num(sum(mul(a.x,b.x),mul(5,mul(a.y,b.y))),
               sum(mul(a.x,b.y),mul(a.y,b.x)));
}
num operator /(num a,num b) {
    return num(sub(mul(a.x,b.x),mul(5,mul(a.y,b.y))),
               sub(mul(a.y,b.x),mul(a.x,b.y)))*
               qpow(sub(mul(b.x,b.x),mul(5,mul(b.y,b.y))),mod-2);
}

inline num qpow(num a,ll b) { num c=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

inline num sum(num x,ll n) { return (x-qpow(x,n+1))/(1-x); }

int main() { int T=read();
    while (T--) {
        ll n=read(); int x=read()%mod;
        num A=sum(num(inv2,inv2)*x,n),B=sum(num(inv2,-inv2)*x,n);
        printf("%d\n",(num(0,inv5)*(A-B)).x);
    }
    return 0;
}