
Lv.1
沙 雕 一 个
在 【C++教程】一起++ 第7弹 循环(下) 中回复
#include<cstdio>
#define FN(S) F operator S (const F& x) const
#define ull long long
#define v ((p+1)>>1)
#define p 1000000007
struct F
{
ull a,b;
F(ull a=0,ull b=0):a(a),b(b){}
FN(+){return{(a+x.a)%p,(b+x.b)%p};}
FN(-){return{(a-x.a+p)%p,(b-x.b+p)%p};}
FN(*){return{(a*x.a+5*b*x.b)%p,(a*x.b+x.a*b)%p};}
};
inline F P(F a,ull t)
{
F r = F(1,0);
while(t){if(t&1)r=r*a;a=a*a;t>>=1;}
return r;
}
int main()
{
ull n;
scanf("%lld",&n);
printf("%lld",(P(F(v,v),n)-P(F(v,v-1),n)).b);
return 0;
}
2026-01-06T21:30:38 点赞:0
在 【爵士的简单易懂的C++ OI教程】数论问题全面详解 中回复
typedef long long int ll;
ll exgcd(ll a,ll b,ll*x,ll*y)
{
if(!b)return*x=1,*y=0,a;
ll d=exgcd(b,a%b,y,x);
*y-=a/b**x;
return d;
}//这里给出不用tmp的ecgcd解法
2026-01-06T21:36:12 点赞:0