CometOJ contest#13「火鼠的皮衣 -不焦躁的内心-」（機關根反演）

給定 n , a , b , p n,a,b,p n,a,b,p，求

∑ i = 0 n 2 a i b n − i ∗ 2 ( n 2 ∗ i ) \sum_{i=0}^{\frac{n}{2}}a^ib^{n-i*2}\binom{n}{2*i} i=0∑2n​​aibn−i∗2(2∗in​)

指數不相同，醜陋

∑ i = 0 n 2 a i ∗ 2 b n − i ∗ 2 ( n 2 ∗ i ) \sum_{i=0}^{\frac{n}{2}}\sqrt a^{i*2}b^{n-i*2}\binom{n}{2*i} i=0∑2n​​a

​i∗2bn−i∗2(2∗in​)

直接枚舉 i ∗ 2 i*2 i∗2

∑ i = 0 n a i b n − i ( n i ) [ 2 ∣ i ] \sum_{i=0}^{n}\sqrt a^{i}b^{n-i}\binom{n}{i}[2|i] i=0∑n​a

​ibn−i(in​)[2∣i]

機關根反演

∑ i = 0 n a i b n − i ( n i ) ∑ j = 0 1 w 2 i j 2 = ∑ i = 0 n a i b n − i ( n i ) 1 + w 2 i 2 \sum_{i=0}^{n}\sqrt a^{i}b^{n-i}\binom{n}{i}\frac{\sum_{j=0}^1w_2^{ij}}{2}=\sum_{i=0}^{n}\sqrt a^{i}b^{n-i}\binom{n}{i}\frac{1+w_2^i}{2} i=0∑n​a

​ibn−i(in​)2∑j=01​w2ij​​=i=0∑n​a

​ibn−i(in​)21+w2i​​

= 1 2 ( ∑ i = 0 n a i b n − i ( n i ) + ∑ i = 0 n ( a w 2 1 ) i b n − i ( n i ) ) =\frac{1}{2}(\sum_{i=0}^{n}\sqrt a^{i}b^{n-i}\binom{n}{i}+\sum_{i=0}^{n}(\sqrt a w_2^1)^{i}b^{n-i}\binom{n}{i}) =21​(i=0∑n​a

​ibn−i(in​)+i=0∑n​(a

​w21​)ibn−i(in​))

= 1 2 ( ( a + b ) n + ( b − a ) n ) =\frac{1}{2}((\sqrt a+b)^n+(b-\sqrt a)^n) =21​((a

​+b)n+(b−a

​)n)

直接帶複數進行運算，兩個算出來實部正好相等， 1 2 \frac{1}{2} 21​ 的系數消掉，算一個的實部即可

orz cyk

#include<bits/stdc++.h>
#define cs const
using namespace std;
typedef long long ll;
ll n, A, B, p; int T;
ll add(ll a, ll b){ return (a + b) % p; }
ll mul(ll a, ll b){ return (a*b - (ll)((long double)a/p*b) * p + p) % p; }
struct node{
	ll x, y;
	node(ll _x = 0, ll _y = 0){ x = _x; y = _y; }
	node operator + (cs node &a){ return node(add(x, a.x), add(y, a.y)); }
	node operator - (cs node &a){ return node(add(x, p-a.x), add(y, p-a.y)); }
	node operator * (cs node &a){ return node(add(mul(x, a.y), mul(y, a.x)), add(mul(A, mul(x,a.x)), mul(y, a.y))); }
};
int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%lld%lld%lld%lld", &n, &A, &B, &p); A = A % p; B = B % p;
		node now(1, B), ans(0, 1);
		for(;n;n>>=1, now=now*now) if(n&1) ans=ans*now;
		cout << ans.y << '\n'; 
	} return 0; 
}