loj6485 LJJ 学二项式定理

题目描述：

loj

题解：

单位根反演。

$[n|x]=\frac{1}{n} \sum _{i=0}^{n-1} (ω_n^x)^i$

证明？显然啊，要么停在$(1,0)$要么转一圈。

所以说题目要求的是$\sum _{i=0}^{n} C(n,i) * s^i * a_{i\;mod\;4}$

把$a$提前，变成$\sum_{k=0}^{3}a_k \sum _{i=0} ^{n} C(n,i) *s^i [4|i-k]$

然后把上面单位根反演式子套进去。后面变成$\sum _{i=0} ^n C(n,i) * s^i * \frac{1}{4} \sum _{j=0} ^{3} (ω_4 ^{i-1})^j$

把后面提前面：$\frac{1}{4} \sum_{j=0}^3 ω_4^{-j} \sum_{i=0}^{n} C(n,i)*s^i*ω_4^{ij}$

发现二项式定理：$\frac{1}{4} \sum_{j=0}^3 ω_4^{-j} * (sω_4^j+1)^n$

最后就剩快速幂了？

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int MOD = ;

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

ll fastpow(ll x,ll y)

{

    ll ret = ;

    while(y)

    {

        if(y&)ret=ret*x%MOD;

        x=x*x%MOD;y>>=;

    }

    return ret;

}

int T;

ll n,s,a0,a1,a2,a3,w0,w1,w2,w3,W0,W1,W2,W3,ans,inv;

void work()

{

    read(n),read(s),read(a0),read(a1),read(a2),read(a3);n%=(MOD-),ans=;

    W0 = fastpow(s*w0%MOD+,n),W1 = fastpow(s*w1%MOD+,n);

    W2 = fastpow(s*w2%MOD+,n),W3 = fastpow(s*w3%MOD+,n);

    ans=(ans+a0*(w0*W0%MOD+w0*W1%MOD+w0*W2%MOD+w0*W3%MOD)%MOD)%MOD;

    ans=(ans+a1*(w0*W0%MOD+w3*W1%MOD+w2*W2%MOD+w1*W3%MOD)%MOD)%MOD;

    ans=(ans+a2*(w0*W0%MOD+w2*W1%MOD+w0*W2%MOD+w2*W3%MOD)%MOD)%MOD;

    ans=(ans+a3*(w0*W0%MOD+w1*W1%MOD+w2*W2%MOD+w3*W3%MOD)%MOD)%MOD;

    printf("%lld\n",ans*inv%MOD);

}

int main()

{

//    freopen("tt.in","r",stdin);

    read(T);inv = fastpow(,MOD-);

    w0=,w1=fastpow(,(MOD-)/),w2=w1*w1%MOD,w3=w1*w2%MOD;

    while(T--)work();

    return ;

}

巴特西

loj6485 LJJ 学二项式定理

最新文章

热门文章