来源：Comet OJ - Contest #13

芝士相关：复平面在信息学奥赛中的应用【雾

其实是道 sb 题？？？

发现原式貌似十分可二项式定理，然后发现确实如此

我们把 \(a^i\) 替换成 \(\sqrt{a}^{2i}\) 然后发现原式求的就是：\((\sqrt{a} +b)^n\) 展开后的偶数项

而这些偶数项有个性质，就是他们都不包含 \(\sqrt{a}\) ，所以我们可以把 \((\sqrt{a} +b)\) 转换到复平面上的点， \(b\) 做第一维， \(\sqrt a\) 做第二维

这样，每次第二维坐标相乘的时候乘上 A 丢给第一维就好了

那么最后咱就用快速幂搞出答案取个第一维就完事儿了

于是学过二次剩余的聚聚显然秒懂代码长什么样...

Code

一直 WA ，后来才发现自己第二维赋的初始值出锅了... （真是憨呢）

//by Judge (zlw ak ioi)

#include<bits/stdc++.h>

#define int __int128_t

using namespace std;

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int CCF=-1,Z;

inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}

inline void print(int x,char chr='\n'){

	if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;

	while(z[++Z]=x%10+48,x/=10);

	while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;

} int n,A,B,p;

struct cp{ int x,y; cp(){}

	cp(int _x,int _y){x=_x,y=_y;}

	cp operator *(const cp& b){

		return cp((x*b.x+y*b.y%p*A)%p , (x*b.y+y*b.x)%p);

	}

}s;

inline int qpow(cp x,int p){ s=cp(1,0);

	for(;p;p>>=1,x=x*x) if(p&1) s=s*x; return s.x;

}

inline void Solv(){

	n=read(),A=read(),B=read(),p=read();

	A%=p,B%=p,print(qpow(cp(B,1),n));

}

signed main(){ int T=read();

	while(T--) Solv(); return Ot(),0;

}

巴特西

Comet OJ - Contest #13 「火鼠的皮衣 -不焦躁的内心-」

Code

最新文章

热门文章