CF1924C题解
liaiyang
·
·
题解
典型的推理题。
这个折纸很难推，但是我们知道 V=M+2\sqrt 2，因为显然每次折纸后山峰和山谷的增加量一样，且第一次的答案是 M=0，V=2\sqrt2。
而且每一次层数是 2 倍，长度是 \frac{\sqrt2}2 倍，所以每一次增加量是原增加量的 \sqrt 2 倍。
又因为第一次到第二次的增加量是 2，所以我们有
M=\sum_{i=0}^{n-2}2\sqrt 2^i=2\sum_{i=0}^{n-2}\sqrt 2^i=2\frac{\sqrt 2^{n-1}-1}{\sqrt 2-1}=2(\sqrt2^{n-1}-1)(\sqrt2+1)
V=M+2\sqrt 2
维护有理数添加 \sqrt2 的扩域 Q(\sqrt2)，在这上面做即可。
由于有快速幂，所以复杂度为 $O(\sum \log n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast")
#define int long long
#define y0 Y0
#define y1 Y1
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define P pair<int,int>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod)
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
#define submod(x,y,mod) (((x-=y)<0)&&(x+=mod))
#define addmod(x,y,mod) (((x+=y)>=mod)&&(x-=mod))
mt19937 rnd(time(0));
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(int u=0, char c=getchar(), bool f=false){
for(;!isdigit(c);c=getchar()) f|=c=='-';
for(;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+(c^'0');
return f?-u:u;
}
inline void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>9) wt(x/10);
putchar((x%10)^'0');
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1;
const int mod=999999893,g=3,gi=332748118;
const int N=2e5+10;
struct node{
int x,y;
node(int a,int b):x(a),y(b){}
};
node operator%(const node a,const int p){return node((a.x%p+p)%p,(a.y%p+p)%p);}
node operator+(const node a,const node b){return node(a.x+b.x,a.y+b.y);}
node operator-(const node a,const node b){return node(a.x-b.x,a.y-b.y);}
node operator*(const node a,const node b){return node(a.x*b.x+2*a.y*b.y,a.x*b.y+a.y*b.x);}
node power(node x,int k){
node res={1,0};x=x%mod;
while(k){
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
int power(int x,int k){
int res=1;x=x%mod;
while(k){
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
node operator/(const node a,const node b){
int u=power(b.x*b.x-2*b.y*b.y,mod-2);
return node((b.x*a.x-2*b.y*a.y)%mod*u%mod,(b.x*a.y-b.y*a.x)%mod*u%mod)%mod;
}
int n,T;
void work(){
n=rd;
node m=(((power(node(0,1),n-1)-node(1,0))%mod*node(1,1))%mod*node(2,0))%mod,v=(m+node(0,2))%mod;
wt((m/v).y,'\n');
}
main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
T=rd;
while(T--) work();
return 0;
}
```