```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define N 10003
#define pi 3.141592653589793
using namespace std;
struct BigInt{
int num[N];
int size;
bool negative;
bool operator < (const BigInt& a) const{
if(a.negative&&!negative) return false;
if(negative&&!a.negative) return true;
bool f = negative;
for(int i=size;i>=1;--i){
if(a.num[i]==num[i]) continue;
if(f) return num[i]>a.num[i];
else return num[i]<a.num[i];
}
return false;
}
bool operator > (const BigInt& a) const{
if(a.negative&&!negative) return true;
if(negative&&!a.negative) return false;
bool f = negative;
for(int i=size;i>=1;--i){
if(a.num[i]==num[i]) continue;
if(!f) return num[i]>a.num[i];
else return num[i]<a.num[i];
}
return false;
}
bool operator == (const BigInt& a) const{
if(negative!=a.negative) return false;
if(size!=a.size) return false;
for(int i=size;i>=1;--i)
if(num[i]!=a.num[i]) return false;
return true;
}
};
struct complex{
double r,i;
complex(double r=0,double i=0):r(r),i(i){}
complex operator + (const complex& a) const{
return complex(r+a.r,i+a.i);
}
complex operator * (const complex& a) const{
return complex(r*a.r-i*a.i,r*a.i+i*a.r);
}
complex operator - (const complex& a) const{
return complex(r-a.r,i-a.i);
}
};
int rev_[N];
complex F[N],G[N];
void FFT(complex *a,int type,int lim){
for(int i=0;i<lim;++i){
if(i>=rev_[i]) continue;
swap(a[i],a[rev_[i]]);
}
for(int mid=1;mid<lim;mid<<=1){
complex rt = complex(cos(pi/mid),type*sin(pi/mid));
int r = mid<<1;
for(int j=0;j<lim;j+=r){
complex w = complex(1,0);
for(int k=0;k<mid;++k){
complex x = a[j+k];
complex y = w*a[j+k+mid];
a[j+k] = x+y;
a[j+k+mid] = x-y;
w = w*rt;
}
}
}
}
inline BigInt newBigInt(string n){
int t = 0;
BigInt a;
memset(a.num,0,sizeof(a.num));
a.size = n.length();
if(n[0]=='-'){
t = 1;
a.size--;
}
for(int i=1;i<=a.size;++i)
a.num[i] = n[a.size-i+t]-'0';
a.negative = (t==0)?false:true;
return a;
}
inline BigInt toBigInt(int a){
BigInt b = newBigInt("0");
int l = 1;
if(a<0){
a = -a;
b.negative = true;
}
while(a){
b.num[l] = a%10;
a /= 10;
++l;
}
b.size = l-1;
return b;
}
const BigInt ZERO = newBigInt("0");
const BigInt ONE = newBigInt("1");
const BigInt TWO = newBigInt("2");
const BigInt TEN = newBigInt("10");
void print(BigInt a){
int l = a.size;
if(a.negative) putchar('-');
for(int i=l;i>=1;--i)
putchar(a.num[i]+'0');
}
BigInt add(BigInt a,BigInt b);
BigInt subtract(BigInt a,BigInt b);
BigInt multiply(BigInt a,BigInt b){
int l,n,m,lim,cnt;
if(a==ZERO||b==ZERO) return ZERO;
BigInt c = ZERO;
cnt = l = 0;
lim = 1;
n = a.size-1;
m = b.size-1;
memset(F,0,sizeof(F));
memset(G,0,sizeof(G));
for(int i=0;i<=n;++i) F[i].r = a.num[i+1];
for(int i=0;i<=m;++i) G[i].r = b.num[i+1];
cnt = n+m;
while(lim<=cnt){
lim <<= 1;
++l;
}
for(int i=0;i<lim;++i)
rev_[i] = (rev_[i>>1]>>1)|((i&1)<<(l-1));
FFT(F,1,lim);
FFT(G,1,lim);
for(int i=0;i<=lim;++i)
F[i] = F[i]*G[i];
FFT(F,-1,lim);
for(int i=0;i<=cnt;++i)
c.num[i+1] = F[i].r/lim+0.5;
++cnt;
for(int i=1;i<=cnt;++i){
if(c.num[i]<10) continue;
c.num[i+1] += c.num[i]/10;
c.num[i] %= 10;
}
while(c.num[cnt+1]>0) ++cnt;
int i = cnt;
while(c.num[i]==0) --i;
c.size = i;
c.negative = a.negative^b.negative;
return c;
}
BigInt add(BigInt a,BigInt b){
BigInt c = ZERO;
if(a.negative&&b.negative){
a.negative = false;
b.negative = false;
c = add(a,b);
c.negative = true;
return c;
}else if(a.negative&&!b.negative){
a.negative = false;
c = subtract(b,a);
return c;
}else if(!a.negative&&b.negative){
b.negative = false;
c = subtract(a,b);
return c;
}
int l = max(a.size,b.size);
for(int i=1;i<=l;++i)
c.num[i] = a.num[i]+b.num[i];
for(int i=1;i<=l;++i){
if(c.num[i]<10) continue;
c.num[i+1]++;
c.num[i] -= 10;
}
c.size = l;
if(c.num[l+1]!=0) c.size++;
return c;
}
BigInt _divide(BigInt a,int b){
bool flag = false;
if(b<0){
flag = true;
b = -b;
}
BigInt c = ZERO;
if(a<toBigInt(b)) return c;
int l,n = a.size;
l = n;
while(a.num[n]<b&&l>=1){
a.num[n-1] += (a.num[n]<<3)+(a.num[n]<<1);
a.num[n] = 0;
--n;
}
for(int i=n;i>=1;--i){
if(a.num[i]>=b){
c.num[i] = a.num[i]/b;
a.num[i] %= b;
}
a.num[i-1] += (a.num[i]<<3)+(a.num[i]<<1);
}
c.size = n;
c.negative = a.negative^flag;
return c;
}
BigInt subtract(BigInt a,BigInt b){
BigInt c = ZERO;
if(a.negative&&!b.negative){
a.negative = false;
c = add(a,b);
c.negative = true;
return c;
}else if(a.negative&&b.negative){
a.negative = false;
b.negative = false;
return subtract(b,a);
}else if(!a.negative&&b.negative){
b.negative = false;
c = add(a,b);
c.negative = false;
return c;
}
if(a<b){
c = subtract(b,a);
c.negative = true;
return c;
}else if(a==b) return c;
int l = max(a.size,b.size);
for(int i=1;i<=l;++i)
c.num[i] = a.num[i]-b.num[i];
for(int i=1;i<=l;++i){
if(c.num[i]>=0) continue;
c.num[i] += 10;
c.num[i+1]--;
}
while(!c.num[l]) --l;
if(l==0) l = 1;
c.size = l;
return c;
}
BigInt power(BigInt a,int t){
bool flag = false;
BigInt b = ONE;
if(t&1&&a.negative) flag = true;
while(t){
if(t&1) b = multiply(a,b);
a = multiply(a,a);
t >>= 1;
}
a.negative = flag;
return b;
}
BigInt _mod(BigInt a,int b){
BigInt c = _divide(a,b);
c = multiply(toBigInt(b),c);
c = subtract(a,c);
return c;
}
inline BigInt Abs(BigInt a){
a.negative = false;
return a;
}
struct grid{
BigInt m[2][2];
};
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
inline grid mul(grid a,grid b){
grid c;
c.m[0][0] = add(multiply(a.m[0][0],b.m[0][0]),multiply(a.m[1][0],b.m[0][1]));
c.m[1][0] = add(multiply(a.m[0][0],b.m[1][0]),multiply(a.m[1][0],b.m[1][1]));
c.m[0][1] = add(multiply(a.m[0][1],b.m[0][0]),multiply(a.m[1][1],b.m[0][1]));
c.m[1][1] = add(multiply(a.m[0][1],b.m[1][0]),multiply(a.m[1][1],b.m[1][1]));
return c;
}
inline grid mpow(grid a,int t){
grid ans;
ans.m[0][0] = ZERO;
ans.m[0][1] = ONE;
ans.m[1][0] = ONE;
ans.m[1][1] = ONE;
while(t){
if(t&1) ans = mul(ans,a);
a = mul(a,a);
t >>= 1;
}
return ans;
}
int main(){
int n;
read(n);
if(n==0){
putchar('0');
return 0;
}
grid a;
a.m[0][0] = ZERO;
a.m[0][1] = ONE;
a.m[1][0] = ONE;
a.m[1][1] = ONE;
grid ans = mpow(a,n-1);
print(ans.m[1][1]);
return 0;
}
```
by NaCly_Fish @ 2019-01-13 10:45:11
@[NaCly_Fish](/space/show?uid=115864) 那么下次搞个$n=10^5$的版本吧（大雾）
另外这都是什么神仙啊
by chen_zhe @ 2019-01-13 10:45:54
你要知道FFT的常数
by ezoixx130 @ 2019-01-13 10:48:18
@[ezoixx130](/space/show?uid=34886) fft常数一般还行吧
by chen_zhe @ 2019-01-13 10:49:13
反正Orz就对了
这都是什么神仙啊qwq
by 花里心爱 @ 2019-01-13 10:55:37
我是卡常数大佬
by 已注销%Jm9VScx @ 2019-01-13 10:56:01
@[Irressey](/space/show?uid=79017) orz您fAKe啊
by NaCly_Fish @ 2019-01-13 10:57:11
@[NaCly_Fish](/space/show?uid=115864) 窝连高精都不会dalao就开始用fft虐题了qwq
by 花里心爱 @ 2019-01-13 10:58:10
@[NaCly_Fish](/space/show?uid=115864) Orz 用 $\texttt{FFT}$ 虐普及题目的神仙！
by Siyuan @ 2019-01-13 11:03:21
@[Irressey](/space/show?uid=79017) 窝连A+B都不会dalao就开始吊打集训队了qwq
by NaCly_Fish @ 2019-01-13 11:03:49