题意：求Σfi^m%p。 zoj上p是1e9+7，牛客是1e9； 对于这两个，分别有不同的做法。
前者利用公式，公式里面有sqrt(5)，我们只需要二次剩余求即可。 后者mod=1e9，5才mod下没有二次剩余，所以不能这么做了。可以分解mod，然后利用循环节搞。
zoj：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = ;
const LL MOD = ;
LL fac[N],A[N],B[N];
void Init()
{
fac[] = ;
for(int i=; i<N; i++)
fac[i] = fac[i-] * i % MOD;
A[] = B[] = ;
for(int i=; i<N; i++)
{
A[i] = A[i-] * % MOD;
B[i] = B[i-] * % MOD;
}
}
LL quick_mod(LL a,LL b,LL MOD)
{
LL ans = ;
a %= MOD;
while(b){
if(b&){
ans = ans * a % MOD;
b--;
}
b>>=; a = a * a % MOD;
}
return ans;
} LL Solve(LL n,LL k)
{
LL ans = ;
for(int r=; r<=k; r++)
{
LL t = A[k-r] * B[r] % MOD;
LL x = fac[k];
LL y = fac[k-r] * fac[r] % MOD;
LL c = x * quick_mod(y,MOD-,MOD) % MOD;
LL tmp = t * (quick_mod(t,n,MOD) - ) % MOD * quick_mod(t-,MOD-,MOD) % MOD;
if(t == ) tmp = n % MOD;
tmp = tmp * c % MOD;
if(r & ) ans -= tmp;
else ans += tmp;
ans %= MOD;
}
LL m = quick_mod(,MOD-,MOD);
ans = ans * quick_mod(m,k,MOD) % MOD;
ans = (ans % MOD + MOD) % MOD;
return ans;
} int main()
{
int T;
LL n,k;
Init();
scanf("%d",&T);
while(T--)
{
cin>>n>>k;
cout<<Solve(n,k)<<endl;
}
return ;
}
牛客： 你可以不熟悉斐波拉契的循环节具体怎么求，但是只要知道mod=p^a，fib[]%mod的循环节小于p^(a-1)* (2*p+2)。
而1e9计较特殊，1e9=2^9*5^9，这两部分对应的循环节都不是很大，所以我们可以分别求，然后中国剩余定理合并啊，就可以水过去了。
(但是我的代码怎么这么慢啊
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int Mod=1e9;
int md[]={,};
int f[],ans[];
int qpow(int a,int x,int p)
{
int res=; while(x){
if(x&) res=1LL*res*a%p;
x>>=; a=1LL*a*a%p;
} return res;
}
void exgcd(int a,int b,int &x,int &y)
{
if(b==){ x=; y=; return;}
exgcd(b,a%b,y,x); y-=a/b*x;
}
int rev(int a,int b)
{
int x,y; exgcd(a,b,x,y);
x=(x%b+b)%b; return x;
}
int main()
{
int N,M;
scanf("%d%d",&N,&M);
rep(k,,) {
f[]=; f[]=; int j=;
for(;;j++){
f[j]=(f[j-]+f[j-]);
if(f[j]>=md[k]) f[j]-=md[k];
if(f[j]==&&f[j-]==) {
j--; break;
}
}
int P=N/j;
for(int i=;i<j;i++) {
int t=qpow(f[i],M,md[k]);
ans[k]=(ans[k]+1LL*t*(P+(i<=N%j)))%md[k];
}
}
int res=(1LL*ans[]*md[]%Mod*rev(md[],md[])%Mod+1LL*ans[]*md[]%Mod*rev(md[],md[])%Mod)%Mod;
printf("%d\n",res);
return ;
}