Codeforces #921 : Div1 C. Fractal Origami

コードは短め。
https://codeforces.com/contest/1924/problem/C

問題

整数Nが与えられる。
正方形の折り紙を、四つ角が中心に来るように折ると面積が半分になる。
この作業をN回行う。

山折りと谷折りの線の長さの非は、有理数A,Bを用いてA+B√2と表現できる。
このBを求めよ。

解法

山折り(M)と谷折り(V)の長さの差は常に一定。
一方、和は毎回√2倍になる。

すなわちV-M=2√2、V+M=2*(√2^(N+)-1)/(√2-1)となるので、ここからM/Vを答えればよい。

int T;
ll N;
const ll mo=999999893;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		__int128 DA=0,DB=2;
		__int128 SA=4*(modpow(2,N/2)-1)%mo;
		__int128 SB=2*(modpow(2,(N+1)/2)-1)%mo;
		
		__int128 PA=SA-DA,PB=SB-DB;
		__int128 QA=SA+DA,QB=SB+DB;
		
		__int128 PD=((PB*QA-PA*QB)%mo+mo)%mo;
		__int128 Q=QA*QA-2*QB*QB;
		PD=PD*modpow(Q%mo+mo)%mo;
		
		cout<<(ll)PD<<endl;
		
		
	}
}

まとめ

色々解法ありそうだけど、自力だともう少し面倒なコード組んじゃいそう。